[博弈]HDU_2873
传送门
VC时死活过不了的一题,原来是我把题目的输入搞错了,这出题的也太搞了,把读入的第一行的第一个当成(1,1)居然也不表示一下,我表示很蛋疼- -||,一般不都是第一行的最后一个表示(n,m)的么?
VC时,我说:我保证sg函数没错,然后我保证是这样搞的,然后就没有然后了,就一直死活过不了,后来找了报告,发现看不懂他的代码,不过思想也是博弈SG函数.然后作死的调啊调.可能是上天可怜我了,给我一组数据,而且我对拍是发现不对,最最重要的是,发现了那个正确的读入和我的不同啊@@@@@@.我想死啊.尼玛就不能说明下啊.
下面是说明,对于SG函数,sg[i]=mex{n,i可到n},mex是集合中未出现的最小值(>=0).然后对于对个SG游戏的当前局面就是当前所有点的sg函数的异或,这个Game Theory上有证明,自己去看去.然后就没有然后了,这题就变成水题了.代码:
1. #include
2. #include
3. #include
4. #include
5. int sg[56][56];
6. int n,m;
7. void init_sg()
8. {
9. int i,j;
10. int used[5151];
11. int ii,jj;
12. for(i=1i<56;i++)
13. {
14. sg[i][1]=i-1
15. sg[1][i]=i-1
16. }
17. for(i=2i<51;i++)
18. {
19. for(j=2j<51;j++)
20. {
21. memset(used,0,sizeof(used));
22. for(ii=1ii
23. {
24. for(jj=1jj
25. {
26. used[sg[ii][j]^sg[i][jj]]=1
27. }
28. }
29. for(ii=0ii<2501;ii++)
30. {
31. if(0 == used[ii])
32. {
33. sg[i][j]=ii;
34. break
35. }
36. }
37. }
38. }
39. #if 0
40. printf(“:::::::::::::::::::\n”);
41. for(i=1i<6;i++)
42. {
43. for(j=1j<6;j++)
44. printf(“%d “,sg[i][j]);
45. printf(“\n”);
46. }
47. printf(“:::::::::::::::::::\n”);
48. #endif
49. }
50. void work()
51. {
52. int i,j;
53. char c;
54. int ans=0
55. for(i=1i<=n;i++)
56. {
57. for(j=1j<=m;j++)
58. {
59. scanf(“%c”,c);
60. if(‘#’ == c)
61. {
62. ans ^= sg[i][j];
63. }
64. }
65. getchar();
66. }
67. if(0 == ans)
68. printf(“Jack\n”);
69. else
70. printf(“John\n”);
71. return ;
72. }
73. int main(void)
74. {
75. freopen(“2873.in”,“r”,stdin);
76. freopen(“2873.out”,“w”,stdout);
77. init_sg();
78. while(1)
79. {
80. scanf(“%d%d%c”,n,&m);
81. if(0 == n & 0==m)
82. break
83. work();
84. }
85. return 0
86. }
