hdu4759 Poker Shuffle 2013 ACM/ICPC Asia Regional Changchun Online

找了很久的规律，只看十进制数字，各种乱七八糟的规律=没规律！
看了别人的解题报告，虽然看懂了，可是怎么发现的这个规律呢T.T~想了很久很久~

以下是转载的别人的图，自己再画太麻烦了~
全部看出0~2^n-1-1，下标从0开始！！！

每次洗牌的时候，奇数在后偶数在前时，只需循环右移一下，如下：
0(000) -->0(000) -->0(000) -->0(000)
1(001) -->4(100) -->2(010) -->1(001)
2(010) -->1(001) -->4(100) -->2(010)
3(011) -->5(101) -->6(110) -->3(011)
4(100) -->2(010) -->1(001) -->4(100)
5(101) -->6(110) -->3(011) -->5(101)
6(110) -->3(011) -->5(101) -->6(110)
7(111) -->7(111) -->7(111) -->7(111)

每一列就是一种情况，前一列就是洗牌之后的情况，发现二进制的规律。

奇数在前偶数在后时，只需右移一下，高位亦或1，如下（从右向左看）：
000(0) -> 100(4) -> 110(6) -> 111(7) -> 011(3) -> 001(1) -> 000(0)
001(1) -> 000(0) -> 100(4) -> 110(6) -> 111(7) -> 011(3) -> 001(1)
010(2) -> 101(5) -> 010(2) -> 101(5) -> 010(2) -> 101(5) -> 010(2)
011(3) -> 001(1) -> 000(0) -> 100(4) -> 110(6) -> 111(7) -> 011(3)
100(4) -> 110(6) -> 111(7) -> 011(3) -> 001(1) -> 000(0) -> 100(4)
101(5) -> 010(2) -> 101(5) -> 010(2) -> 101(5) -> 010(2) -> 101(5)
110(6) -> 111(7) -> 011(3) -> 001(1) -> 000(0) -> 100(4) -> 110(6)
111(7) -> 011(3) -> 001(1) -> 000(0) -> 100(4) -> 110(6) -> 111(7)

每一列就是一种情况，前一列就是洗牌之后的情况，发现二进制的规律。

相当于奇数在前是高位异或1，偶数在前高位异或0，经过很多次移动之后，可能每一位了异或了一个1了，
也或许有的异或了，有的没异或，但是不管过程怎样，只要是异或，那么这些数字都得一起异或，即每一列
中的每一个数字都要异或这些，每两个任意的数字都是经过相同的变化得来的。
所以输入A, X, B, Y，执行A--;X--;B--;Y--;这些操作~
即A xor C = X；B xor C = Y，C就是整个移动的过程。交换律即A xor X = B xor Y = C
最后大数判断A xor X 与B xor Y是否相等即可。

 1 import java.math.*;
 2 import java.util.*;
 3 
 4 public class Main{
 5     static int n;
 6     static Scanner cin = new Scanner(System.in);
 7     
 8     static BigInteger rot(BigInteger x){
 9         BigInteger tmp = x.and(BigInteger.valueOf(1));
10         return x.shiftRight(1).or(tmp.shiftLeft(n-1));
11     }
12     
13     public static void main(String[] args){
14         int t = cin.nextInt(),    cases=0;
15         while(++cases <= t){
16             n = cin.nextInt();
17             BigInteger A = cin.nextBigInteger(),    X = cin.nextBigInteger();
18             BigInteger B = cin.nextBigInteger(),    Y = cin.nextBigInteger();
19             A = A.add(BigInteger.valueOf(-1));
20             B = B.add(BigInteger.valueOf(-1));
21             X = X.add(BigInteger.valueOf(-1));
22             Y = Y.add(BigInteger.valueOf(-1));
23             String ans = "No";
24             for(int i=0; i <= n; i++){
25                 A = rot(A);
26                 B = rot(B);
27                 BigInteger tmpx = A.xor(X);
28                 BigInteger tmpy = B.xor(Y);
29                 if(tmpx.compareTo(tmpy)==0){
30                     ans = "Yes";
31                     break;
32                 }
33             }
34             System.out.println("Case " + cases + ": " + ans);
35         }
36     }
37 }

View Code

hdu4759 Poker Shuffle 2013 ACM/ICPC Asia Regional Changchun Online

相关推荐