POJ 1222 EXTENDED LIGHTS OUT
//https://www.cnblogs.com/Empress/p/4156234.html
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int x[31],a[31][31],ca,T,i,j,n,m,t;
void gauss(int n,int m){
int k,col=0;
for (k=0;k<n && col<m;k++,col++){
int mx=k;
for (int i=k+1;i<n;i++)
if (a[i][col]>a[mx][col]) mx=i;
if (mx!=k)
for (int i=col;i<=m;i++) swap(a[k][i],a[mx][i]);
if (!a[k][col]){
k--;
continue;
}
for (int i=k+1;i<n;i++)
if (a[i][col])
for (int j=col;j<=m;j++) a[i][j]^=a[k][j];
}
for (int i=m-1;i>=0;i--){
x[i]=a[i][m];
for (int j=i+1;j<m;j++) x[i]^=a[i][j] && x[j];
}
}
int main(){
scanf("%d",&T);
n=5;m=6;
while (T--){
printf("PUZZLE #%d\n",++ca);
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
for (i=0;i<n;i++)
for (j=0;j<m;j++){
t=i*m+j;
a[t][t]=1;
if (i) a[(i-1)*m+j][t]=1;
if (i<n-1) a[(i+1)*m+j][t]=1;
if (j) a[i*m+j-1][t]=1;
if (j<m-1) a[i*m+j+1][t]=1;
}
for (i=0;i<n;i++)
for (j=0;j<m;j++) scanf("%d",&a[i*m+j][n*m]);
gauss(n*m,n*m);
for (i=0;i<n;i++)
for (j=0;j<m;j++) printf("%d%c",x[i*m+j],j==m-1?'\n':' ');
}
}POJ 1681 Painter’s Problem
//https://www.cnblogs.com/kuangbin/archive/2012/08/31/2665913.html
//本来这题要枚举自由元的，但因为数据水，所以过了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int x[230],a[230][230],ans,i,j,n,T,t;
char s[16];
int gauss(int n,int m){
int k,col=0;
for (k=0;k<n && col<m;k++,col++){
int mx=k;
for (int i=k+1;i<n;i++)
if (a[i][col]>a[mx][col]) mx=i;
if (mx!=k)
for (int i=col;i<=m;i++) swap(a[k][i],a[mx][i]);
if (!a[k][col]){
k--;
continue;
}
for (int i=k+1;i<n;i++)
if (a[i][col])
for (int j=col;j<=m;j++) a[i][j]^=a[k][j];
}
for (int i=k;i<n;i++)
if (a[i][col]) return -1;
for (int i=m-1;i>=0;i--){
x[i]=a[i][m];
for (int j=i+1;j<m;j++) x[i]^=a[i][j] && x[j];
}
return 0;
}
int main(){
scanf("%d",&T);
while (T--){
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
scanf("%d",&n);
for (i=0;i<n;i++){
scanf("%s",s);
for (j=0;j<n;j++) a[i*n+j][n*n]=(s[j]=='w');
}
for (i=0;i<n;i++)
for (j=0;j<n;j++){
t=i*n+j;
a[t][t]=1;
if (i) a[(i-1)*n+j][t]=1;
if (i<n-1) a[(i+1)*n+j][t]=1;
if (j) a[i*n+j-1][t]=1;
if (j<n-1) a[i*n+j+1][t]=1;
}
if (gauss(n*n,n*n)==-1){
puts("inf");
continue;
}
ans=0;
for (i=0;i<n*n;i++) ans+=x[i];
printf("%d\n",ans);
}
}POJ 1753 Flip Game
//https://www.cnblogs.com/alihenaixiao/p/4621918.html
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int x[17],a[17][17],mn,n,i,fi[17],fnum[17],b[17];
char s[5][5];
int gauss(int n,int m){
int k,col=0,cnt=0;
memset(fi,0,sizeof(fi));
memset(b,0,sizeof(b));
for (k=0;k<n && col<m;k++,col++){
int mx=k;
for (int i=k+1;i<n;i++)
if (a[i][col]>a[mx][col]) mx=i;
if (mx!=k)
for (int i=col;i<=m;i++) swap(a[k][i],a[mx][i]);
if (!a[k][col]){
fi[col]=1;
b[cnt++]=col;
k--;
continue;
}
for (int i=k+1;i<n;i++)
if (a[i][col])
for (int j=col;j<=m;j++) a[i][j]^=a[k][j];
}
for (int i=k;i<n;i++)
if (a[i][col]) return 1e9;
int res=1e9;
for (int i=0;i<1<<cnt;i++){
int nu=0,tmp=i;
memset(fnum,0,sizeof(fnum));
for (int j=0;j<cnt;j++){
if (tmp&1) fnum[b[j]]=1,nu++;
tmp>>=1;
}
for (int j=k-1;j>=0;j--)
if (!fi[j]){
int temp=a[j][m];
for (int l=j+1;l<m;l++)
if (a[j][l]) temp^=fnum[l];
fnum[j]=temp;
if (temp) nu++;
}
res=min(res,nu);
}
return res;
}
void solve(char c){
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
for (int i=0;i<n;i++)
for (int j=0;j<n;j++) a[i*n+j][n*n]=(s[i][j]==c);
for (int i=0;i<n;i++)
for (int j=0;j<n;j++){
int t=i*n+j;
a[t][t]=1;
if (i) a[(i-1)*n+j][t]=1;
if (i<n-1) a[(i+1)*n+j][t]=1;
if (j) a[i*n+j-1][t]=1;
if (j<n-1) a[i*n+j+1][t]=1;
}
mn=min(mn,gauss(n*n,n*n));
}
int main(){
n=4;
for (i=0;i<n;i++) scanf("%s",s[i]);
mn=1e9;
solve('w');
solve('b');
if (mn==1e9) puts("Impossible");
else printf("%d",mn);
}POJ 1830 开关问题
//https://www.cnblogs.com/shenben/p/6265976.html
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int ans,n,i,a[30][30],b[30],x,y,T;
int gauss(int n,int m){
int k,col=0;
for (k=0;k<n && col<m;k++,col++){
int mx=k;
for (int i=k+1;i<n;i++)
if (a[i][col]>a[mx][col]) mx=i;
if (mx!=k)
for (int i=col;i<=m;i++) swap(a[k][i],a[mx][i]);
if (!a[k][col]){
k--;
continue;
}
for (int i=k+1;i<n;i++)
if (a[i][col])
for (int j=col;j<=m;j++) a[i][j]^=a[k][j];
}
for (int i=k;i<n;i++)
if (a[i][col]) return -1;
return m-k;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);memset(a,0,sizeof(a));
for (i=0;i<n;i++) scanf("%d",&b[i]);
for (i=0;i<n;i++) scanf("%d",&a[i][n]),a[i][n]^=b[i];
for (i=0;i<n;i++) a[i][i]=1;
while (~scanf("%d%d",&x,&y) && x && y) a[y-1][x-1]=1;//注意，是a[y-1][x-1]
ans=gauss(n,n);
if (ans==-1) puts("Oh,it's impossible~!!");
else printf("%d\n",1<<ans);
}
}POJ 3185 The Water Bowls
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,a[21][21],ans,b[21],fi[21],x[21];
void gauss(int n,int m){
int k,col=0,cnt=0;
for (k=0;k<n && col<m;k++,col++){
int mx=k;
for (int i=k+1;i<n;i++)
if (a[i][col]>a[mx][col]) mx=i;
if (mx!=k)
for (int i=col;i<=m;i++) swap(a[k][i],a[mx][i]);
if (!a[k][col]){
k--;fi[cnt++]=col;
b[col]=1;
continue;
}
for (int i=k+1;i<n;i++)
if (a[i][col])
for (int j=col;j<=m;j++) a[i][j]^=a[k][j];
}
for (int t=0;t<1<<cnt;t++){
int tmp=t,num=0;memset(x,0,sizeof(x));
for (int i=0;i<cnt;i++){
if (tmp&1) x[fi[i]]=1,num++;
tmp>>=1;
}
for (int i=k-1;i>=0;i--)
if (!b[i]){
int temp=a[i][m];
for (int j=i+1;j<n;j++) temp^=a[i][j] && x[j];
x[i]=temp;
if (temp) num++;
}
ans=min(ans,num);
}
}
int main(){
n=20;
for (i=0;i<n;i++){
scanf("%d",&a[i][n]);
a[i][i]=1;
if (i) a[i-1][i]=1;
if (i<n-1) a[i+1][i]=1;
}
ans=1e9;
gauss(n,n);
printf("%d",ans);
}POJ 2947 Widget Factory
//https://www.cnblogs.com/gj-Acit/p/3903085.html
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int a[302][302],x[302],i,j,k,n,m,ans,xx,yy;
char st[5],end[5],str[7][4]={"MON","TUE","WED","THU","FRI","SAT","SUN"};
int find(char *s){
for (int i=0;i<7;i++)
if (!strcmp(str[i],s)) return i;
}
int lcm(int x,int y){return x/__gcd(x,y)*y;}
void ex_gcd(int a,int b,int &x,int &y){
if (!b){
x=1,y=0;
return;
}
ex_gcd(b,a%b,y,x);
y-=a/b*x;
}
int gauss(int n,int m){
int k=0,col=0;
for (;k<n && col<m;k++,col++){
int mx=k;
for (int i=k+1;i<n;i++)
if (abs(a[i][col])>abs(a[mx][col])) mx=i;
if (mx!=k)
for (int i=col;i<=m;i++) swap(a[k][i],a[mx][i]);
if (!a[k][col]){
k--;
continue;
}
for (int i=k+1;i<n;i++)
if (a[i][col]){
int LCM=lcm(abs(a[i][col]),abs(a[k][col]));
int ta=LCM/a[i][col],tb=LCM/a[k][col];
if (a[i][col]*a[k][col]<0) tb=-tb;
for (int j=col;j<=m;j++) a[i][j]=((a[i][j]*ta-a[k][j]*tb)%7+7)%7;
}
}
for (int i=k;i<n;i++)
if (a[i][col]) return -1;
if (k<m) return 1;
for (int i=m-1;i>=0;i--){
int tmp=a[i][m];
for (int j=i+1;j<m;j++) tmp-=a[i][j]*x[j]%7;
tmp=(tmp%7+7)%7;
ex_gcd(a[i][i],7,xx,yy);
x[i]=(tmp*xx%7+7)%7;
if (x[i]<3) x[i]+=7;
}
return 0;
}
int main(){
while (~scanf("%d%d",&m,&n) && m && n){
memset(a,0,sizeof(a));
for (i=0;i<n;i++){
scanf("%d%s%s",&k,st,end);
for (j=0;j<k;j++) scanf("%d",&xx),(a[i][xx-1]+=1)%=7;
a[i][m]=find(end)-find(st)+1;
}
ans=gauss(n,m);
if (ans==-1) puts("Inconsistent data.");
else if (ans==1) puts("Multiple solutions.");
else for (i=0;i<m;i++) printf("%d%c",x[i],i==m-1?'\n':' ');
}
}POJ 1166 The Clocks
//https://blog.csdn.net/u010885899/article/details/49781635
#include<cstdio>
#include<algorithm>
using namespace std;
int i,j,fl,a[10][10],x[10],xx,yy;
void ex_gcd(int a,int b,int &x,int &y){
if (!b) x=1,y=0;
else ex_gcd(b,a%b,y,x),y-=a/b*x;
}
int lcm(int x,int y){
return x/__gcd(x,y)*y;
}
void gauss(int n,int m){
int k=0,col=0;
for (;k<n && col<m;k++,col++){
int mx=k;
for (;mx<n;mx++)//要改成这样，但不懂为什么，网上没解释
if (abs(a[mx][col])) break;
if (mx!=k)
for (int i=col;i<=m;i++) swap(a[k][i],a[mx][i]);
if (!a[k][col]){
k--;
continue;
}
for (int i=k+1;i<n;i++)
if (a[i][col]){
int LCM=lcm(abs(a[i][col]),abs(a[k][col]));
int ta=LCM/a[i][col],tb=LCM/a[k][col];
if (a[i][col]*a[k][col]<0) tb=-tb;
for (int j=col;j<=m;j++) a[i][j]=((a[i][j]*ta-a[k][j]*tb)%4+4)%4;
}
}
for (int i=m-1;i>=0;i--){
int tmp=a[i][m];
for (int j=i+1;j<m;j++) tmp-=a[i][j]*x[j]%4;
ex_gcd(a[i][i],4,xx,yy);
x[i]=(tmp*xx%4+4)%4;
}
}
int main(){
for (i=0;i<3;i++)
for (j=0;j<3;j++) scanf("%d",&a[i*3+j][9]),a[i*3+j][9]=4-a[i*3+j][9];
a[0][0]=a[1][0]=a[3][0]=a[4][0]=1;
a[0][1]=a[1][1]=a[2][1]=1;
a[1][2]=a[2][2]=a[4][2]=a[5][2]=1;
a[0][3]=a[3][3]=a[6][3]=1;
a[1][4]=a[3][4]=a[4][4]=a[5][4]=a[7][4]=1;
a[2][5]=a[5][5]=a[8][5]=1;
a[3][6]=a[4][6]=a[6][6]=a[7][6]=1;
a[6][7]=a[7][7]=a[8][7]=1;
a[4][8]=a[5][8]=a[7][8]=a[8][8]=1;
gauss(9,9);
for (i=0;i<9;i++)
for (j=0;j<x[i];j++){
if (fl) putchar(' ');
fl=1;
putchar(i+1+48);
}
}HDU 3949 XOR(线性基模板)
//线性基：https://blog.csdn.net/qaq__qaq/article/details/53812883
//题解：https://blog.csdn.net/qq_33184171/article/details/54695958
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,i,m,cnt,ca;
ll p[65],a[10002],d[65],k,ans;
void gauss(){
for (int i=0;i<n;i++)
for (int j=63;j>=0;j--)
if (a[i]&(1ll<<j))
if (d[j]) a[i]^=d[j];
else{d[j]=a[i];break;}
for (int i=63;i>=0;i--)
for (int j=i-1;j>=0;j--)
if (d[i]&(1ll<<j)) d[i]^=d[j];
cnt=0;
for (int i=0;i<64;i++)
if (d[i]) p[cnt++]=d[i];
}
int main(){
scanf("%d",&T);
while (T--){
printf("Case #%d:\n",++ca);
scanf("%d",&n);
for (i=0;i<n;i++) scanf("%lld",&a[i]);
memset(d,0,sizeof(d));
gauss();
scanf("%d",&m);
while (m--){
scanf("%lld",&k);
if (n!=cnt) k--;
if (k>=(1ll<<cnt)){
puts("-1");
continue;
}
ans=0;
for (i=0;i<cnt;i++)
if (k&(1ll<<i)) ans^=p[i];
printf("%lld\n",ans);
}
}
} 另外还有几道题，可以去做一下，老师布置了，但太神，我放弃了
HDU 4818 RP problem
POJ 1487 Single-Player Games
hdu OJ 2449
foj1704 Turn off the light
HDU 3976 Electric resistance
京公网安备 11010502036488号