2005-07-31 19:53| 
12 Comments | 本文内容遵从Problem
小卡卡继续着他的Pascal圣地之行。他来到了Pascal农场主John的家里，向他探询关于Pascal圣地宝藏的事。
John答应小卡卡愿意把他所知道的一切告诉小卡卡，但是John有一个要求，那就是希望小卡卡帮助他找出他走丢的一头奶牛。
John的奶牛都是由1-2^k编号的，但是John在放牛的时候无意中弄丢了一头奶牛。他希望小卡卡告诉他，他走丢的奶牛的编号是多少。
Input
该题含有多组测试数据。
每组测试数据第一行一个整数k表示奶牛的数目为2^k（1<=k<=20）。
第二行到第2^k行每行一个整数表示还在农场的一头奶牛的编号（并不是按顺序给出的）。
Output
输出走丢的奶牛的编号
Sample Input
2
4
1
3
Sample Output
2
问题就是这样了。怎么办？cow:array[1..1048576]of boolean;？一个一个查找比较？
最终，解决办法还是被我找到了，一个出乎意料的算法：把读入的数全加起来，然后用公式算从一加到2^k的和，用它来减读入的数的和显然就是差的那个数了。
呵呵，很不寻常吧。这应该归为什么算法呢？
12 条回复
您也随便说几句吧：
正常。
数学算法。。
回复：2年前的我真弱啊
呵呵，慢慢长大啊。
这道题冒似是故意让编程的人走弯路的：）正常人比较容易想，哈。
ms我当年还是靠sqrt(n)的空间弄的~
进制问题吧
大牛的成长历程。。。。。
ps这是安徽的省选题吗？每年考试都是卡卡、可可、Samul星球之类的。
我有一道类似的题目：有个大学有两个人私奔，校长让全校学生签到，现在给出大学原有的学生数N，还有签到的人的编号，求私奔的两个人的编号。N<=100000.
这题貌似很简单，但是空间限制1K。我没有打错，就是1K。程序都比1K长。
回复：求两个人的和与平方和，然后解方程组
那个1k是人为计算出来的，不是实际意义上的
有个魔术就是利用这种原理：54张牌取走一张，然后翻两次（一次个位求和，一次8张死记）找出是哪一张。
本人决定从大牛的第一篇文章学起.先向大牛打声招呼~~
我很早就想出来过这个算法。
其实用位异或更快，搞一个变量赋0，每输入一个就异或一下，最后这个变量就是那个数。
一点儿不弱吧...
看来 我离 大牛的 哺乳期 都还很远.....
顺便 问下
你 这时候 有多老..
希望 不要听到是 初中...
或者 更小..
一个个的算xor可以么？