高斯消元

hdu 3949 XOR http://acm.hdu.edu.cn/showproblem.php?pid=3949 2013-1-18

给n个数，由这些数异或得到新的数，求第k小的数

把所有数看做一个向量空间，先求出向量空间的一个基

矩阵中mt(r,c)=a[r]>>(m-1-c) 化为约化阶梯矩阵
View Code

1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const int N=100010;
 8 LL a[N];
 9 int n,m=60;
10 int mt(int r,int c)
11 {
12     return (a[r]>>(m-1-c))&1;
13 }
14 int gauss(int n,int m)
15 {
16     for(int r=0,c=0;r<n && c<m;r++,c++)
17     {
18         int p=r;
19         while(p<n && mt(p,c)==0) p++;
20         if(p==n) {r--; continue;}
21         if(r!=p) swap(a[r],a[p]);
22         for(int i=0;i<n;i++)
23             if(i!=r && mt(i,c)==1) a[i]^=a[r];
24     }
25     for(int i=0;i<n;i++)
26         if(a[i]==0) return i;
27     return n;
28 }
29 int main()
30 {
31     int T,C=0;
32     scanf("%d",&T);
33     while(T--)
34     {
35         printf("Case #%d:n",++C);
36         scanf("%d",&n);
37         for(int i=0;i<n;i++) scanf("%I64d",&a[i]);
38         int r=gauss(n,m);
39         int q;
40         scanf("%d",&q);
41         while(q--)
42         {
43             LL k;
44             scanf("%I64d",&k);
45             if(r<n) k--;
46             if(k>=(1LL<<r))
47             {
48                 printf("-1n");
49                 continue;
50             }
51             LL ans=0;
52             for(int i=0;i<r;i++)
53                 if((k>>i)&1) ans^=a[r-1-i];
54             printf("%I64dn",ans);
55         }
56     }
57     return 0;
58 }

hdu 3364 Lanterns http://acm.hdu.edu.cn/showproblem.php?pid=3364 2013-1-17

开关灯，求解的个数
View Code

1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 const int N=55;
 8 bool sw[N][N];
 9 int mt[N][N];
10 LL gauss(int n,int m)
11 {
12     int r,c;
13     for(r=0,c=0;r<n && c<m;r++,c++)
14     {
15         int p=r;
16         while(p<n && mt[p][c]==0) p++;
17         if(p==n) {r--; continue;}
18         if(p!=r) for(int j=c;j<=m;j++)
19             swap(mt[p][j],mt[r][j]);
20         for(int i=r+1;i<n;i++) if(mt[i][c]!=0)
21             for(int j=c;j<=m;j++) mt[i][j]^=mt[r][j];
22     }
23     for(int i=r;i<n;i++)
24         if(mt[i][m]!=0) return 0;
25     return (1LL<<(m-r));
26 }
27 int main()
28 {
29     int T,C=0;
30     scanf("%d",&T);
31     while(T--)
32     {
33         printf("Case %d:n",++C);
34         memset(sw,0,sizeof(sw));
35         int n,m;
36         scanf("%d%d",&n,&m);
37         for(int i=0;i<m;i++)
38         {
39             int k;
40             scanf("%d",&k);
41             for(int j=0;j<k;j++)
42             {
43                 int a;
44                 scanf("%d",&a);
45                 sw[i][a-1]=true;
46             }
47         }
48         int q;
49         scanf("%d",&q);
50         while(q--)
51         {
52             memset(mt,0,sizeof(mt));
53             for(int i=0;i<n;i++)
54             {
55                 int a;
56                 scanf("%d",&a);
57                 mt[i][m]=a;
58                 for(int j=0;j<m;j++)
59                     if(sw[j][i]) mt[i][j]=1;
60             }
61             LL ans=gauss(n,m);
62             printf("%I64dn",ans);
63         }
64     }
65     return 0;
66 }

hdu 4200 Bad Wiring http://acm.hdu.edu.cn/showproblem.php?pid=4200 2013-1-17

开关灯，枚举所有解
View Code

1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N=110;
 7 int mt[N][N],a[N];
 8 int gauss(int n,int m)
 9 {
10     for(int r=0,c=0;r<n && c<m;r++,c++)
11     {
12         int p=r;
13         while(p<n && mt[p][c]==0) p++;
14         if(p==n) {r--; continue;}
15         if(p!=r) for(int i=c;i<=m;i++)
16             swap(mt[p][i],mt[r][i]);
17         for(int i=r+1;i<n;i++) if(mt[i][c]!=0)
18         {
19             for(int j=c;j<=m;j++) mt[i][j]^=mt[r][j];
20         }
21     }
22     for(int i=0;i<n;i++) if(mt[i][i]==0)
23     {
24         int p=i+1;
25         while(p<n && mt[i][p]==0) p++;
26         if(p==n)
27         {
28             for(int j=i;j<n;j++)
29                 if(mt[j][n]!=0) return n+1;
30             return i;
31         }
32         for(int j=0;j<n;j++) swap(mt[j][i],mt[j][p]);
33     }
34     return n;
35 }
36 int main()
37 {
38 //freopen("in.txt","r",stdin);
39     int T;
40     scanf("%d",&T);
41     while(T--)
42     {
43         int n,d;
44         scanf("%d%d",&n,&d);
45         memset(mt,0,sizeof(mt));
46         for(int i=0;i<n;i++) scanf("%d",&mt[i][n]);
47         for(int i=0;i<n;i++)
48             for(int j=i-d>=0?i-d:0;j<=i+d && j<n;j++) mt[i][j]=1;
49         int r=gauss(n,n);
50         if(r>n) {printf("impossiblen"); continue;}
51         int ans=n;
52         for(int x=0;x<(1<<(n-r));x++)
53         {
54             for(int i=0;i<n-r;i++) a[r+i]=(x>>i)&1;
55             for(int i=r-1;i>=0;i--)
56             {
57                 a[i]=mt[i][n];
58                 for(int j=i+1;j<n;j++)
59                     if(mt[i][j]) a[i]^=a[j];
60             }
61             int c=0;
62             for(int i=0;i<n;i++) c+=a[i];
63             ans=min(ans,c);
64         }
65         printf("%dn",ans);
66     }
67     return 0;
68 }

原文链接: https://www.cnblogs.com/yangcl/archive/2013/01/17/2865022.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍