10.17T5 位运算+逐位推理

1947 -- 【模拟试题】编码

Description

　　DEX国刚刚截获了KCAJ国与AWAW国之间的S.Message 。D国S302情报机构情报员007 手里正拿着写有K国与A国之间Message的文件。“什么？！居然被加密了！！”007忍不住说道，“KCAJ，你会出路的！”
　　幸运的是K国与A国此次通讯时间远远超过了007所估计的30s，因此007又截获了大量的Message。通过对这些Message的研究，007发现了其中的秘密：
　　每一条S.Message原本由8个32-bit的正整数N1..N8组成，本来这8个整数可以由计算机直接破解得出相应的文字。但对于每条信息，K国与A国另外使用了不同的密钥M来再次加密。所谓“密钥”其实也是一个32-bit的整数，在传递讯息的时候，是将N1 Xor M、N2 Xor M、…、N8 Xor M、N9 Xor M这9个整数传给对方（其中N9为N1~N8这8个整数的和Mod 2^32）。
　　有了上面的发现，007马上意识到他可以破解出Message了！这实在是一个简单的工作，007决定让你——也就是他的助手来完成此工作。

Input

　　输入文件按顺序输入9个整数N1..N9。每个整数用16进制表示。

Output

　　输出仅一个数，即密钥M。同样用16进制表示。

Sample Input

3 4 4 7 7 b a 2 2e

Sample Output

6

Hint

【数据范围】
　40％的数据满足M<=500；
　100％的数据满足M<2^32；

 

 

 

出题意图：

    递推题几乎也是分区联赛的必考题，本题考察选手运用递推思想解题的能力。

简要解答：

    本题目的是求出M，换言之只要确定M转换成二进制后每一位是0还是1即可。

    首先我们把32-bit整数二进制位从低位到高位编号为第1位到第32位；

    设输入的9个整数为A[1]..A[9]，即A[1]=N1 Xor M，A[2]=N2 Xor M……A[9]=N9 Xor M；

    A[i,j]＝0或1，表示A[i]转化为2进制后第j位上的数字,  之后类似做竖式加法.  那么如何递推呢？从低位到高位，显然，低位一确定即不会改变。

    显然我们需要枚举M的第i位数字是0还是1：

设M的第i位数字是0：

在确定第i位之前，M的前i-1位已确定，即前i-1位已正确验证。我们设M的i位数字是0，对所A1到A8与设定的M异或并取出前i位求和得到原始值的前i位累加和，如果该和的前i位与A9对M异或并取出的前i位相等，好么等式成立，M第i位为0,继续递推，否则，第i位为1并修改M。

最后输出m即可.

说人话就是推第i位时候，如果m此时是0则这一位什么数字都不会变，我们就把上一个m拿来加一下，如果前i位是相同的就是0，反之就是1

code:

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    unsigned int a[10],m=0,mask=0;
    for(int i=1;i<=9;i++)scanf("%x",&a[i]);
    for(int i=0;i<32;i++){
        int sum=0;
        mask+=(1<<i);
        for(int j=1;j<=8;j++){
            sum+=((a[j]^m)&mask);
        }
        if((sum&mask)!=((a[9]^m)&mask))
            m+=(1<<i);
    }
    printf("%x",m);
    return 0;
}

over