Cutting Game POJ2311(SG函数)
2022/2/2 23:17:40
本文主要是介绍Cutting Game POJ2311(SG函数),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Cutting Game - POJ 2311 - Virtual Judge
SG函数深入理解orz:博弈论 SG函数_Strangedbly-CSDN博客_sg函数
AC代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) //#pragma GCC optimize("Ofast") #include <iostream> #include <queue> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <cctype> #include <map> #include <vector> #include <deque> #include <set> #include <stack> #include <numeric> #include <iomanip> #include <functional> using namespace std; #define lowbit(x) ((x) & -(x)) #define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); #define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); typedef vector<int> vi; typedef vector<long long> vll; typedef vector<char> vc; template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T power(T a, int b) { T res = 1; for (; b; b >>= 1, a = a * a) { if (b & 1) { res = res * a; } } return res; } template <typename T> inline void read(T& x) { x = 0; int f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); } x *= f; } /* Tips: 1.int? long long? 2.don't submit wrong answer 3.figure out logic first, then start writing please 4.know about the range 5.check if you have to input t or not 6.modulo of negative numbers is not a%b, it is a%b + abs(b) */ const int INF = 0x3f3f3f3f; const int mod = 1000000007; const double PI = acos(-1.0); vector<vector<int> > sg(210, vector<int>(210, -1)); int getsg(int n, int m) { if (sg[n][m] != -1) { return sg[n][m]; } vector<int> vis(1006, 0); for (int i = 2; i <= n - i; i++) { vis[getsg(i, m) ^ getsg(n - i, m)] = 1; } for (int i = 2; i <= m - i; i++) { vis[getsg(n, i) ^ getsg(n, m - i)] = 1; } for (int i = 0;; i++) { if (vis[i] == 0) { return sg[n][m] = i; } } } void solve() { int w, h; while (cin >> w >> h) { if (getsg(w, h)) { cout << "WIN" << endl; } else { cout << "LOSE" << endl; } } } int main() { //IOS1; IOS2; int __t = 1; //cin >> __t; for (int _t = 1; _t <= __t; _t++) { solve(); } return 0; } /* */
这篇关于Cutting Game POJ2311(SG函数)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验
- 2024-05-29AutoMQ 对象存储数据高效组织的秘密: Compaction
- 2024-05-29活动预告|来 GIAC 大会听大数据降本利器:AutoMQ 基于云原生重新设计的 Kafka