热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

2013长春网赛1001hdu4759PokerShuffle

题目链接:http:acm.hdu.edu.cnshowproblem.php?pid4759题意:有一堆2^n的牌,牌原先按(1,2,.k)排序,每一次洗牌都将牌分成两种情况:(1

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4759

题意:有一堆2^n的牌,牌原先按(1,2,....k)排序,每一次洗牌都将牌分成两种情况:(1,3,5,....k-1)或(2,4,6,.....k),

给出四个数:A  X  B  Y  ,问有没有可能出现A位置的牌序号为X,B位置的牌序号是Y。输出Yes或No。

1 <= N <= 1000, 1 <= A, B, X, Y <= 2^N.

分析:二进制的运用。

题目给的牌编号是从一开始的,要先将其转成从0开始的。

一开始的编号是0~2^N-1,每次洗牌的过程如下:

第一种洗牌:将奇数放前面,偶数放后面。每个位置的数的变化相当于二进制数右移一位(相当于除以2),然后最高位异或1。

第二种洗牌:将偶数放前面,奇数放后面。每个位置的数的变化相当于二进制数右移一位(相当于除以2),然后最高位异或0。

这样就把位置为i的牌,经过一次洗牌后的位置算出来了。

例如:      牌:   0     1    2    3    4    5     6     7                       0     1      2     3      4      5     6     7 

            位置:   0     1    2    3    4    5     6     7        变成          4     0      5     1      6      2     7     3

         二进制: 000 001 010 011 100 101 110 111                   100  000  101  001  110  010  111  011

上面的是第一种洗牌方式,可以看出奇数在前,偶数在后。

下面是第一种洗牌的规律:

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)

可以看出,经过若按同一种洗牌方式,经过2*n次洗牌后,牌堆会恢复到原来的序列。

但是题目有两种洗牌方式,是反过来的,所以只要经过n次洗牌后就会恢复原来的序列了。

也就是说对于一堆2^n的牌,最多只有n种不同的序列,也就是最多右移n位,超过n位就会重复了。

 

经过若干次洗牌,可以看成是右移了k位,然后异或上一个数。

所以首先将A X B Y都减一,然后枚举X,Y右移k位以后,能不能同时异或上相同的数得到A,B。

由于a^b=c,可以得到a^c=b

解法总结如下:

从1到n枚举右移X,Y,每次判断X^A是否等于Y^B。

n比较大,要用大数。

用java大数来处理比较方便。

AC 代码:

 1 import java.io.*;
 2 import java.util.*;
 3 import java.math.*;
 4 public class Main {
 5     static int n;
 6     public static BigInteger right(BigInteger a)     //循环移位
 7     {
 8         BigInteger tmp=a.and(BigInteger.ONE);       //取出最低位作为右移后的首位
 9         return a.shiftRight(1).or(tmp.shiftLeft(n-1));    //将最低位加到最高位上
10     }
11     public static void main(String[] args) {
12         int i,t,k,flag;
13         BigInteger A,B,X,Y,a,b;
14         Scanner cin=new Scanner(System.in);
15         t=cin.nextInt();
16         for(i=1;i<=t;i++)
17         {
18             n=cin.nextInt();
19             A=cin.nextBigInteger();
20             X=cin.nextBigInteger();
21             B=cin.nextBigInteger();
22             Y=cin.nextBigInteger();
23             
24             A=A.add(BigInteger.valueOf(-1));   //从0开始
25             X=X.add(BigInteger.valueOf(-1));
26             B=B.add(BigInteger.valueOf(-1));
27             Y=Y.add(BigInteger.valueOf(-1));
28             
29             flag=0;
30             for(k=1;k<=n;k++)
31             {
32                 X=right(X);
33                 Y=right(Y);
34                 a=X.xor(A);
35                 b=Y.xor(B);
36                 if(a.equals(b))
37                 {
38                     flag=1;
39                     break;
40                 }
41             }
42             if(flag==1)
43                 System.out.println("Case "+i+": Yes");
44             else
45                 System.out.println("Case "+i+": No");
46         }
47     }
48 
49 }
View Code

 

 


推荐阅读
author-avatar
W_庆祥
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有