高斯消元专题 - c++编程基础

}
for(int i=k+1;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 a[i][j]=((a[i][j]*ta-a[k][j]*tb)%2+2)%2;
}
}
// debug();
for(int i=k;i if(a[i][col]) return inf;

for(int i=0,j;i if(!a[i][i])
{
for(j=i+1;j if(a[i][j]) break;
if(j>=var) break;
for(int r=0;r }

/* int ret=inf,lim= (1<<(var-k));

for(int j=0;j {
for(int i=0;i<(var-k);i++)
if(j&(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 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 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 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 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< 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
连动题
[cpp]
#include
#include
#include
#include

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 {
int mx=k;
for(int i=k+1;i if(a[i][col]>a[mx][col]) mx=i;
if(mx!=k)
for(int i=k;i if(!a[k][col]) { k--;continue; }
for(int i=k+1;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 a[i][j]=((a[i][j]*ta)%2 - (a[k][j]*tb)%2+2)%2;
}
}

for(int i=k;i if(a[i][var]) return inf;
for(int i=0,j;i if(!a[i][i])
{
for(j=i+1;j if(a[i][j]) break;
if(var==j) break;
for(int r=0;r }

int ret=inf;
long long lim= (1<<(var-k));

for(long long j=0;j {
for(int i=0;i<(var-k);i++)
if(j&(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 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 if(x[i]) cnt++;
ret=min(cnt,ret);
if(ret==0) break;
}

return ret;

高斯消元专题(二)