hdu4759 Poker Shuffle 法则题

hdu4759 Poker Shuffle 规律题

思路：把所有标号减1，这里要从二进制的角度来找规律，我们先考虑把单数牌放到最前面的情况。注意我们之后讨论的都是减1后的。

我们观察每个数值i在洗牌以后位置的变化

数值 0 1 10 11 100 101 110 111
位置1: 0 1 10 11 100 101 110 111
位置2(偶数在前): 0 100 1 101 10 110 11 111
位置2(奇数在前): 100 0 101 1 110 10 111 11

我们可以发现做完(偶数在前)操作时，每个数的位置的数值是跟操作之前的位置的数值是同构的，现在有(奇数在前)的操作，我们进一步发现，

选择任意两个数值x，y，把它们的位置的数值抑或以后的值val与操作之前的这个数值也是同构的。

问题变为判操作后的val与原先的val是否同构。

import java.io.*;
import java.util.*;
import java.math.*;
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int cas = in.nextInt();
        BigInteger one = BigInteger.ONE;
        BigInteger a, b, x, y;
        int n;
        for(int ca = 1; ca <= cas; ca++) {
            n = in.nextInt();
            a = in.nextBigInteger().subtract(one);
            x = in.nextBigInteger().subtract(one);
            b = in.nextBigInteger().subtract(one);
            y = in.nextBigInteger().subtract(one);
            boolean ok = false;
            BigInteger bit = BigInteger.valueOf(1).shiftLeft(n-1);
            a = a.xor(b);
            x = x.xor(y);
            for(int i = 0; i < n; i++) {
                if(a.equals(x) == true) {
                    ok = true;
                    break;
                }
                boolean t = a.testBit(0);
                a = a.shiftRight(1);
                if(t == true) a = a.xor(bit);
            }
            System.out.print("Case "+ca+": ");
            if(ok == true) 
                System.out.println("Yes");
            else 
                System.out.println("No");
        }
    }
}

hdu4759 Poker Shuffle 法则题

相关推荐