刷墻

發布時間: 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 */

總結

以上是生活随笔為你收集整理的2017西安交大ACM小学期 刷墙[折半枚举+异或]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。