poj_高斯消元总结

《poj_高斯消元总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.开关问题：poj1222EXTENDEDLIGHTSOUThttp://162.105.81.212/JudgeOnline/problem?id=1222poj1681Painter'sProblemhttp://162.105.81.212/JudgeOnline/problem?id=1681poj1830开关问题http://162.105.81.212/JudgeOnline/problem?id=1830设有矩阵D，X，A；D代表方程组的系数，A代表最终的状态，X为解，则建立方程组D*X=A（mod2）；该方程代表灯泡开始全

2、为关，然后我们按下某些开关，使灯泡的最后状态为A。如果逆向思维，我们再次按些这些开关，则所有灯泡为关，因此，我们只需解出X即可。构造系数时d[i][j]代表第i个开关要影响第j个灯时为1，否则为0。X[i]==1代表该开关按下，0代表不按下。1830代码实现：#include#includeusingnamespacestd;boold[230][230];intn;voidGauss(){inti,j,k,p;k=1;for(i=1;i<=n;i++)//一个循环找一个解{j=i;while(d[j][k

3、]==0){while(d[j][k]==0){j++;if(j>n)break;}if(j>n){for(p=1;p=n+1)return;}}//当前x可能为无解或不定元解if(j>i)for(p=k;p<=n+1;p++)swap(d[j][p],d[i][p]);for(j=1;j<=n;j++)if(d[j][k]==1&&j!=i){for(p=k;p<=n+1;p++)d[j][p]^=d[i][p];}k++;i

4、f(k>=n+1)return;}}//上三角阵intmain(){intt,i,j;scanf("%d",&t);while(t--){memset(d,0,sizeof(d));scanf("%d",&n);inta[30];for(i=1;i<=n;i++)scanf("%d",&a[i]);inttemp;for(i=1;i<=n;i++){scanf("%d",&temp);if(a[i]!=temp)d[i][n+1]=1;d[i][i]=1;}intr,c;while(scanf("%d%d",&r,&c),r

5、c){d[c]

6、[r]=1;}/*for(i=1;i<=n;i++){for(j=1;j<=n+1;j++)printf("%d",d[i][j]);puts("");}*/Gauss();intcnt=0,f=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++){if(d[i][j]==1)break;}if(j>n){if(d[i][n+1]==1)f=1;elsecnt++;}}if(f)printf("Oh,it'simpossible~!!");elseprintf("%d",(int)pow(2.0,cnt));}

7、return0;}1.方程组取模运算poj2947http://162.105.81.212/JudgeOnline/problem?id=2947poj2065http://162.105.81.212/JudgeOnline/problem?id=2065这两个题就主要是建立方程形式A*B=C（%mod）;2947代码实现：方程数m和未知数n不相等。·#include·#include·#include·usingnamespacestd;··intd[302][302];·inta

8、ns[302];·intm,n,x,y;·intfind(char*s)·{·if(strcmp(s,"MON")==0)return1;·elseif(strcmp(s,"TUE")==0)return2;·elseif(strcmp(s,"WED")==0)return3;·elseif(strcmp(s,"THU")==0)return4;·elseif(strcmp(s,"FRI")==0)return5;·elseif(strcmp(s,"SAT")==0)return6;·elseif(strcmp(s,"SUN")==0)re

9、turn7;·}·intgcd(inta,intb)·{·if(b==0)returna;·returngcd(b,a%b);·}·intlcm(inta,intb)·{·ret