POJ1222 http://poj.org/problem?id=1222

一定有解，直接高斯消元搞定

[cpp] view plaincopy

1. #include <iostream>  
2. #include <cmath>  
3. #include <cstdio>  
4. #include <cstring>  
5. using namespace std;  
6.   
7. const int maxn =30;  
8.   
9. int equ,var;  
10.   
11. int a[maxn+1][maxn+1],x[maxn];  
12.   
13. void Gauss(){  
14.     int k,col;  
15.     for(k=0,col=0;k<equ&&col<var;k++,col++){  
16.         int mx=k;  
17.         for(int i=k+1;i<equ;i++)  
18.             if(a[i][col]>a[mx][col]) mx=i;  
19.         if(mx!=k)  
20.             for(int i=col;i<var+1;i++)  
21.             swap(a[k][i],a[mx][i]);  
22.         if(!a[k][col]){k--;continue;}  
23.         for(int i=k+1;i<equ;i++){  
24.             if(a[i][col]!=0){  
25.                 for(int j=col;j<var+1;j++)  
26.                     a[i][j]^=a[k][j];  
27.             }  
28.         }  
29.     }  
30.     for(int i=var-1;i>=0;i--){  
31.         int tmp=a[i][var];  
32.         for(int j=i+1;j<var;j++) tmp^=(a[i][j]&&x[j]);  
33.         x[i]=tmp;  
34.     }  
35. }  
36.   
37. void init(){  
38.     memset(a,0,sizeof(a));  
39.     memset(x,0,sizeof(x));  
40.     for(int i=0;i<5;i++){  
41.         for(int j=0;j<6;j++){  
42.             if(i!=0) a[i*6+j][(i-1)*6+j]=1;  
43.             if(i!=4) a[i*6+j][(i+1)*6+j]=1;  
44.             if(j!=0) a[i*6+j][i*6+j-1]=1;  
45.             if(j!=5) a[i*6+j][i*6+j+1]=1;  
46.             a[i*6+j][i*6+j]=1;  
47.         }  
48.     }  
49. }  
50.   
51. int main()  
52. {  
53.     int t,ca=1;  
54.     cin>>t;  
55.     while(t--){  
56.         init();  
57.         equ=var=30;  
58.         for(int i=0;i<30;i++)  
59.             cin>>a[i][30];  
60.         Gauss();  
61.         printf("PUZZLE #%d\n",ca++);  
62.         for(int i=0;i<30;i++)  
63.         {  
64.             if(i%6!=0) putchar(‘ ‘);  
65.             printf("%d",x[i]);  
66.             if(i%6==5) puts("");  
67.         }  
68.     }  
69.     return 0;  
70. }  

高斯消元判断有没有解，然后二进制枚举自由变元 求最小值

[cpp] view plaincopy

1. #include <iostream>  
2. #include <cstring>  
3. #include <cstdio>  
4. #include <cmath>  
5. using namespace std;  
6.   
7. const int maxn = 16*16;  
8.   
9. int a[maxn][maxn],x[maxn],n;  
10. int free_num,free_x[maxn],equ,var;  
11. char mp[20][20];  
12.   
13. void init()  
14. {  
15.     memset(a,0,sizeof(a));  
16.     memset(free_x,0,sizeof(free_x));  
17.     memset(x,0,sizeof(x));  
18.     free_num=0;  
19.     for(int i=0;i<n;i++){  
20.         for(int j=0;j<n;j++){  
21.             if(i!=0) a[i*n+j][(i-1)*n+j]=1;  
22.             if(i!=n-1) a[i*n+j][(i+1)*n+j]=1;  
23.             if(j!=0) a[i*n+j][i*n+j-1]=1;  
24.             if(j!=n-1) a[i*n+j][i*n+j+1]=1;  
25.             a[i*n+j][i*n+j]=1;  
26.         }  
27.     }  
28.     equ=var=n*n;  
29. }  
30.   
31. int Gauss()  
32. {  
33.     int k,col;  
34.     for(k=0,col=0;k<equ&&col<var;k++,col++){  
35.         int mx=k;  
36.         for(int i=k+1;i<equ;i++)  
37.             if(a[i][col]>a[mx][col]) mx=i;  
38.         if(k!=mx){  
39.             for(int i=col;i<var+1;i++)  
40.                 swap(a[k][i],a[mx][i]);  
41.         }  
42.         if(!a[k][col]){  
43.             k--;  
44.             free_x[free_num++]=col;  
45.             continue;  
46.         }  
47.         for(int i=k+1;i<equ;i++){  
48.             if(a[i][col]!=0){  
49.                 for(int j=col;j<var+1;j++)  
50.                     a[i][j]^=a[k][j];  
51.             }  
52.         }  
53.     }  
54.     for(int i=k;i<equ;i++)  
55.         if(a[i][col]) return -1;  
56.     return var-k;  
57. }  
58.   
59. void solve()  
60. {  
61.     int t=Gauss();  
62.     //cout<<"t "<<t<<endl;  
63.     if(t==-1){  
64.         printf("inf\n");  
65.         return ;  
66.     }  
67.     int ans;  
68.     if(t==0){  
69.         ans=0;  
70.         for(int i=var-1;i>=0;i--){  
71.             x[i]=a[i][var];  
72.             for(int j=i+1;j<var;j++)  
73.                 x[i]^=(a[i][j]&&x[j]);  
74.             ans+=x[i];  
75.         }  
76.     }  
77.     else{  
78.         ans=1000000000;  
79.         /*cout<<"******"<<endl; 
80.         for(int i=0;i<t;i++) 
81.             cout<<free_x[i]<<" "; 
82.         cout<<endl<<"*******"<<endl;*/  
83.         for(int i=0;i<(1<<t);i++){  
84.             int tmp=0;  
85.             for(int j=0;j<t;j++){  
86.                 if(i&(1<<j)){  
87.                     x[free_x[j]]=1;  
88.                     tmp++;  
89.                 }  
90.                 else  
91.                     x[free_x[j]]=0;  
92.             }  
93.             for(int j=var-t-1,k;j>=0;j--){  
94.                 for(k=j;k<var;k++)  
95.                     if(a[j][k]) break;  
96.                 x[k]=a[j][var];  
97.                 for(int l=k+1;l<var;l++)  
98.                     x[k]^=(a[j][l]&&x[l]);  
99.                 tmp+=x[k];  
100.             }  
101.             ans=min(tmp,ans);  
102.         }  
103.     }  
104.     printf("%d\n",ans);  
105. }  
106.   
107. int main()  
108. {  
109.     int t;  
110.     scanf("%d",&t);  
111.     while(t--){  
112.         scanf("%d",&n);  
113.         init();  
114.         for(int i=0;i<n;i++)  
115.             scanf("%s",mp[i]);  
116.         for(int i=0;i<n;i++){  
117.             for(int j=0;j<n;j++){  
118.                 if(mp[i][j]==‘w‘)  
119.                     a[i*n+j][n*n]=1;  
120.             }  
121.         }  
122.         solve();  
123.     }  
124.     return 0;  
125. }  

同上

[cpp] view plaincopy

1. #include <iostream>  
2. #include <cstring>  
3. #include <cstdio>  
4. using namespace std;  
5.   
6. const int maxn = 17;  
7.   
8. int equ,var,free_num,free_x[maxn];  
9. int a[maxn][maxn],x[maxn];  
10. char mp[4][4];  
11.   
12. void init()  
13. {  
14.     memset(a,0,sizeof(a));  
15.     memset(x,0,sizeof(x));  
16.     var=equ=16;  
17.     free_num=0;  
18.     for(int i=0;i<4;i++){  
19.         for(int j=0;j<4;j++){  
20.             if(i!=0) a[i*4+j][(i-1)*4+j]=1;  
21.             if(i!=3) a[i*4+j][(i+1)*4+j]=1;  
22.             if(j!=0) a[i*4+j][i*4+j-1]=1;  
23.             if(j!=3) a[i*4+j][i*4+j+1]=1;  
24.             a[i*4+j][i*4+j]=1;  
25.         }  
26.     }  
27. }  
28.   
29. int Gauss()  
30. {  
31.     int k,col;  
32.     for(k=0,col=0;k<equ&&col<var;k++,col++){  
33.         int mx=k;  
34.         for(int i=k+1;i<equ;i++)  
35.             if(a[i][col]>a[mx][col]) mx=i;  
36.         for(int i=col;i<var+1;i++)  
37.             swap(a[k][i],a[mx][i]);  
38.         if(!a[k][col]){  
39.             k--;  
40.             free_x[free_num++]=col;  
41.             continue;  
42.         }  
43.         for(int i=k+1;i<equ;i++){  
44.             if(a[i][col]){  
45.                 for(int j=col;j<var+1;j++)  
46.                     a[i][j]^=a[k][j];  
47.             }  
48.         }  
49.     }  
50.     for(int i=k;i<equ;i++)  
51.         if(a[i][col]) return -1;  
52.     return var-k;  
53. }  
54.   
55. int calu()  
56. {  
57.     int t=Gauss();  
58.     //cout<<"t "<<t<<endl;  
59.     if(t==-1) return -1;  
60.     int ans;  
61.     if(t==0){  
62.         ans=0;  
63.         for(int i=var-1;i>=0;i--){  
64.             x[i]=a[i][var];  
65.             for(int j=i+1;j<var;j++)  
66.                 x[i]^=(x[j]&&a[i][j]);  
67.             ans+=x[i];  
68.         }  
69.     }  
70.     else{  
71.         ans=10000000;  
72.         for(int i=0;i<(1<<t);i++){  
73.             int tmp=0;  
74.             for(int j=0;j<t;j++){  
75.                 if(i&(1<<j)){  
76.                     x[free_x[j]]=1;  
77.                     tmp++;  
78.                 }  
79.                 else  
80.                     x[free_x[j]]=0;  
81.             }  
82.             for(int j=var-t-1,k;j>=0;j--){  
83.                 for(k=j;k<var;k++)  
84.                     if(a[j][k]) break;  
85.                 x[k]=a[j][var];  
86.                 for(int l=k+1;l<var;l++)  
87.                     x[k]^=(a[j][l]&&x[l]);  
88.                 tmp+=x[k];  
89.             }  
90.             ans=min(ans,tmp);  
91.         }  
92.     }  
93.     return ans;  
94. }  
95.   
96. int main()  
97. {  
98.     while(~scanf("%s",mp[0])){  
99.         scanf("%s%s%s",mp[1],mp[2],mp[3]);  
100.         init();  
101.         for(int i=0;i<4;i++){  
102.             for(int j=0;j<4;j++){  
103.                 if(mp[i][j]==‘w‘)  
104.                     a[i*4+j][16]=0;  
105.                 else  
106.                     a[i*4+j][16]=1;  
107.             }  
108.         }  
109.         int ans1=calu();  
110.         init();  
111.         for(int i=0;i<4;i++){  
112.             for(int j=0;j<4;j++){  
113.                 if(mp[i][j]==‘b‘)  
114.                     a[i*4+j][16]=0;  
115.                 else  
116.                     a[i*4+j][16]=1;  
117.             }  
118.         }  
119.         int ans2=calu();  
120.         //cout<<"ans1  ans2 "<<ans1<<" "<<ans2<<endl;  
121.         if(ans1>=0&&ans2>=0){  
122.             cout<<min(ans1,ans2)<<endl;  
123.         }  
124.         else{  
125.             if(ans1<0&&ans2<0)  
126.                 cout<<"Impossible"<<endl;  
127.             else  
128.                 cout<<max(ans1,ans2)<<endl;  
129.         }  
130.     }  
131.     return 0;  
132. }  

求解的方案数 每个变量有两种取值  则总数为2^x  个 x为自由变量的个数

[cpp] view plaincopy

1. #include <iostream>  
2. #include <cstring>  
3. #include <cstdio>  
4. #include <cmath>  
5. using namespace std;  
6.   
7. int free_num,n;  
8. int a[30][30],s[30],e[30],x[30];  
9. int Gauss()  
10. {  
11.     int k,col;  
12.     for(k=0,col=0;k<n&&col<n;k++,col++){  
13.         int mx=k;  
14.         for(int i=k+1;i<n;i++)  
15.             if(a[mx][col]<a[i][col]) mx=i;  
16.         if(mx!=k){  
17.             for(int i=col;i<n+1;i++)  
18.                 swap(a[k][i],a[mx][i]);  
19.         }  
20.         if(!a[k][col]){  
21.             k--;  
22.             continue;  
23.         }  
24.         for(int i=k+1;i<n;i++){  
25.             if(a[i][col]!=0){  
26.                 for(int j=col;j<n+1;j++)  
27.                     a[i][j]^=a[k][j];  
28.             }  
29.         }  
30.     }  
31.     for(int i=k;i<n;i++){  
32.         if(a[i][col]!=0)  
33.             return -1;  
34.     }  
35.     return n-k;  
36. }  
37. int main()  
38. {  
39.     int t;  
40.     cin>>t;  
41.     while(t--){  
42.         cin>>n;  
43.         for(int i=0;i<n;i++)  
44.             cin>>s[i];  
45.         for(int j=0;j<n;j++)  
46.             cin>>e[j];  
47.         int x,y;  
48.         memset(a,0,sizeof(a));  
49.         for(int i=0;i<n;i++)  
50.             a[i][i]=1;  
51.         while(1){  
52.             cin>>x>>y;  
53.             if(x==0&&y==0)  
54.                 break;  
55.             a[y-1][x-1]=1;  
56.         }  
57.         for(int i=0;i<n;i++)  
58.             a[i][n]=s[i]^e[i];  
59.         int free_num=Gauss();  
60.         if(free_num==-1)  
61.             cout<<"Oh,it‘s impossible~!!"<<endl;  
62.         else  
63.             cout<<(1<<free_num)<<endl;  
64.         Gauss();  
65.     }  
66.     return 0;  
67. }  

一维的更简单 随便搞 

[cpp] view plaincopy

1. #include <iostream>  
2. #include <cstring>  
3. #include <cstdio>  
4. using namespace std;  
5.   
6. const int maxn = 21;  
7.   
8. int equ,var,free_num,free_x[maxn];  
9. int a[maxn][maxn],x[maxn],s[maxn];  
10.   
11. void init()  
12. {  
13.     memset(a,0,sizeof(a));  
14.     memset(x,0,sizeof(x));  
15.     var=equ=20;  
16.     free_num=0;  
17.     for(int i=0;i<20;i++){  
18.         a[i][i]=1;  
19.         if(i!=0) a[i][i-1]=1;  
20.         if(i!=19) a[i][i+1]=1;  
21.         if(s[i]) a[i][20]=1;  
22.     }  
23. }  
24.   
25. int Gauss()  
26. {  
27.     int k,col;  
28.     for(k=0,col=0;k<equ&&col<var;k++,col++){  
29.         int mx=k;  
30.         for(int i=k+1;i<equ;i++)  
31.             if(a[i][col]>a[mx][col]) mx=i;  
32.         for(int i=col;i<var+1;i++)  
33.             swap(a[k][i],a[mx][i]);  
34.         if(!a[k][col]){  
35.             k--;  
36.             free_x[free_num++]=col;  
37.             continue;  
38.         }  
39.         for(int i=k+1;i<equ;i++){  
40.             if(a[i][col]){  
41.                 for(int j=col;j<var+1;j++)  
42.                     a[i][j]^=a[k][j];  
43.             }  
44.         }  
45.     }  
46.     for(int i=k;i<equ;i++)  
47.         if(a[i][col]) return -1;  
48.     return var-k;  
49. }  
50.   
51. int calu()  
52. {  
53.     int t=Gauss();  
54.     if(t==-1) return -1;  
55.     int ans;  
56.     if(t==0){  
57.         ans=0;  
58.         for(int i=var-1;i>=0;i--){  
59.             x[i]=a[i][var];  
60.             for(int j=i+1;j<var;j++)  
61.                 x[i]^=(x[j]&&a[i][j]);  
62.             ans+=x[i];  
63.         }  
64.     }  
65.     else{  
66.         ans=10000000;  
67.         for(int i=0;i<(1<<t);i++){  
68.             int tmp=0;  
69.             for(int j=0;j<t;j++){  
70.                 if(i&(1<<j)){  
71.                     x[free_x[j]]=1;  
72.                     tmp++;  
73.                 }  
74.                 else  
75.                     x[free_x[j]]=0;  
76.             }  
77.             for(int j=var-t-1,k;j>=0;j--){  
78.                 for(k=j;k<var;k++)  
79.                     if(a[j][k]) break;  
80.                 x[k]=a[j][var];  
81.                 for(int l=k+1;l<var;l++)  
82.                     x[k]^=(a[j][l]&&x[l]);  
83.                 tmp+=x[k];  
84.             }  
85.             ans=min(ans,tmp);  
86.         }  
87.     }  
88.     return ans;  
89. }  
90. int main()  
91. {  
92.     while(~scanf("%d",&s[0])){  
93.         for(int i=1;i<20;i++)  
94.             scanf("%d",&s[i]);  
95.         init();  
96.         cout<<calu()<<endl;  
97.     }  
98.     return 0;  
99. }  

AX=B  => X=A^(-1)*B  通过逆矩阵来求X,当然这题也可以打表 把A的逆矩阵给打出来 后面来一组数据乘一次 效率很高

[cpp] view plaincopy

1. #include <iostream>  
2. #include <cstring>  
3. #include <cstdio>  
4. using namespace std;  
5.   
6. int a[16][33];  
7. int free_x[16],equ,var;  
8. int c[16][16];  
9. /*int c[16][16]={ 
10. 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 
11. 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 
12. 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
13. 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 
14. 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 
15. 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 
16. 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 
17. 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 
18. 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 
19. 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 
20. 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 
21. 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 
22. 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 
23. 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 
24. 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 
25. 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1 
26. };*/  
27. void init()  
28. {  
29.     memset(a,0,sizeof(a));  
30.     int k=0;  
31.     for(int i=0;i<4;i++){  
32.         for(int j=0;j<4;j++){  
33.             k=i*4+j;  
34.             for(int p=0;p<4;p++){  
35.                 a[k][i*4+p]=1;  
36.                 a[k][p*4+j]=1;  
37.             }  
38.         }  
39.     }  
40.     for(int i=0;i<16;i++) a[i][i+16]=1;  
41. }  
42.   
43.   
44.   
45. void gauss()  
46. {  
47.     for(int i=0;i<16;i++){  
48.         int k;  
49.         for(k=i;k<16;k++)  
50.             if(a[k][i]) break;  
51.         for(int j=0;j<32;j++) swap(a[i][j],a[k][j]);  
52.         for(int j=0;j<16;j++){  
53.             if(i!=j&&a[j][i]){  
54.                 for(int k=0;k<32;k++)  
55.                     a[j][k]=a[j][k]^a[i][k];  
56.             }  
57.         }  
58.     }  
59.     for(int i=0;i<16;i++)  
60.         for(int j=0;j<16;j++)  
61.         c[i][j]=a[i][j+16];  
62. }  
63. int main()  
64. {  
65.     char mp[10];  
66.     int b[16];  
67.     memset(b,0,sizeof(b));  
68.     for(int i=0;i<4;i++){  
69.         cin>>mp;  
70.         for(int j=0;j<4;j++){  
71.             if(mp[j]==‘+‘)  
72.                 b[i*4+j]=1;  
73.         }  
74.     }  
75.     init();  
76.     gauss();  
77.     /*for(int i=0;i<16;i++){ 
78.         for(int j=0;j<16;j++) 
79.             cout<<c[i][j]<<","; 
80.         cout<<endl; 
81.     }*/  
82.     int ans[16];  
83.     int sum=0;  
84.     memset(ans,0,sizeof(ans));  
85.     for(int i=0;i<16;i++){  
86.         for(int j=0;j<16;j++)  
87.         ans[i]=ans[i]^(c[i][j]&&b[j]);  
88.         sum+=ans[i];  
89.     }  
90.     cout<<sum<<endl;  
91.     for(int i=0;i<16;i++){  
92.         if(ans[i]==1)  
93.             cout<<i/4+1<<" "<<i%4+1<<endl;  
94.     }  
95.     return 0;  
96. }  

高斯消元学习