发布时间: 2017年7月3日 12:17 最后更新: 2017年7月6日 22:29 时间限制: 3000ms 内存限制: 128M
描述小明有一面黑白混搭的墙，他想给把墙重新粉刷一遍。他将任务分给了xx粉刷匠，但是xx粉刷匠提出要求，他要根据原来墙的颜色进行粉刷，将白色墙刷成黑色，将黑色墙刷成白色。小明不高兴了，他给了粉刷匠一个奇怪的刷子，并且要求墙的每部分只能操作一次（不包括由于刷子原因被粉刷），问最后粉刷匠可以有多少种把墙刷完的方案，如果不能完成目标，输出poor plasterer
输入第一行一个数字T(T<=1000)表示组数据 每组数据： 第一行一个数N（0<N<30）表示墙的长度 第二行有N个字母，第i个字母表示第i米墙的颜色 （w：白色，b：黑色） 第三行表示小明想得到的最后状态 第四行一个数M表示要求数 接下来M(M<=100)行，每行两个数 A, B ，表示在粉刷第A米时，由于奇怪的刷子第B米也会被粉刷成与原来相反的颜色
输出输出对应的答案
样例输入1 复制 2 3 w w w b b b 6 1 2 1 3 2 1 2 3 3 1 3 2 3 w w w b w b 2 1 2 2 1 样例输出1 4 poor plasterer AC代码： #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; int N,M; int sta,tar; const int MAX = 2e6; int rules[35]; int s1[MAX]; int s2[MAX]; int cnt1; int cnt2; void make(int s[],int& cnt,int l,int r){ int n = r - l + 1; for(int S = 0;S < (1<<n);S++){ int tmp = 0; for(int i = 0;i < n;i++){ if( (S>>i) & 1){ int op = l + i + 1; tmp ^= rules[op]; } } s[cnt++] = tmp; } } int read(){ int res = 0; for(int i = 0;i < N;i++){ char c; scanf(" %c",&c); if(c == 'b'){ res |= (1<<i); } } return res; } int main(){ int T;scanf("%d",&T); while(T--){ cnt1 = cnt2 = 0; //memset(cnts,0,sizeof(cnts)); sta = tar = 0; scanf("%d",&N); sta = read(); tar = read(); for(int i = 1;i <= N;i++){ rules[i] = 0; rules[i] ^= (1<<(i-1)); } scanf("%d",&M); for(int i = 0;i < M;i++){ int a,b; scanf("%d%d",&a,&b); rules[a] ^= (1<<(b-1)); } int l = N / 2; make(s1,cnt1,0,l-1); make(s2,cnt2,l,N-1); sort(s2,s2+cnt2); int ans = 0; for(int i = 0;i < cnt1;i++){ int tt = s1[i] ^ tar ^ sta; int res = upper_bound(s2,s2+cnt2,tt) - lower_bound(s2,s2+cnt2,tt); ans += res; } if(ans){ printf("%d\n",ans); } else{ puts("poor plasterer"); } } return 0; } /* 1 3 w w w w w b 0 */
