tyvj 1567:
博弈，题目给的数据是不超过1000位，所以这题应该找规律求解。
我是将30以内的sg值值求出来，然后规律就很容易看出来啦。
求sg值：
#include <stdio.h>
#include <string.h>
int sg[100][100];
int getsg(int x, int y)
{
int i;
if(sg[x][y] != -1)
return sg[x][y];
bool vis[100];
memset(vis, 0, sizeof(vis));
for(i = 1; i < x; i++)
vis[getsg(x - i, i)] = 1;
for(i = 1; i < y; i++)
vis[getsg(y - i, i)] = 1;
for(i = 0; i < 100; i++)
if(vis[i] == 0)
break;
return sg[x][y] = sg[y][x] = i;
}
int main (void)
{
memset(sg, -1, sizeof(sg));
int i, j;
for(i = 0; i < 100; i++)
sg[1][i] = sg[i][1] = 1;
for(i = 1; i <= 30; i ++)
for(j = 1; j <= 10; j++)
getsg(i, j);
//getsg(20, 20);//开始这样写，但是结果不对
for(i = 1; i <= 30; i ++)
{
for(j = 1; j <= 10; j++)
{
if(sg[i][j] != 0)
printf("1 ");
else
printf("0 ");
}
printf("\n");
}
return 0;
}
打出来的结果：
1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
恩 除此之外还有一种思考方式，可以直接找到规律，上面sg函数是以二维来思考的，我们也可以换作一维，那么n，就代表已经将其中一堆吃完，剩下那一堆将要被分割的糖果数是n。
当n = 1时，先手胜。
当n = 2，因为只能分成（1， 1）（胜， 胜）， 所以2是必败的。
当n = 3，可以分成（2， 1）（败， 胜），那么后手在面对（2， 1）这个状态的时候肯定是吃掉2这堆，留下1这堆，因为通过前面的分析知道分割1可以保证胜利，这样后手就会赢，所以3是必败的。
当n = 4时， 可以分成（2， 2）（败， 败）， （1， 3）（胜， 败），先手肯定要将两个必败态留给对手，所以肯定会选择分成（2， 2）。
当n = 5时， 可以分成（2， 3）（败， 败）， （1， 4）（胜， 胜）， 先手选择分成（2， 3）保证对手输。
也就是说如果n的后继状态中有一种分法（a， b），其中a和b都是必败的，那么n是必胜的，否则必败。
………………
推个20或者30的应该就可以看出规律：
1 2 3 4 5 6 7 8 9 10
1 0 0 1 1 1 0 0 1 1
11 12 13 14 15 16 17 18 19 20
1 0 0 1 1 1 0 0 1 1
(做题的时候如果头脑清楚思维敏捷，这应该也是不错的方法，但是感觉就是不太适合我_(:з」∠)_)
找到规律就很好写了～
#include <stdio.h>
#include <string.h>
char a[10010], b[10010];
int yes(char x)
{
if(x == '1' || x == '4' || x == '5' || x == '6' || x == '9' || x == '10')
return 1;
return 0;
}
int f(char x)
{
if(x == '2' || x == '3' || x == '7' || x == '8')
return 0;
return 1;
}
int main (void)
{
while(scanf("%s %s", a, b) != EOF)
{//只要判断最后一位
int len1 = strlen(a), len2 = strlen(b);
if(yes(a[len1 - 1]) || yes(b[len2 - 1]))
printf("Matrix67\n");
else
{
if(f(b[len2 - 1]) || f(a[len1 - 1]))
printf("Matrix67\n");
else
printf("Shadow\n");
}
}
return 0;
}