高斯消元专题由于老师的讲课，我又重拾高斯消元，做了一天的高斯，感觉老师讲得很好，模板也不错，我懒得自己写
高斯消元专题
由于老师的讲课，我又重拾高斯消元，做了一天的高斯，感觉老师讲得很好，模板也不错，我懒得自己写，就把同僚的模板拿过来用了，反正基本原理都懂了。
http://poj.org/problem?id=1222
高斯消元模板题，只有唯一解。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=30;int a[maxn][maxn+1],x[maxn];int equ,var,free_num;void Debug(){ for(int i=0;i<equ;i++) { for(int j=0;j<var+1;j++) cout<<a[i][j]<<" "; cout<<endl; }}int gcd(int a,int b){ if(a<0) return gcd(-a,b); if(b<0) return gcd(a,-b); return b==0?a:gcd(b,a%b);}int Gauss(){ int k,col=0; for(k=0;k<equ&&col<var;k++,col++) { int mx=k; for(int i=k+1;i<equ;i++) if(a[i][col]>a[mx][col]) mx=i; if(mx!=k) for(int i=k;i<var+1;i++) swap(a[k][i],a[mx][i]); if(!a[k][col]) { k--;continue; } for(int i=k+1;i<equ;i++) if(a[i][col]!=0) { int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][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<var+1;j++) a[i][j]=((a[i][j]*ta)%2 - (a[k][j]*tb)%2+2)%2; } } // Debug(); //cout<<col<<endl<<endl; for(int i=k;i<equ;i++) if(a[i][var]) return -1; for(int i=0,j;i<equ;i++) if(!a[i][i]) { for(j=i+1;j<var;j++) if(a[i][j]) break; if(j>=var) break; for(int r=0;r<equ;r++) swap(a[r][i],a[r][j]); } //唯一解 for(int i=k-1;i>=0;i--) { int tmp=a[i][var]%2; for(int j=i+1;j<var+1;j++) if(a[i][j]) tmp=(tmp-a[i][j]*x[j]%2+2)%2; x[i]=(tmp/a[i][i])%2; }}void init(){ memset(a,0,sizeof(a)); memset(x,0,sizeof(x)); for(int i=0;i<5;i++) for(int j=0;j<6;j++) { if(i!=0) a[i*6+j][(i-1)*6+j]=1; if(i!=4) a[i*6+j][(i+1)*6+j]=1; if(j!=0) a[i*6+j][i*6+j-1]=1; if(j!=5) a[i*6+j][i*6+j+1]=1; a[i*6+j][i*6+j]=1; }}int main(int argc, char *argv[]){ int T,ca=1; scanf("%d",&T); equ=30,var=30; while(T--) { init(); for(int i=0;i<30;i++) scanf("%d",&a[i][30]); Gauss(); printf("PUZZLE #%d\n",ca++); for(int i=0;i<30;i++) { if(i%6!=0) putchar(' '); printf("%d",x[i]); if(i%6==5) puts(""); } } return EXIT_SUCCESS;}
http://poj.org/problem?id=1681
动最少的砖，枚举自由元，找1的个数最少的那组解。
#include <iostream>#include <cstdio>#include <cstring>#include <stdio.h>using namespace std;const int inf=0x3fffffff;const int maxn=15*15;int a[maxn][maxn+1],x[maxn],equ,var,n; char s[20][20];void init(){ equ=var=n*n; for(int i=0;i<n;i++) scanf("%s",s[i]); memset(a,0,sizeof(a)); for(int i=0;i<var;i++) a[i][var]= (s[i/n][i%n]!='y'),a[i][i]=1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) { /* if(i!=0) a[(i-1)*n+j][i*n+j]=1; if(i!=n-1) a[(i+1)*n+j][i*n+j]=1; if(j!=0) a[i*n+j-1][i*n+j]=1; if(j!=n-1) a[i*n+j+1][i*n+j]=1;*/ if(i-1>=0) a[i*n+j][(i-1)*n+j]=1; if(i+1<n) a[i*n+j][(i+1)*n+j]=1; if(j-1>=0) a[i*n+j][i*n+j-1]=1; if(j+1<n) a[i*n+j][i*n+j+1]=1; }}void debug(){ for(int i=0;i<equ;i++) { for(int j=0;j<=var;j++) cout<<a[i][j]<<" "; cout<<endl; } cout<<endl;}int gcd(int a,int b){ if(a<0) return gcd(-a,b); if(b<0) return gcd(a,-b); return b==0?a:gcd(b,a%b);}int gauss(){ int k,col; for(k=col=0;k<equ&&col<var;k++,col++) { int mx=k; for(int i=k+1;i<equ;i++) if(a[i][col]>a[mx][col]) mx=i; if(k!=mx){ for(int i=k;i<var+1;i++) swap(a[k][i],a[mx][i]); } if(!a[k][col]){ k--;continue; } for(int i=k+1;i<equ;i++) if(a[i][col]) { int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][col]; int ta=lcm/a[i][col],tb=lcm/a[k][col]; for(int j=col;j<var+1;j++) a[i][j]=((a[i][j]*ta-a[k][j]*tb)%2+2)%2; } } // debug(); for(int i=k;i<equ;i++) if(a[i][col]) return inf; for(int i=0,j;i<equ;i++) if(!a[i][i]) { for(j=i+1;j<var;j++) if(a[i][j]) break; if(j>=var) break; for(int r=0;r<equ;r++) swap(a[r][i],a[r][j]); } /* int ret=inf,lim= (1<<(var-k)); for(int j=0;j<lim;j++) { for(int i=0;i<(var-k);i++) if(j&(1<<i)) x[equ-1-i]=1; else x[equ-1-i]=0; for(int i=k-1;i>=0;i--) { int tmp=a[i][var]; for(int j=i+1;j<var;j++) tmp=((tmp-a[i][j]*x[j])%2+2)%2; x[i]=tmp/a[i][i]%2; } int cnt=0; for(int i=0;i<var;i++) if(x[i]) cnt++; ret=min(cnt,ret); if(ret==0) break; }*/ // 二进制枚举 int Min=inf; for(int j=0;j<(1<<(equ-k));j++) { int tmp=j,p=equ-1; while(tmp) x[p--]=tmp%2,tmp>>=1; for(int i=k-1;i>=0;i--) { int tmp=a[i][var]%2; for(int j=i+1;j<var;j++) if(a[i][j]) tmp=(tmp-a[i][j]*x[j]%2+2)%2; x[i]=(tmp/a[i][i])%2; } tmp=0; for(int i=0;i<var;i++) tmp+=x[i]; Min=min(Min,tmp); if(Min==0) break; } //全部枚举 return Min;}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d",&n); init(); // debug(); int re=gauss(); //cout<<re<<endl; if(re==inf) puts("inf"); else printf("%d\n",re); } return 0;}
http://poj.org/problem?id=1753
同上，不贴代码了
http://poj.org/problem?id=3185
没什么特别的
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3858
枚举四种图案，没什么特别的
http://acm.hdu.edu.cn/showproblem.php?pid=4200
连动题
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=101;const int inf=0x3fffffff;int a[maxn][maxn+1],x[maxn];int equ,var,free_num;int n,m;int gcd(int a,int b){ if(a<0) return gcd(-a,b); if(b<0) return gcd(a,-b); return b==0?a:gcd(b,a%b);}int Gauss(){ int k,col=0; for(k=0;k<equ&&col<var;k++,col++) { int mx=k; for(int i=k+1;i<equ;i++) if(a[i][col]>a[mx][col]) mx=i; if(mx!=k) for(int i=k;i<var+1;i++) swap(a[k][i],a[mx][i]); if(!a[k][col]) { k--;continue; } for(int i=k+1;i<equ;i++) if(a[i][col]!=0) { int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][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<var+1;j++) a[i][j]=((a[i][j]*ta)%2 - (a[k][j]*tb)%2+2)%2; } } for(int i=k;i<equ;i++) if(a[i][var]) return inf; for(int i=0,j;i<equ;i++) if(!a[i][i]) { for(j=i+1;j<var;j++) if(a[i][j]) break; if(var==j) break; for(int r=0;r<equ;r++) swap(a[r][i],a[r][j]); } int ret=inf; long long lim= (1<<(var-k)); for(long long j=0;j<lim;j++) { for(int i=0;i<(var-k);i++) if(j&(1<<i)) x[equ-1-i]=1; else x[equ-1-i]=0; for(int i=k-1;i>=0;i--) { int tmp=a[i][var]; for(int j=i+1;j<var;j++) tmp=((tmp-a[i][j]*x[j])%2+2)%2; x[i]=tmp/a[i][i]%2; } int cnt=0; for(int i=0;i<var;i++) if(x[i]) cnt++; ret=min(cnt,ret); if(ret==0) break; } return ret;}void init(){ memset(a,0,sizeof(a)); memset(x,0,sizeof(x)); for(int i=0;i<n;i++) { scanf("%d",&a[i][var]); a[i][i]=1; } for(int i=0;i<n;i++) { int p,q; if(i-m>=0) p=i-m;else p=0; if(i+m<n) q=i+m;else q=n-1; for(int j=p;j<=q;j++) a[j][i]=1; } return ;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); //cout<<"*"<<endl; equ=n;var=n; init(); int ans=Gauss(); if(ans==inf) puts("impossible"); else printf("%d\n",ans); } return 0;}
http://poj.org/problem?id=2947
同余题
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=301;const int inf=0x3fffffff;int a[maxn][maxn+1],x[maxn];int equ,var,free_num;char str[8][4]={"MON","TUE","WED","THU","FRI","SAT","SUN"};__int64 exGcd(__int64 a,__int64 b, __int64 &xx, __int64 &yy){ if(b == 0) { xx = 1; yy = 0; return a; } __int64 r = exGcd(b, a % b, xx, yy); __int64 t = xx; xx = yy; yy = t - a / b * yy; return r;}int gcd(int a,int b){ if(a<0) return gcd(-a,b); if(b<0) return gcd(a,-b); return b==0?a:gcd(b,a%b);}void Gauss(){ int k,col=0; __int64 xx,yy; for(k=0;k<equ&&col<var;k++,col++) { int mx=k; for(int i=k+1;i<equ;i++) if(abs(a[i][col])>abs(a[mx][col])) mx=i; if(mx!=k) for(int i=k;i<var+1;i++) swap(a[k][i],a[mx][i]); if(!a[k][col]) { k--;continue; } for(int i=k+1;i<equ;i++) if(a[i][col]!=0) { int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][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<var+1;j++) a[i][j]=((a[i][j]*ta)%7 - (a[k][j]*tb)%7+7)%7; } } for(int i=k;i<equ;i++) if(a[i][col]!=0) {puts("Inconsistent data.");return ;} if(var>k){puts("Multiple solutions.");return ;} for(int i=0,j;i<equ;i++) if(a[i][i]==0) { for(j=i+1;j<var;j++) if(a[i][j]) break; //if(var==j) break; if(j>=var) break; for(int r=0;r<equ;r++) swap(a[r][i],a[r][j]); } for(int i=k-1;i>=0;i--) { int tmp=a[i][var]%7; for(int j=i+1;j<var;j++) if(a[i][j]) tmp=(tmp-a[i][j]*x[j]%7+7)%7; __int64 d=exGcd(a[i][i],7,xx,yy); if(tmp%d!=0){puts("Inconsistent data.");return ;} else{ x[i]=tmp/d*xx%7+7; x[i]=x[i]%(7/d); } while(x[i]<3) x[i]=x[i]+7; } for(int i=0;i<var;i++) { if(i==0) cout<<x[i]; else cout<<" "<<x[i]; } puts("");}void init(){ memset(a,0,sizeof(a)); memset(x,0,sizeof(x)); int d; char s1[4],s2[4]; for(int i=0;i<equ;i++) { scanf("%d%s%s",&d,s1,s2); int q1,q2; for(int j=0;j<8;j++) if(!strcmp(s1,str[j])){q1=j;break;} for(int j=0;j<8;j++) if(!strcmp(s2,str[j])){q2=j;break;} while(d--) { int num; scanf("%d",&num); num--;a[i][num]++; a[i][num]%=7; } a[i][var]=(q2-q1+1+7)%7; } return ;}int main(){ while(scanf("%d%d",&var,&equ)!=EOF) { if(var==0&&equ==0) break; init(); Gauss(); } return 0;}
http://poj.org/problem?id=2065
同上