A

题目链接：https://vjudge.net/contest/276374#problem/A

题目大意：给你20个杯子，每一次操作，假设当前是对第i个位置进行操作，那么第i个位置，第i+1个位置，第i-1个位置的盘子都会翻转，第一个和最后一个例外（只有两个）。然后问你最少的操作数能够使得盘子全部变成反着的（0代表反，1代表正）。

bfs的做法：

具体思路：bfs，注意起点为0个操作的情况，然后逐步的去找满足题目条件的最优步数。如果是起点是初始状态，然后去找全部都是翻转的情况，这样的话会mle，因为递归层数会明显的比第一种的多。

AC代码：

 1 #include<iostream>
 2 #include<stack>
 3 #include<cstring>
 4 #include<iomanip>
 5 #include<stdio.h>
 6 #include<algorithm>
 7 #include<cmath>
 8 #include<queue>
 9 using namespace std;
10 # define ll long long
11 # define inf 1ll<<60
12 const int mod = 21252;
13 const int maxn = 1<<23;
14 struct node
15 {
16     int num;
17     int step;
18     node() {}
19     node(int xx,int yy)
20     {
21         num=xx,step=yy;
22     }
23 }q[maxn];
24 int vis[maxn];
25 bool check(int t)
26 {
27     for(int i=0; i<20; i++)
28     {
29         if((1<<i)&t)
30             return false;
31     }
32     return true;
33 }
34 int bfs(int t)
35 {
36     int pre=0,last=0;
37     q[last++]=(node(t,0));
38     while(pre<last)
39     {
40         node top=q[pre++];
41         if(check(top.num))
42             return top.step;
43         for(int i=0; i<20; i++)
44         {
45             int tmp=top.num;
46             if(!(tmp&(1<<i)))continue;
47             if(i==0)
48             {
49                 tmp^=(1<<0);
50                 tmp^=(1<<1);
51             }
52             else if(i==19)
53             {
54                 tmp^=(1<<19);
55                 tmp^=(1<<18);
56             }
57             else
58             {
59                 tmp^=(1<<i);
60                 tmp^=(1<<(i-1));
61                 tmp^=(1<<(i+1));
62             }
63             if(vis[tmp])
64                 continue;
65                 q[last++]=node(tmp,top.step+1);
66         }
67     }
68     return false;
69 }
70 int main()
71 {
72     //freopen("data1.out","r",stdin);
73     int s=0,tmp;
74     for(int i=0; i<20; i++)
75     {
76         scanf("%d",&tmp);
77         if(tmp)
78         s|=(1<<i);
79     }
80     int ans=bfs(s);
81     printf("%d
",ans);
82     return 0;
83 }

高斯消元的方法：

就是构建20个方程，每一个方程的构建就和题目中的一样，最后得出的所有x的解就是最终答案。

AC代码：

  1 #include<iostream>
  2 #include<stack>
  3 #include<cstring>
  4 #include<iomanip>
  5 #include<stdio.h>
  6 #include<algorithm>
  7 #include<cmath>
  8 #include<queue>
  9 using namespace std;
 10 # define ll long long
 11 # define inf 0x3f3f3f3f
 12 const int mod = 21252;
 13 const int maxn = 40;
 14 int a[maxn][maxn];
 15 int equ,var;
 16 int b[maxn][maxn];
 17 int x[maxn];
 18 int free_x[maxn];
 19 int free_num;
 20 int Gass()
 21 {
 22     int max_r,col,k;
 23     free_num=0;
 24     for(k=0,col=0; k<equ&&col<var; k++,col++)
 25     {
 26         max_r=k;
 27         for(int i=k+1; i<equ; i++)
 28         {
 29             if(abs(a[i][col])>abs(a[max_r][col]))
 30                 max_r=i;
 31         }
 32         if(a[max_r][col]==0)
 33         {
 34             k--;
 35             free_x[free_num++]=col;
 36             continue;
 37         }
 38         if(max_r!=k)
 39         {
 40             for(int j=col; j<var+1; j++)
 41                 swap(a[k][j],a[max_r][j]);
 42         }
 43         for(int i=k+1; i<equ; i++)
 44         {
 45             if(a[i][col]!=0)
 46             {
 47                 for(int j=col; j<var+1; j++)
 48                     a[i][j]^=a[k][j];
 49             }
 50         }
 51     }
 52     for(int i=k; i<equ; i++)
 53         if(a[i][col]!=0)
 54         {
 55             return -1;
 56         }
 57     if(k<var)
 58         return var-k;
 59     for(int i=var-1; i>=0; i--)
 60     {
 61         x[i]=a[i][var];
 62         for(int j=i+1; j<var; j++)
 63             x[i]^=(a[i][j]&&x[j]);
 64     }
 65     return 0;
 66 }
 67 int n;
 68 void init()
 69 {
 70     memset(x,0,sizeof(x));
 71     memset(a,0,sizeof(a));
 72     equ=20;
 73     var=20;
 74     for(int i=0; i<20; i++)
 75     {
 76         a[i][i]=1;
 77         if(i>0)
 78             a[i-1][i]=1;
 79         if(i<20-1)
 80             a[i+1][i]=1;
 81     }
 82 }
 83 int solve()
 84 {
 85     int t=Gass();
 86     if(t==-1)
 87     {
 88         return t;
 89     }
 90     else if(t==0)
 91     {
 92         int  ans=0;
 93         for(int i=0; i<n*n; i++)
 94             ans+=x[i];
 95         return ans;
 96     }
 97     else
 98     {
 99         int ans=inf;
100         int tot=(1<<t);
101         for(int i=0; i<tot; i++)
102         {
103             int cnt=0;
104             for(int j=0; j<t; j++)
105             {
106                 if(i&(1<<j))
107                 {
108                     cnt++;
109                     x[free_x[j]]=1;
110                 }
111                 else
112                 {
113                     x[free_x[j]]=0;
114                 }
115             }
116             for(int j=var-t-1; j>=0; j--)
117             {
118                 int dex;
119                 for(dex=j; dex<var; dex++)
120                     if(a[j][dex])
121                         break;
122                 x[dex]=a[j][var];
123                 for(int l=dex+1; l<var; l++)
124                 {
125                     if(a[j][l])
126                         x[dex]^=x[l];
127                 }
128                 cnt+=x[dex];
129             }
130             ans=min(ans,cnt);
131         }
132         return ans;
133     }
134 }
135 int main()
136 {
137   // freopen("hqx.txt","r",stdin);
138     init();
139     int tmp;
140     for(int i=0; i<20; i++)
141     {
142         scanf("%d",&tmp);
143         a[i][20]=tmp;
144     }
145     int t=solve();
146     printf("%d
",t);
147     return 0;
148 }