棋盘
Time Limit: 1000 ms Memory Limit: 65535 kB Solved: 124 Tried: 377
Description
UDK和RU在一个白色的方格棋盘上玩游戏，棋盘有N行M列，由N*M个小方格组成。两人轮流进行游戏，UDK先开始，然后是RU。在每一轮游戏中，当前一方需要在棋盘上选择一个1*k或k*1的全白矩形，并将里面的k个小格子全部染成黑色（每轮k的大小都可以由当前玩家自己决定），将最后一个格子染色的一方获得游戏胜利。
现在假设两人都采取最佳的策略，给定棋盘大小，请问谁将获得胜利？
Input
数据的第一行是一个整数T(0 <= T <= 10000)，代表一共有T组测试数据。
接下来T行，每行由两个整数N和M组成(1 <= N, M <= 100)，表示了每组数据中棋盘的大小。
Output
请严格输出T行，每行仅包括一个字符串"UDK" 或者 "RU"，代表每组测试数据对应的胜利一方的姓名。
Sample Input
2
1 2
2 2
Sample Output
UDK
RU
Hint
Sample Input中共有两组数据，其中第一组数据棋盘的大小是1*2，即1行2列，UDK先手，可以直接选择涂1*2的矩阵，把棋盘完全染色从而直接获得胜利。
请严格按照输出规则输出，行末不允许有多余的空格，最后一组数据行末同样需要换行。
Source
第五届ACM趣味程序设计竞赛第二场（正式赛）
题解：博弈题，刚开始时，dp[i][j]表示i行j列时先手胜为1败为0，我就只能想到是如果dp[i-1][j]和的dp[i][j-1]有一个为0时
则dp[i][j]必定为1，因为先手可以走一步就可以达到先手必输的状态，让自己必赢。
但是如果相邻的两个状态都是1呢？？？？
后来看了解题报告才知道自己方向想错了。。
当i和j都是偶数时先手必输，因为后手可以一直摆和先手对称的局面。那这样最后一定是后手赢了。。
当i和j都是奇数时先手必胜。因为先手可以摆一个在最中间。然后就一直跟着后手走。同上。最后先手赢。。
当i和j为奇偶时先手必赢。因为就像我刚开始想的一样。dp[i-1][j]和dp[i][j-1]必定有一个为0就是都是偶数先手必输。
。。。。。。。
最后总结一下：博弈论可以从上一步走一步就可以达到对方必输的局面。后者是跟着对方对称走。最后就会赢。。
#include<cstdio>
#include<cstring>
int dp[105][105];
char di[2][10] = {"RU","UDK"};
void Init()
{
int i,j;
for(i=1;i<101;i++)
{
dp[i][1] = 1;
dp[1][i] = 1;
}
for(i=2;i<101;i++)
for(j=2;j<101;j++)
{
if(dp[i-1][j]==0 || dp[i][j-1]==0)
dp[i][j] = 1;
else
{
if(i%2==0 && j%2==0)
dp[i][j] = 0;
else
dp[i][j] = 1;
}
}
}
int main()
{
int t,n,m;
scanf("%d",&t);
Init();
while(t--)
{
scanf("%d%d",&n,&m);
printf("%s\n",di[dp[n][m]]);
}
return 0;
}