白书博弈学习

nim博弈 n堆火柴，每堆有若干个火柴，两人轮流拿，每次可以选择一堆至少拿一个，也可以整堆拿走，无法拿的人输。

每堆火柴的个数异或和==0，先手输，否则先手赢。

http://acm.hust.edu.cn/vjudge/problem/32746 UVA11859

题意：给2维矩阵，每次可以选择矩阵的一行中的1个或多个大于1的整数，把他们每个数都变成真因子。 12可以变1 2 3 4 6.

解法：等价于拿掉一个或者多个素因子，一行对应一堆火柴，每个数每个素因子看成一个火柴，即nim博弈。

 1 #include<bits/stdc++.h>
 2 #define mt(a,b) memset(a,b,sizeof(a))
 3 using namespace std;
 4 const int M=1e4+10;
 5 int a[64][64];
 6 char answer[2][8]={"NO","YES"};
 7 vector<int> prime;
 8 bool is[M];
 9 int n,m;
10 void init(){
11     mt(is,0);
12     for(int i=2;i*i<M;i++){
13         if(is[i]) continue;
14         for(int j=i*i;j<M;j+=i){
15             is[j]=true;
16         }
17     }
18     prime.clear();
19     for(int i=2;i<M;i++){
20         if(is[i]) continue;
21         prime.push_back(i);
22     }
23 //    printf("%d",prime[prime.size()-1]);
24 }
25 int solve(){
26     int nim=0;
27     for(int i=0;i<n;i++){
28         int sum=0;
29         for(int j=0;j<m;j++){
30             for(int k=0;k<prime.size();k++){
31                 if(prime[k]>a[i][j]) continue;
32                 while(a[i][j]%prime[k]==0){
33                     sum++;
34                     a[i][j]/=prime[k];
35                 }
36             }
37         }
38         nim^=sum;
39     }
40     return nim!=0;
41 }
42 int main(){
43     init();
44     int t;
45     while(~scanf("%d",&t)){
46         int cas=1;
47         while(t--){
48             scanf("%d%d",&n,&m);
49             for(int i=0;i<n;i++){
50                 for(int j=0;j<m;j++){
51                     scanf("%d",&a[i][j]);
52                 }
53             }
54             printf("Case #%d: %s\n",cas++,answer[solve()]);
55         }
56     }
57     return 0;
58 }

View Code

end

白书 博弈学习

推荐阅读

白书博弈学习