今天在mop上看到一个智力题：

有10个人站成一队，每个人头上都戴着一顶帽子，帽子的颜色或者是红的或者是黄的。

　　最后一个人能够看到前面9个人的帽子颜色，倒数第二个人能够看到前面8个人的帽子颜色，以此类推，第一个人什么也看不到。

　　现在让这10个人事先商量好一种策略之后从后往前报自己帽子的颜色，每个人只能说一次，并且只能说“红”或者“黄”。 (最后一个人) 10 9 8 7 6 5 4 3 2 1 (第一个人)

　　有一种策略，编号为偶数的人报前一个人的帽子颜色，编号为奇数的人将听到的颜色报出来，这样，至少有5个人报对了自己帽子的颜色。

　　问：采取什么样的策略能够让至少9个人报对自己帽子的颜色？

我的思路是这样的：

这些人可以看成0/1二进制。

第一个报的人，肯定不能保证自己的答案，因为没人给他证据。

最后一个报的人证据最多。

9个人最后报告的答案都是固定的，都必须是自己的颜色

所以说，只有第一个人的答案是灵活的。其它人需要根据自己看到的颜色，估计自己的颜色，然后把自己假设的颜色，带入策略中计算，看是否符合已经回答了的人的答案。

也就是说，这个策略的关键在于不能出现错误的猜测也可以满足已经回答了的人的答案。拿第二个报数的人说，它能够参考的已经回答了的人的答案只有一个，所以换句话说，这个策略要有唯一性

所以|和&操作就可以排除。剩下异或

那策略就是:

当第n号人报数的时候，先把前面所有的看到的n-1的事实求异或，然后假设自己一个答案。计算出的值带入前面10-n的回答中运算，看这些已经回答的答案跟本策略是否吻合。如果都吻合，答案就确定。如果不吻合，那猜测错误，答案取反。

根据这个策略验证了一下，可行。

接着看了一下标准答案:

每个人只能说【红】或者【黄】，，但是并不表示【红】或者【黄】就一定要表示帽子的颜色。。可以事先约定，，让【红】和【黄】表示别的意思。。

所以策略可以是这样：约定让10号（因为他能看到前面9个人）来说前面有几个人是戴黄帽子的。。戴黄帽子的人数是奇数就说【红】，，偶数就说【黄】。。这样，，9号就能根据自己看到的情况，，比较一下就知道自己是什么颜色的帽子。。比如10号说【红】，，9号看到奇数个黄帽子就知道自己是红帽子，，因为如果自己是黄帽子那10应该喊【黄】才对；而看到偶数个黄帽子就知道自己是黄帽子了。。

9号喊对了自己的帽子，，8号就可以根据前两人的信息和自己看到的帽子情况判断自己的帽子颜色了。。这样一个一个以此类推，，一直到1号报对为止。。

这样就能让至少9个人都报对自己的帽子了。。

ft, 这么简单阿。不过实质是一样的，因为异或运算就是计算奇偶的算法。同时发现，根本不用把假设的答案跟前面所有的回答对照，只需要对照前面一个回答就可以了。因为异或是唯一的。

所以，该题目其实还有进一步改进的余地，如何才能要用尽所有的答案才可以算出自己的答案呢？

下面是我以前发到vchelp一个我做过的题目。atc第一次招聘的paper test最有一个题目

请回答下面10个相关的问题：

1，第一个答案是B的问题是？
A) 2 B) 3 C)4 D) 5 E)6
2, 唯一的连续两个具有相同答案的是？
A) 2,3 B)3,4 C)4,5 D)5,6 E)6,7
3, 本问题答案和哪个问题答案相同？
A)1 B)2 C)4 D)7 E)6
4, 答案是A的问题的个数？
A)0 B)1 C)2 D)3 E)4
5, 本问题答案和哪个问题相同？
A)10 B)9 C)8 D)7 E)6
6, 答案是A的问题的个数和答案是什么的问题的个数相同？
A)B B)C C)D D)E E)以上都不是
7，按照字母顺序本问题的答案和下一个问题的答案相差几个字母？
A)4 B)3 C)2 D)1 E)0 注：A和B相差一个字母
8，答案是元音字母的问题的个数？
A)2 B)3 C)4 D)5 E)6 注: A和E是元音字母
9，答案是辅音字母的个数？
A)是一个质数 B)是一个阶乘数 C)是一个平方数 D)是一个立方数 E）是5的倍数
10，本问题的答案是：
A)A B)B C)C D)D E)E

题眼应该是第五题,观察第五题,发现从第六题道第十题在如下分布里面,必定由一个是正确的:
10-A 9-B 8-C 7-D 6-E
然后经过观察,发现7-D 8-C 9-A里面如果选择任意一个,那么着三个都可以被同时选择,所以这里至少是一个突破口
于是7,8,9三个题目的答案就确定下来了

如果能够做到这里,可以算成功了1/3.我做到这里花了十五分钟左右

然后我看到7,8,9确定下来了,剩下的最容易确定就是1,5这两个题目
第一题的A很好排除,这样就剩下6个题目没有确定,根据第一题的提示,表示后面肯定有一个题目的答案是B,同时在前面的8题说了,一共有四个元音字母,现在只出现了第9题的一个元音字母,也就是说在没有确定六个题目中有三个元音字母.同时看最后一个题目的题干,发现他是跟其他联系最少的一个,基本上是来凑数目的.同时结合前面的,发现两个东西是最需要凑的,一个就是元音字母和辅音字母的数目,还有一个就是答案是A的问题的个数,把这两个方在一起考虑,安么最后一个题目最有可能的就是选A!!
如果能够做到这里,成功就不远了.
剩下的事情就是还有两个e没有出现,同时不允许新的a出现,那么答案救显而易见了!


我当时判定了7,8,9三个题目后翻了个错误,我直接去做第五题,因为既然7,8,9做出来了,我以为第五题的BCD三个答案中肯定有一个是正确的.但是做了很久后发现行不通,才改变的思路

我觉得努力做还是很容易的,关键是要不怕意识到错误,发现自己好像做错了就不要坚持,换一个可能的答案继续做.主要是靠观察那些题目选项是正确的可能性大,然后就做假设推理.

不过可惜的是,我虽然把最难得题目做出来了,但是前面因为粗心错了两个很简单的题目,其中一个把链表反转..............
sigh