【编码】

题目描述

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 232)。

有了上面的发现,007马上意识到他可以破解出Message了!这实在是一个简单的工作,007决定让你——也就是他的助手来完成此工作。

(提示:xor 是位运算的“异或”运算,C语言中用“^”表示,运算规则:不同则1,相同为0。)

输入格式

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

输出格式

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

样例数据 1

输入

3 4 4 7 7 b a 2 2e

输出

6

备注

【数据范围】
40%的数据满足:M<=500;
100%的数据满足:M<232

一道蛋疼的进制转换问题,考场的时候不知道怎么写写了个暴力30分……(说好的40%数据呢╭(╯^╰)╮)晚上回家仔细想了想发现其实不难写。

其实要求M只需要求出M(二进制下)每一位就行了,而且明显第i位不是0就是1,所以我就枚举是0的情况,如果不是自然就是1了。首先定义一个二维数组F[i][j]表示第i个数第j位(二进制下)是0还是1,然后定义一个数组step处理到第i位的进位,既然题目给的是Xor后的数,我们就Xor回去(在假设M[i]=0)的情况下,然后把总和sum加上step,再mod 2看第i位处理下来是0还是1,如果处理下来和第9个数一样,那M[i]=0成立否则M[i]=1,至于进位,如果成立的话直接用sum/2就是下一位的进位,如果不成立的话那么说明应该统计一次完全相反的情况,即Xor 1的情况,但不用这么麻烦,既然已经统计过Xor 0的情况了,那么8-Xor 0的情况就是Xor 1的情况了,但是sum已经加了个进位的step所以还要减掉它,最后再加上进位的step再除以2就是下一位的进位情况了……说着很绕看代码吧:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*