Poker Shuffle
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 95 Accepted Submission(s): 24
Jason is not only an ACMer, but also a poker nerd. He is able to do a perfect shuffle. In a perfect shuffle, the deck containing K cards, where K is an even number, is split into equal halves of K/2 cards which are then pushed together in a certain way so as to make them perfectly interweave. Suppose the order of the cards is (1, 2, 3, 4, …, K-3, K-2, K-1, K). After a perfect shuffle, the order of the cards will be (1, 3, …, K-3, K-1, 2, 4, …, K-2, K) or (2, 4, …, K-2, K, 1, 3, …, K-3, K-1).
Suppose K=2^N and the order of the cards is (1, 2, 3, …, K-2, K-1, K) in the beginning, is it possible that the A-th card is X and the B-th card is Y after several perfect shuffles?
Input to this problem will begin with a line containing a single integer T indicating the number of datasets.
Each case contains five integer, N, A, X, B, Y. 1 <= N <= 1000, 1 <= A, B, X, Y <= 2^N.
For each input case, output “Yes” if it is possible that the A-th card is X and the B-th card is Y after several perfect shuffles, otherwise “No”.
3 1 1 1 2 2 2 1 2 4 3 2 1 1 4 2
Case 1: Yes Case 2: Yes Case 3: No
题目意思很简单。
就是洗牌，抽出奇数和偶数，要么奇数放前面，要么偶数放前面。
总共2^N张牌。
需要问的是，给了A X B Y 问经过若干洗牌后，第A个位置是X，第B个位置是Y 是不是可能的。
题目给的牌编号是1开始的，先转换成0开始。
一开始位置是0~2^N-1. 对应的牌是0~2^N-1
首先来看每次洗牌的过程。
对于第一种洗牌：将奇数放前面，偶数放后面。其实每个位置数的变化就是相当于循环右移一位，然后高位异或1.
对于第二种洗牌：讲偶数放前面，奇数放后面。其实每个位置数的变化就是相当于循环右移一位，然后高位异或0.
所以经过若干次洗牌，可以看成是循环右移了K位，然后异或上一个数。
所以对于题目的查询：
首先将A X B Y都减一。 然后枚举X,Y循环右移了K位以后，能不能同时异或上相同的数得到A,B
需要大数，然后转化成二进制就可以解决了。
循环右移X,Y，然后判断A ^ X 是不是等于 B ^ Y
1 /* *********************************************** 2 Author :kuangbin 3 Created Time :2013/9/28 星期六 11:57:13 4 File Name :2013长春网络赛\1001.cpp 5 ************************************************ */ 6 7 #pragma comment(linker, "/STACK:1024000000,1024000000") 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include
再贴一下JAVA的程序。
JAVA写大数很方便啊。。。。
1 import java.io.*; 2 import java.util.*; 3 import java.math.*; 4 public class Main { 5 6 public static void main(String args[]) 7 { 8 int T; 9 int iCase = 0;10 int n;11 BigInteger A,X,B,Y;12 int []a = new int[1010];13 int []x = new int[1010];14 int []b = new int[1010];15 int []y = new int[1010];16 Scanner cin = new Scanner(System.in);17 T = cin.nextInt();18 while(T > 0)19 {20 iCase++;21 n = cin.nextInt();22 A = cin.nextBigInteger();23 X = cin.nextBigInteger();24 B = cin.nextBigInteger();25 Y = cin.nextBigInteger();26 A = A.subtract(BigInteger.ONE);27 X = X.subtract(BigInteger.ONE);28 B = B.subtract(BigInteger.ONE);29 Y = Y.subtract(BigInteger.ONE);30 for(int i = 0;i < n;i++)31 {32 a[i] = A.mod(BigInteger.valueOf(2)).intValue();33 b[i] = B.mod(BigInteger.valueOf(2)).intValue();34 x[i] = X.mod(BigInteger.valueOf(2)).intValue();35 y[i] = Y.mod(BigInteger.valueOf(2)).intValue();36 A = A.divide(BigInteger.valueOf(2));37 B = B.divide(BigInteger.valueOf(2));38 X = X.divide(BigInteger.valueOf(2));39 Y = Y.divide(BigInteger.valueOf(2));40 //System.out.println(a[i]+" "+ x[i]+" "+ b[i]+" "+y[i]);41 }42 boolean flag = false;43 for(int k = 0;k <= n;k++)44 {45 x[n] = x[0];46 for(int i = 0;i < n;i++)x[i] = x[i+1];47 y[n] = y[0];48 for(int i = 0;i < n;i++)y[i] = y[i+1];49 boolean ff = true;50 for(int i = 0;i < n;i++)51 if((x[i]^a[i]) != (y[i]^b[i]))52 {53 ff = false;54 break;55 }56 if(ff)57 {58 flag = true;59 break;60 }61 }62 if(flag)System.out.println("Case "+iCase+": Yes");63 else System.out.println("Case "+iCase+": No");64 T--;65 }66 }67 68 }