基层科普网站建设的现状,网站设计的一般流程是什么,建筑工程类招聘网站,网易网站开发POJ 2311 Cutting Game
题目大意
有一张有whw\times hwh个格子的长方形纸张#xff0c;两个人轮流将当前的纸张中选一张#xff0c;并沿着格子的边界将这张纸剪成两部分。最先切出只有一个格子的纸张#xff08;111\times 111的纸张#xff09;的玩家获胜。当双方都采用最…POJ 2311 Cutting Game
题目大意
有一张有w×hw\times hw×h个格子的长方形纸张两个人轮流将当前的纸张中选一张并沿着格子的边界将这张纸剪成两部分。最先切出只有一个格子的纸张1×11\times 11×1的纸张的玩家获胜。当双方都采用最优策略时问先手必胜还是必败。必胜则输出WIN必败则输出LOSE。
有多组数据。
数据范围
2≤w,h≤2002\leq w,h\leq 2002≤w,h≤200 题解
令sg[i][j]sg[i][j]sg[i][j]表示i×ji\times ji×j的纸张的状态那么枚举剪的位置kkk则
sg[i][j]mex{sg[i][k]⊕sg[i][j−k],sg[i][k]⊕sg[i][j−k]}sg[i][j]mex\{sg[i][k]\oplus sg[i][j-k],sg[i][k]\oplus sg[i][j-k]\}sg[i][j]mex{sg[i][k]⊕sg[i][j−k],sg[i][k]⊕sg[i][j−k]}
我们可以预处理出所有sg[i][j]sg[i][j]sg[i][j]。
然后对于每一组w,hw,hw,h答案即为sg[w][h]sg[w][h]sg[w][h]可以O(1)O(1)O(1)得出。
时间复杂度为O(n3)O(n^3)O(n3)。 code
#includeiostream
#includecstdio
using namespace std;
int n,m,z[205],sg[205][205];
int main()
{for(int i1;i200;i){for(int j1;j200;j){for(int k0;k200;k) z[k]0;for(int k2;ki-1;k){z[sg[k][j]^sg[i-k][j]]1;}for(int k2;kj-1;k){z[sg[i][k]^sg[i][j-k]]1;}int x0;for(;z[x];x);sg[i][j]x;}}while(scanf(%d%d,n,m)!EOF){if(sg[n][m]) printf(WIN\n);else printf(LOSE\n);}return 0;
}
