2013
12-30

# Bridged Marble Rings

26 marbles―half yellow and half gray―are distributed between two circles of 13 marbles each. The marbles in each circle can be freely rotated clockwise or counterclockwise. The upper and lower circles are bridged by a smaller circle, which rotates―in the plane of the board―180 degrees, effectively exchanging the three bottommost marbles of the upper circle with the three uppermost marbles of the lower one. The goal is to get all gray marbles to the upper circle and all yellow marbles to the lower one while minimizing the number of times the bridging circle is rotated.

The input is a series of lines, where each line describes an initial board configuration. Each line is a permutation of 13 y’s and 13 g’s. The first half of the line describes the clockwise configuration of the upper circle, and the rest of the line describes the clockwise configuration of the lower one. Of course, each y corresponds to a yellow marble, and each g corresponds to a gray one.

The input file will include multiple test cases. Each test case consists of a single line containing some permutation of the string y13g13. All lines (including the last one) are terminated with a newline. The newline immediately follows the last letter on the line.

The input is a series of lines, where each line describes an initial board configuration. Each line is a permutation of 13 y’s and 13 g’s. The first half of the line describes the clockwise configuration of the upper circle, and the rest of the line describes the clockwise configuration of the lower one. Of course, each y corresponds to a yellow marble, and each g corresponds to a gray one.

The input file will include multiple test cases. Each test case consists of a single line containing some permutation of the string y13g13. All lines (including the last one) are terminated with a newline. The newline immediately follows the last letter on the line.

gggggggggggggyyyyyyyyyyyyy
yyyyyggggggggyyyygggggyyyy
gyyygyggyyygyyggyyggggyygg
ygygygygygygygygygygygygyg

0
2
5
6

1 = 二进制01
2 = 二进制10
3 = 二进制11  XOR
———————
0 = 二进制00 (注意不进位)

a ^ b ^ (a ^ b)=(a ^ a) ^ (b ^ b) = 0 ^ 0 = 0。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
using namespace std;
int num[200024];
int main(  )
{
int n;
while( scanf( "%d" ,&n ),n )
{
int x = 0;
for( int i = 0 ; i < n ; i ++ )
{
scanf( "%d",&num[i] );
x ^= num[i];
}
if( x == 0 ) printf( "No\n" );
else
{
printf( "Yes\n" );
for( int i = 0; i < n; i ++ )
{
int t = x ^ num[i];
if( t <= num[i] )
{
printf( "%d %d\n",num[i] , t );
}
}
}
}
//system( "pause" );
return 0;
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。