Flip and Shift

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,acm1063,Flip and Shift,1,题目叙述,This puzzle consists of a random sequence of m black disks and n white disks on an oval-shaped track, with a turnstile capable of flipping (i.e., reversing) three consecutive disks. In Figure 1, there are 8 black disks and 10 white disks on the track. You may spin the turnstile to flip the three disks in it or shift one position clockwise for each of the disks on the track .,2,The goal of this puzzle is to gather the disks of the same color in adjacent positions using flips and shifts.,You are to write a program which decides whether a given sequence can reach a goal or not. If a goal is reachable, then write a message YES; otherwise, write a message NO.,3,InputThe input consists of T test cases. And T is given in the first line of the input file. Each of the next T lines gives a test case. A test case consists of an integer, representing the sum of m and n, and a sequence of m+n 0s and 1s, representing an initial sequence. A 0 denotes a white disk and a 1 denotes a black disk. The sum of m and n is at least 10 and does not exceed 30. There is a space between numbers.,OutputThe output should print either YES or NO for each test case, one per line,Sample Input2,18 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1,14 1 1 0 0 1 1 1 0 0 1 1 0 1 0,Sample OutputYES,NO,4,分析可进行的操作,Flip:能使第i位的盘子和第k（k与i有相同的奇偶性）位的盘子交换,Shift:使任意位置的盘子地位相同;并且可使奇数(偶数)位上的任意两个盘子位置交换,从而使其形成任意一种全排列形式.,由于每个盘子地位相同,但又需要定出奇偶数位置,不妨将盘子按输入的顺序排位数.不过需要注意由此带来的一些问题.,5,从而我们想到将偶数位和奇数位的盘子分开来考虑.,(此处配合黑板讲题),大体思路是:在奇(偶)数位形成的圈1(2)内部进行位置变换,使其达到黑白盘分列的状态;,然后再将两圈相互交叉融合,由于要交叉融合,则须考虑圈1(2)的元素个数N1,N2,可能的情况只有两种:,6,情况一:N1=N2+1,此时可知共有奇数个盘子,由第一位和最后一位相邻且可互换,及每个盘子地位相等可知,任意两个相邻的盘子可互换,从而整体可达到任意一种全排列的形式,故此时必能达到所求状态,该情况下，易犯错误为直接由所输入的盘子个数的奇偶性判断并输出，而不进行输入操作,小提问:5 0 1 0 1 0.,7,情况二：,此时，将内部分好序的两圈交融时，（不妨取白盘子作为说明）要使得两圈中的白盘子相连不能有黑盘子的介入则必有,白,白,，或者,白,白,，或者,白,白,（配合黑板讲题）,此时应特别注意盘子的地位是相同的,此步易犯错误：,交叉时未考虑到,白,白,的情况,8,代码,void main(),int T,n,m,i=0,j,nn,disk30;,scanf(%d,while(iT),m=0; n=0;,scanf(%d,for(j = 0 ; jnn;j+),scanf(%d,if(j%2=1 ,else if(j%2=0 ,if(nn%2=1)printf(YESn);,else,if( n=m-1 | n=m | n=m+1 )printf(YESn);,else printf(NOn);,i+;,9,科学研究发现:在听完解题报告后带着愉悦的心情用力鼓掌有助于身体健康,大家不妨试一试,Thank you,10,