给定20个桶的状态，可以翻转桶把相邻的状态变换。问最少的变换次数。
此类问题通常有以下解决方案 1.暴力枚举 2.高斯消元 + 暴力枚举 3.找规律性质
这题和上一题POJ1830 很相似，可以用高斯消元异或方程组枚举自由元做。 但是比较麻烦；
注意到每个桶至多翻转一次。 从右往左的第一个1必然要通过 i+1号翻转来实现，因此可以O（n） 贪心 解决。
当然要考虑边界，这里可以加一个虚拟的0号桶。
#pragma warning(disable:4996) #include<iostream> #include<algorithm> #include<bitset> #include<tuple> #include<unordered_map> #include<fstream> #include<iomanip> #include<string> #include<cmath> #include<cstring> #include<vector> #include<map> #include<set> #include<list> #include<queue> #include<stack> #include<sstream> #include<cstdio> #include<ctime> #include<cstdlib> #define INF 0x3f3f3f3f #define inf 0x7FFFFFFF #define MOD 998244353 #define moD 1000000003 #define pii pair<int,int> #define eps 1e-8 #define equals(a,b) (fabs(a-b)<eps) #define bug puts("bug") #define re register #define fi first #define se second const int maxn = 100; const double Inf = 10000.0; const double PI = acos(-1.0); typedef long long ll; typedef unsigned long long ull; using namespace std; int dir[25]; int dirr[25]; int solve(int sta,int *dir) { dir[0] = sta; int res = 0; for (int i = 0; i <= 19; i++) { if (dir[i] == 1) dir[i] = 0, dir[i + 1] ^= 1, dir[i + 2] ^= 1, res++; } return res; } int main() { for (int i = 1; i <= 20; i++) scanf("%d", &dir[i]); for (int i = 1; i <= 20; i++) dirr[i] = dir[i]; printf("%d ", min(solve(0, dir), solve(1, dirr))); }