1. 给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
2. 给你n个数，其中有且仅有两个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。
1. 从头到尾异或一遍，最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑到异或运算满足交换律，先异或和后异或都是一样的，因此这个算法显然正确。
2. 从头到尾异或一遍，你就得到了需要求的两个数异或后的值。这两个数显然不相等，异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位，然后把所有这n个数分成两类，在那一位上是0的分成一类，在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。
题目来源：http://groups.google.com/group/pongba/browse_frm/thread/f4a080edbe3ce0e1
三个人坐成一个圆圈，每个人头上戴着一顶黑色的或者白色的帽子。每个人都只能看到另外两个人头上的帽子颜色。现在，他们需要独立地猜测自己头上的帽子颜色。每个人都需要在自己的小纸条上写下“黑色”、“白色”或者“放弃”。如果说至少一个人猜对，并且没有人猜错，那他们就获胜了；只要有任何一个人猜错，或者所有人都写的“放弃”，那么他们就输了。如果在游戏开始前他们能够商量一个策略，那么最好的策略是什么？
仔细想一下你会发现，要想保证他们百分之百地获胜是不可能的，因为游戏中大家不能交流信息，谁也不能保证自己能猜对。但是，有一种策略能保证他们有75%的几率获胜。事实上，当人数n=2^k-1时，我们有一种方法可以让获胜的概率达到(2^k-1)/(2^k)。你能想到这种策略吗？
设身处地地想，你会想到一个很自然的策略：如果一个人看到另外两个人的帽子颜色一黑一白，那这个人就放弃（换了你你也不敢猜）；如果另外两个人的帽子颜色一样，那你就猜相反的颜色（概率上看也要大些）。我们来看一下在哪些情况下使用这样的策略能够获胜：
3个黑帽子：每个人都看到两个黑帽子，每个人都猜自己是白帽子，所有人都猜错；
2个黑帽子，1个白帽子：戴黑帽子的人看到一黑一白，于是放弃；戴白帽子的人看的是两个黑帽子，因此他将猜对，从而所有人都获胜；
2个白帽子，1个黑帽子：和上面这种情况是类似的，所有人都将获胜；
3个白帽子：和第一种情况是类似的，所有人都猜错。
注意到只有在第一种情况和第四种情况下才会输掉游戏，这两种情况占了所有情况的2/8。于是，使用这种策略有75%的概率获胜。
我们需要想一想，在这个看似几乎不可能获胜的游戏中，为什么这种策略会有如此高的获胜概率。最关键的就是，这种策略充分利用了胜负判断的准则：大家要错就一起错，只有一个人错怪划不来的；要获胜就只让一个人猜对，多几个人同时猜对也没用。
根据上面的讨论，我们开始尝试把游戏的人数推广到一般的n。为了叙述方便，我们把每个人头顶上的帽子颜色依次用0和1来表示，数字1表示黑帽子，数字0表示白帽子。于是所有可能的情况就是2^n个01串。游戏开始前n个人预先约定一些“保留串”。他们的策略就是，观察其余n-1个人的帽子颜色：如果和所有的保留串都不匹配里，则放弃；如果恰好符合某个保留串，就猜自己是相反的颜色。比如，当n=3时，他们可以约定两个保留串000和111。如果实际情况是001的话，前两个人看到的是?01和0?1，不属于任何一个保留串，于是放弃；第三个人看到的是00?，正好和000相符，于是他就反过来猜自己不是那个0。注意到一些有趣的事实：如果实际情况恰好就是这些保留串之一，那大家就全猜错了；如果实际情况与所有保留串都相差两个数字以上，那大家全部放弃；如果实际情况与某个保留串恰好差一个数字，那只有一个人猜对，其余人放弃，从而获得胜利。现在的问题就是，如何寻找一个保留串集合，使得和某个保留串只差一个数字的情况尽可能的多。注意，我们必须要保证，任意两个保留串之间不能只差一个数字，这样的话才能保证发现有相符保留串的人不会面临“两可”的情况。假如你找到了t个保留串，则保证获胜的情况最多有t*n个（每个串“变一位”都有n种方法）。显然，最完美的情况就是t+t*n恰好等于总的情况数2^n。当n=2^k-1时，t+t*n是有可能恰好等于总情况数2^n的，也就是说每种可能的情况要么就是一个保留串，要么与唯一的一个保留串恰好差一位。此时，t+t*n=t(n+1)=t*(2^k)=2^(2^k-1)，t应该等于2^(2^k-1-k)。下面我们说明这t个保留串是如何生成的。
每个保留串都由原码和校验码两部分组成。我们把n位01串的位置编号转化为二进制，二进制里只有一个数字1的位置（即左起第1,2,4,8,...位）叫做校验码，有至少两个1的位置（3,5,6,7,9,...等其余位置）上的数字称作原码。显然，原码应该有n-k位（即2^k-1-k位）。枚举2^(n-k)种原码的01组合，对于每一组原码，定义第i个校验码的值为，除了它本身以外，所有编号的二进制表达中右起第i个数字为“1”的位置上一共有奇数个1还是偶数个1（相当于把标“x”的位置上的数异或一遍）。比如，第2个校验码是1，当且仅当有奇数个位置上的原码满足，位置编号的二进制表达形如...???1?且该位置上的数值正好也是1。所有可能的原码加上它对应校验码就是我们的保留串。
01串: a1 a2 a3 a4 a5 a6 a7
十进制编号: 1 2 3 4 5 6 7
二进制编号: 001 010 011 100 101 110 111
校验码1(a1): x x x
校验码2(a2): x x x
校验码3(a4): x x x
保留串0: 0 0 0 0 0 0 0
保留串1: 1 1 0 1 0 0 1
保留串2: 0 1 0 1 0 1 0
保留串3: 1 0 0 0 0 1 1
保留串4: 1 0 0 1 1 0 0
...... ...... ......
保留串14: 0 0 1 0 1 1 0
保留串15: 1 1 1 1 1 1 1
我们可以说明，对于任一个n位01串，只要它不是我们的保留串，我都有办法只变动一个数字让原码和校验码相符（从而变成一个保留串）。我们可以观察一下，由原码算出来的校验码和实际的校验码有哪些不同。如果只有一位校验码不同，直接把它改过来就是了；如果有多位校验码不同，那就找出改动哪一位原码可以让这些校验码同时取反。从位置编号的二进制的角度来考虑，这样的一位原码显然是唯一存在的。同时，我们可以保证任两个保留串之间都相差至少两个数字，即便你的原码只改动一位，校验码必然也会随之变化。前面已经说过，保留串的个数有2^(2^k-1-k)个，只有这2^(2^k-1-k)种情况下才会输掉游戏。因此，我们最初的问题就解决了：当人数n=2^k-1时，获胜的概率达到1 - [2^(2^k-1-k)/2^(2^k-1)]，即(2^k-1)/(2^k)。
顺便说一句，上面的编码方式叫做Hamming编码，是一种数据传输的校验方式。
参考资料：http://cornellmath.wordpress.com/2007/09/20/hat-guessing-puzzles-the-revenge/ （会意字，从啬从土）
警告，千万不要去计算pi的二进制表达。数学家们猜想pi是一个正规数(normal number)，也就是说它包含了任意一个有限长的01串，所有n位长的01串都以相等的概率出现在pi的二进制中。
如果你偏要去计算它，你会：
同时，你的电脑里会包含有目前所有已知的最邪恶的电脑病毒──事实上还包括有所有未知的最邪恶的病毒。
我的电脑上有很多极度私密的文件，我不希望你把它们浏览个遍。
你或许想，我只计算几位就行了；但何必去冒这个险呢？谁也说不准，算到哪一位时你会找到关于Kennedy刺杀案的秘密文件，或者你邻居的六岁小女孩和家里的狗狗XX的恶心照片，或者还未发行的最新一部Star Wars的完整拷贝。反正，千万别去算它。
同样的警告还适用于e、根号2、Euler常数、phi、除0以外的代数数的余弦值和其它各种各样的实数。
这也是为什么这些数总是被表示成十进制数的原因。
来源：http://everything2.net/index.pl?node_id=1302963
在各种文明的算术发展过程中，乘法运算的产生是很重要的一步。一个文明可以比较顺利地发展出计数方法和加减法运算，但要想创造一套简单可行的乘法运算方法却不那么容易。我们目前使用的乘法竖式计算看似简便，实际上这需要我们事先掌握九九乘法口诀表；考虑到这一点，这种竖式计算并不是完美的。我们即将看到，在数学的发展过程中，不同的文明创造出了哪些不同的乘法运算方法，其中有的运算法甚至可以完全抛弃乘法表。
古巴比伦数学使用60进制，考古发现的一块古巴比伦泥板证实了这一点。这块泥板上有一个正方形，对角线上有四个数字1, 24, 51, 10。最初发现这块泥板时人们并不知道这是什么意思，后来某牛人惊讶地发现，如果把这些数字当作60进制的三位小数的话，得到的正好是单位正方形对角线长度的近似值：1 + 24/60 + 51/60^2 + 10/60^3 = 1.41421296296... 这说明古巴比伦已经掌握了勾股定理。60进制的使用为古巴比伦数学的乘法运算发展带来了很大的障碍，因为如果你要背59-59乘法口诀表的话，至少也得背1000多项，等你把它背完了后我期末论文估计都已经全写完了。另一项考古发现告诉了我们古巴比伦数学的乘法运算如何避免使用乘法表。考古学家们发现一些泥板上刻有60以内的平方表，利用公式ab = [(a+b)^2 - a^2 - b^2]/2 可以迅速查表得到ab的值。另一个公式则是ab = [(a+b)^2 - (a-b)^2]/4，这说明两个数相乘只需取它们的和平方与差平方的差，再两次取半即可。平方数的频繁使用很可能加速了古巴比伦人发现勾股定理的过程。
古巴比伦数学把除以一个数看作是乘以它的倒数，利用倒数表可以很方便的实现这种算法。倒数表开头的一部分是这个样子：
2 0; 30
3 0; 20
4 0; 15
5 0; 12
6 0; 10
8 0; 7, 30
9 0; 6, 40
10 0; 6
12 0; 5
15 0; 4
16 0; 3, 45
18 0; 3, 20
20 0; 3
.... ....
古巴比伦人很早就发现，1/7是一个无限小数，怎么除也除不完。古巴比伦的倒数表里所有的数都是精确的小数，它们（在60进制中）都是有限小数。碰到无限小数时，他们会用取近似值的方法来解决。例如，古巴比伦人会通过1/13 = 1*(1/13) = 7*(1/91) ≈ 7*(1/90) = 7*(40/3600) = (7*40)/3600 来计算1/13的值。那个40就是查倒数表查出来的。
古埃及数学使用了完全不同的乘法运算法。它们的乘法运算不需要借助任何辅助用表。古埃及人注意到，任何一个数都可以表示为若干个不同的2的幂的和。因此，你需要做的仅仅是不断将1和乘数进行翻倍。看看古埃及人如何计算46乘以22：
46 x 22 = 1012
1 22
2 44 44
4 88 + 88
8 176 + 176
16 352
32 704 + 704
-------
1012
上面的演算中，左列是1不断翻倍的结果，右边是22不断翻倍的结果。选出左列的2, 4, 8, 32，它们的和正好就是被乘数46；那么把右列对应的数加起来就是乘法运算的最终结果。至于如何选出2, 4, 8, 32这四个数，一个简单的方法就是，不断选出左列里小于被乘数的数中最大的一个，然后当前被乘数减去它。比如，32是最大的数，用46-32后剩14；8是小于14的最大数，14-8后剩6；然后最大的小于6的数是4，6减去4后剩2，这样下来2+4+8+32正好就是被乘数46了。这其实就是二进制的经典应用，2, 4, 8, 32正好与46的二进制中的数字1一一对应。你可以在这里看到一些相关的东西。
无独有偶，据说俄国农村曾产生过这样一种乘法算术法：将被乘数逐次减半，同时乘数依次加倍，那么找出所有左边的数是奇数的行，其右列的数的和就是答案。例如，下面的例子中，23, 11, 5和1都是奇数，于是右边对应的44, 88, 176和704的和就是乘法运算的结果。这个做法与古埃及的算术法完全一样，但看起来似乎更神奇一些。
46 x 22 = 1012
46 22
23 44 44
11 88 + 88
5 176 + 176
2 352
1 704 + 704
-------
1012
做人要厚道
转贴请注明出处
你认为，一个函数图象里是否有可能包含这个函数本身的“图象”？难以置信的是，还真有人构造了这样一个东西。2001年，Jeff Tupper发表的一篇论文里提到了这样一个有趣的不等式：
在0 <= x <= 105，n <= y <= n + 16的范围内，这个不等式对应的图象是这个样子：
其中，n = 96093937991895888497167296212785275471500433966012930665150551927170280239526642
46896428421743507181212671537827706233559932372808741443078913259639413377234878
57735749823926629715517173716995165232890538221612403238855866184013235585136048
82869333790249145422928866708109618449609170518345406782773155170540538162738096
76025656250169814820834187831638491155902256100036523513703438744618483787372381
98224849863465033159410054974700593138339226497249461751545728366702369745461014
655997933798537483143786841806593422227898388722980000748404719
你会觉得这个很神奇吗？你也许会想，天哪，这个是怎么构造出来的啊！但仔细思考之后，你会发现这个一点都不神奇。事实上明白了道理之后你可以构造出无数个这样的式子来。现在给你一些时间让你思考一下，你能否看出其中的奥秘？
就像魔术揭秘一样，说穿了真相后上面的这些东西就一点意思都没有了。在这个式子里，涉及到x和y的变量时都加上了取整符号，因此整个图象都是一格一格的。这样，不等式右边的式子就简化为y div 17 * 2^(-17x - y mod 17) mod 2，其中x和y都为整数。接着观察，一个数乘以2的负k次方相当于对应的二进制数右移k位，那么x * 2^(-k) mod 2实质上就是二进制数x右起第k位上的数字。对于某个自然数t，当17t <= y < 17(t+1)时，指数-17x - y mod 17恰好对应所有的负整数，于是位于y=17t和y=17t+16之间的图象的每个像素和t的二进制中的每一位数字一一对应。随着t值的增加，图形的像素会一点一点地变化。当纵坐标足够大时，必然会出现一段高度为17的图象，图象的样子和不等式本身的样子相同。当然，你也可以在里面“找到”任何你想要的图象，只需要把图象还原为二进制数并转换为十进制即可。你甚至可以告诉你的MM，说你发现了一个函数，函数在某个位置的图象正好是某某某我爱你的字样。
Matrix67原创
转贴请注明出处
最近发现了一些很不厚道的人，希望大家注意哦！
在所有的分形图形中，Sierpinski三角形可能是大家最熟悉的了，因为它在OI题目中经常出现，OJ上的题目和省选题目中都有它的身影。这篇文章将简单介绍Sierpinski三角形的几个惊人性质。如果你以前就对Sierpinski三角形有一些了解，这篇文章带给你的震撼将更大，因为你会发现Sierpinski三角形竟然还有这些用途。
Sierpinski三角形的构造
和之前介绍的两种图形一样，Sierpinski三角形也是一种分形图形，它是递归地构造的。最常见的构造方法如上图所示：把一个三角形分成四等份，挖掉中间那一份，然后继续对另外三个三角形进行这样的操作，并且无限地递归下去。每一次迭代后整个图形的面积都会减小到原来的3/4，因此最终得到的图形面积显然为0。这也就是说，Sierpinski三角形其实是一条曲线，它的Hausdorff维度介于1和2之间。
Sierpinski三角形的另一种构造方法如下图所示。把正方形分成四等份，去掉右下角的那一份，并且对另外三个正方形递归地操作下去。挖个几次后把脑袋一歪，你就可以看到一个等腰直角的Sierpinski三角形。
Sierpinski三角形有一个神奇的性质：如果某一个位置上有点（没被挖去），那么它与原三角形顶点的连线上的中点处也有点。这给出另一个诡异的Sierpinski三角形构造方法：给出三角形的三个顶点，然后从其中一个顶点出发，每次随机向任意一个顶点移动1/2的距离（走到与那个顶点的连线的中点上），并在该位置作一个标记；无限次操作后所有的标记就组成了Sierpinski三角形。下面的程序演示了这一过程，程序在fpc 2.0下通过编译。对不起用C语言的兄弟了，我不会C语言的图形操作。{$ASSERTIONS+}
uses graph,crt;
const
x1=320; y1=20;
x2=90; y2=420;
x3=550; y3=420;
density=2500;
timestep=10;
var
gd,gm,i,r:integer;
x,y:real;
begin
gd:=D8bit;
gm:=m640x480;
InitGraph(gd,gm,'');
Assert(graphResult=grOk);
x:=x1;
y:=y1;
for i:=1 to density do
begin
r:=random(3);
if r=0 then
begin
x:=(x+x1)/2;
y:=(y+y1)/2;
end
else if r=1 then
begin
x:=(x+x2)/2;
y:=(y+y2)/2;
end
else begin
x:=(x+x3)/2;
y:=(y+y3)/2;
end;
PutPixel(round(x),round(y),white);
Delay(timestep);
end;
CloseGraph;
end.
Sierpinski三角形与杨辉三角
第一次发现Sierpinski三角形与杨辉三角的关系时，你会发现这玩意儿不是一般的牛。写出8行或者16行的杨辉三角，然后把杨辉三角中的奇数和偶数用不同的颜色区别开来，你会发现杨辉三角模2与Sierpinski三角形是等价的。也就是说，二项式系数（组合数）的奇偶性竟然可以表现为一个分形图形！在感到诧异的同时，冷静下来仔细想想，你会发现这并不难理解。
我们下面说明，如何通过杨辉三角奇偶表的前四行推出后四行来。可以看到杨辉三角的前四行是一个二阶的Sierpinski三角形，它的第四行全是奇数。由于奇数加奇数等于偶数，那么第五行中除了首尾两项为1外其余项都是偶数。而偶数加偶数还是偶数，因此中间那一排连续的偶数不断地两两相加必然得到一个全是偶数项的“倒三角”。同时，第五行首尾的两个1将分别产生两个和杨辉三角前四行一样的二阶Sierpinski三角形。这正好组成了一个三阶的Sierpinski三角形。显然它的最末行仍然均为奇数，那么对于更大规模的杨辉三角，结论将继续成立。
Sierpinski三角形与Hanoi塔
有没有想过，把Hanoi塔的所有状态画出来，可以转移的状态间连一条线，最后得到的是一个什么样的图形？二阶Hanoi塔反正也只有9个节点，你可以自己试着画一下。不断调整节点的位置后，得到的图形大概就像这个样子：
如果把三阶的Hanoi塔表示成无向图的话，得到的结果就是三阶的Sierpinski三角形。下面的这张图说明了这一点。把二阶Hanoi塔对应的无向图复制两份放在下面，然后在不同的柱子上为每个子图的每个状态添加一个更大的盘子。新的图中原来可以互相转移的状态现在仍然可以转移，同时还出现了三个新的转移关系将三个子图连接在了一起。重新调整一下各个节点的位置，我们可以得到一个三阶的Sierpinski三角形。
显然，对于更大规模的Hanoi塔问题，结论仍然成立。
Sierpinski三角形与位运算
编程画出Sierpinski三角形比想象中的更简单。下面的两个代码（实质相同，仅语言不同）可以打印出一个Sierpinski三角形来。const
n=1 shl 5-1;
var
i,j:integer;
begin
for i:=0 to n do
begin
for j:=0 to n do
if i and j = j then write('#')
else write(' ');
writeln;
end;
readln;
end.#include <stdio.h>
int main()
{
const int n=(1<<5)-1;
int i,j;
for (i=0; i<=n; i++)
{
for (j=0; j<=n; j++)
printf( (i&j)==j ? "#" : " ");
printf("\n");
}
getchar();
return 0;
}
上面两个程序是一样的。程序将输出：#
##
# #
####
# #
## ##
# # # #
########
# #
## ##
# # # #
#### ####
# # # #
## ## ## ##
# # # # # # # #
################
# #
## ##
# # # #
#### ####
# # # #
## ## ## ##
# # # # # # # #
######## ########
# # # #
## ## ## ##
# # # # # # # #
#### #### #### ####
# # # # # # # #
## ## ## ## ## ## ## ##
# # # # # # # # # # # # # # # #
################################
这个程序告诉我们：在第i行第j列上打一个点当且仅当i and j=j，这样最后得到的图形就是一个Sierpinski三角形。这是为什么呢？其实原因很简单。把i和j写成二进制（添加前导0使它们位数相同），由于j不能大于i，因此只有下面三种情况：
情况一：
i = 1?????
j = 1?????
问号部分i大于等于j
i的问号部分记作i'，j的问号部分记作j'。此时i and j=j当且仅当i' and j'=j'
情况二：
i = 1?????
j = 0?????
问号部分i大于等于j
i的问号部分记作i'，j的问号部分记作j'。此时i and j=j当且仅当i' and j'=j'
情况三：
i = 1?????
j = 0?????
问号部分i小于j
此时i and j永远不可能等于j。i' < j'意味着i'和j'中首次出现数字不同的那一位上前者为0，后者为1，那么i和j做and运算时这一位的结果是0，与j不等。
注意到，去掉一个二进制数最高位上的“1”，相当于从这个数中减去不超过它的最大的2的幂。观察每一种情况中i,j和i',j'的实际位置，不难发现这三种情况递归地定义出了整个Sierpinski三角形。
嘿！发现没有，我通过Sierpinski三角形证明了这个结论：组合数C(N,K)为奇数当且仅当N and K=K。这篇文章很早之前就计划在写了，前几天有人问到这个东西，今天顺便也写进来。
另外，把i and j=j 换成i or j=n也可以打印出Sierpinski三角形来。i and j=j表示j的二进制中有1的位置上i也有个1，那么此时i or (not j)结果一定全为1（相当于程序中的常量n），因此打印出来的结果与原来的输出正好左右镜像。
Matrix67原创
转贴请注明出处
网友Voldemort在12楼和13楼很辛苦地帖了一个杨辉三角模2问题的扩展，大家可以看看
下面分享的是我自己写的三个代码，里面有些题目也是我自己出的。这些代码都是在我的Pascal时代写的，恕不提供C语言了。代码写得并不好，我只是想告诉大家位运算在实战中的应用，包括了搜索和状态压缩DP方面的题目。其实大家可以在网上找到更多用位运算优化的题目，这里整理出一些自己写的代码，只是为了原创系列文章的完整性。这一系列文章到这里就结束了，希望大家能有所收获。
Matrix67原创，转贴请注明出处。
Problem : 费解的开关
题目来源
06年NOIp模拟赛（一） by Matrix67 第四题
问题描述
你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式
第一行有一个正整数n，代表数据中共有n个待解决的游戏初始状态。
以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
对于30%的数据，n<=5；
对于100%的数据，n<=500。
输出格式
输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。
样例输入
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
样例输出
3
2
-1
程序代码const
BigPrime=3214567;
MaxStep=6;
type
pointer=^rec;
rec=record
v:longint;
step:integer;
next:pointer;
end;
var
total:longint;
hash:array[0..BigPrime-1]of pointer;
q:array[1..400000]of rec;
function update(a:longint;p:integer):longint;
begin
a:=a xor (1 shl p);
if p mod 5<>0 then a:=a xor (1 shl (p-1));
if (p+1) mod 5<>0 then a:=a xor (1 shl (p+1));
if p<20 then a:=a xor (1 shl (p+5));
if p>4 then a:=a xor (1 shl (p-5));
exit(a);
end;
function find(a:longint;step:integer):boolean;
var
now:pointer;
begin
now:=hash[a mod BigPrime];
while now<>nil do
begin
if now^.v=a then exit(true);
now:=now^.next;
end;
new(now);
now^.v:=a;
now^.step:=step;
now^.next:=hash[a mod BigPrime];
hash[a mod BigPrime]:=now;
total:=total+1;
exit(false);
end;
procedure solve;
var
p:integer;
close:longint=0;
open:longint=1;
begin
find(1 shl 25-1,0);
q[1].v:=1 shl 25-1;
q[1].step:=0;
repeat
inc(close);
for p:=0 to 24 do
if not find(update(q[close].v,p),q[close].step+1) and (q[close].step+1<MaxStep) then
begin
open:=open+1;
q[open].v:=update(q[close].v,p);
q[open].step:=q[close].step+1;
end;
until close>=open;
end;
procedure print(a:longint);
var
now:pointer;
begin
now:=hash[a mod BigPrime];
while now<>nil do
begin
if now^.v=a then
begin
writeln(now^.step);
exit;
end;
now:=now^.next;
end;
writeln(-1);
end;
procedure main;
var
ch:char;
i,j,n:integer;
t:longint;
begin
readln(n);
for i:=1 to n do
begin
t:=0;
for j:=1 to 25 do
begin
read(ch);
t:=t*2+ord(ch)-48;
if j mod 5=0 then readln;
end;
print(t);
if i<n then readln;
end;
end;
begin
solve;
main;
end.
======================= 性感的分割线 =======================
Problem : garden / 和MM逛花园
题目来源
07年Matrix67生日邀请赛第四题
问题描述
花园设计强调，简单就是美。Matrix67常去的花园有着非常简单的布局：花园的所有景点的位置都是“对齐”了的，这些景点可以看作是平面坐标上的格点。相邻的景点之间有小路相连，这些小路全部平行于坐标轴。景点和小路组成了一个“不完整的网格”。
一个典型的花园布局如左图所示。花园布局在6行4列的网格上，花园的16个景点的位置用红色标注在了图中。黑色线条表示景点间的小路，其余灰色部分实际并不存在。
Matrix67 的生日那天，他要带着他的MM在花园里游玩。Matrix67不会带MM两次经过同一个景点，因此每个景点最多被游览一次。他和他的MM边走边聊，他们是如此的投入以致于他们从不会“主动地拐弯”。也就是说，除非前方已没有景点或是前方的景点已经访问过，否则他们会一直往前走下去。当前方景点不存在或已游览过时，Matrix67会带MM另选一个方向继续前进。由于景点个数有限，访问过的景点将越来越多，迟早会出现不能再走的情况（即四个方向上的相邻景点都访问过了），此时他们将结束花园的游览。Matrix67希望知道以这种方式游览花园是否有可能遍历所有的景点。Matrix67可以选择从任意一个景点开始游览，以任意一个景点结束。
在上图所示的花园布局中，一种可能的游览方式如右图所示。这种浏览方式从(1,2)出发，以(2,4)结束，经过每个景点恰好一次。
输入格式
第一行输入两个用空格隔开的正整数m和n，表示花园被布局在m行n列的网格上。
以下m行每行n个字符，字符“0”表示该位置没有景点，字符“1”表示对应位置有景点。这些数字之间没有空格。
输出格式
你的程序需要寻找满足“不主动拐弯”性质且遍历所有景点的游览路线。
如果没有这样的游览路线，请输出一行“Impossible”（不带引号，注意大小写）。
如果存在游览路线，请依次输出你的方案中访问的景点的坐标，每行输出一个。坐标的表示格式为“(x,y)”，代表第x行第y列。
如果有多种方案，你只需要输出其中一种即可。评测系统可以判断你的方案的正确性。
样例输入
6 4
1100
1001
1111
1100
1110
1110
样例输出
(1,2)
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(6,1)
(6,2)
(6,3)
(5,3)
(5,2)
(4,2)
(3,2)
(3,3)
(3,4)
(2,4)
数据规模
对于30%的数据，n,m<=5；
对于100%的数据，n,m<=10。
程序代码：program garden;
const
dir:array[1..4,1..2]of integer=
((1,0),(0,1),(-1,0),(0,-1));
type
arr=array[1..10]of integer;
rec=record x,y:integer;end;
var
map:array[0..11,0..11]of boolean;
ans:array[1..100]of rec;
n,m,max:integer;
step:integer=1;
state:arr;
procedure readp;
var
i,j:integer;
ch:char;
begin
readln(m,n);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(ch);
map[i,j]:=(ch='1');
inc(max,ord( map[i,j] ))
end;
readln;
end;
end;
procedure writep;
var
i:integer;
begin
for i:=1 to step do
writeln( '(' , ans[i].x , ',' , ans[i].y , ')' );
end;
procedure solve(x,y:integer);
var
tx,ty,d:integer;
step_cache:integer;
state_cache:arr;
begin
step_cache:=step;
state_cache:=state;
if step=max then
begin
writep;
exit;
end;
for d:=1 to 4 do
begin
tx:=x+dir[d,1];
ty:=y+dir[d,2];
while map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do
begin
inc(step);
ans[step].x:=tx;
ans[step].y:=ty;
state[tx]:=state[tx] or ( 1 shl (ty-1) );
tx:=tx+dir[d,1];
ty:=ty+dir[d,2];
end;
tx:=tx-dir[d,1];
ty:=ty-dir[d,2];
if (tx<>x) or (ty<>y) then solve(tx,ty);
state:=state_cache;
step:=step_cache;
end;
end;
{====main====}
var
i,j:integer;
begin
assign(input,'garden.in');
reset(input);
assign(output,'garden.out');
rewrite(output);
readp;
for i:=1 to n do
for j:=1 to m do
if map[i,j] then
begin
ans[1].x:=i;
ans[1].y:=j;
state[i]:=1 shl (j-1);
solve(i,j);
state[i]:=0;
end;
close(input);
close(output);
end.
======================= 性感的分割线 =======================
Problem : cowfood / 玉米地
题目来源
USACO月赛
问题描述
农夫约翰购买了一处肥沃的矩形牧场，分成M*N(1<=M<=12; 1<=N<=12)个格子。他想在那里的一些格子中种植美味的玉米。遗憾的是，有些格子区域的土地是贫瘠的，不能耕种。
精明的约翰知道奶牛们进食时不喜欢和别的牛相邻，所以一旦在一个格子中种植玉米，那么他就不会在相邻的格子中种植，即没有两个被选中的格子拥有公共边。他还没有最终确定哪些格子要选择种植玉米。
作为一个思想开明的人，农夫约翰希望考虑所有可行的选择格子种植方案。由于太开明，他还考虑一个格子都不选择的种植方案！请帮助农夫约翰确定种植方案总数。
输入格式:
第一行：两个用空格分隔的整数M和N
第二行到第M+1行：第i+1行描述牧场第i行每个格子的情况，N个用空格分隔的整数，表示这个格子是否可以种植（1表示肥沃的、适合种植，0表示贫瘠的、不可种植）
输出格式
一个整数，农夫约翰可选择的方案总数除以 100,000,000 的余数
样例输入
2 3
1 1 1
0 1 0
样例输出
9
样例说明
给可以种植玉米的格子编号：
1 2 3
4
只种一个格子的方案有四种(1,2,3或4)，种植两个格子的方案有三种(13,14或34)，种植三个格子的方案有一种(134)，还有一种什么格子都不种。
4+3+1+1=9。
数据规模
对于30%的数据，N,M<=4；
对于100%的数据，N,M<=12。
程序代码：program cowfood;
const
d=100000000;
MaxN=12;
var
f:array[0..MaxN,1..2000]of longint;
w:array[1..2000,1..2000]of boolean;
st:array[0..2000]of integer;
map:array[0..MaxN]of integer;
m,n:integer;
function Impossible(a:integer):boolean;
var
i:integer;
flag:boolean=false;
begin
for i:=1 to MaxN do
begin
if flag and (a and 1=1) then exit(true);
flag:=(a and 1=1);
a:=a shr 1;
end;
exit(false);
end;
function Conflict(a,b:integer):boolean;
var
i:integer;
begin
for i:=1 to MaxN do
begin
if (a and 1=1) and (b and 1=1) then exit(true);
a:=a shr 1;
b:=b shr 1;
end;
exit(false);
end;
function CanPlace(a,b:integer):boolean;
begin
exit(a or b=b);
end;
procedure FindSt;
var
i:integer;
begin
for i:=0 to 1 shl MaxN-1 do
if not Impossible(i) then
begin
inc(st[0]);
st[st[0]]:=i;
end;
end;
procedure Init;
var
i,j:integer;
begin
for i:=1 to st[0] do
for j:=i to st[0] do
if not Conflict(st[i],st[j]) then
begin
w[i,j]:=true;
w[j,i]:=true;
end;
end;
procedure Readp;
var
i,j,t,v:integer;
begin
readln(m,n);
for i:=1 to m do
begin
v:=0;
for j:=1 to n do
begin
read(t);
v:=v*2+t;
end;
map[i]:=v;
readln;
end;
end;
procedure Solve;
var
i,j,k:integer;
begin
f[0,1]:=1;
map[0]:=1 shl n-1;
for i:=1 to m do
for j:=1 to st[0] do
if not CanPlace(st[j],map[i]) then f[i,j]:=-1 else
for k:=1 to st[0] do if (f[i-1,k]<>-1) and w[j,k] then
f[i,j]:=(f[i,j]+f[i-1,k]) mod d;
end;
procedure Writep;
var
j:integer;
ans:longint=0;
begin
for j:=1 to st[0] do
if f[m,j]<>-1 then ans:=(ans+f[m,j]) mod d;
writeln(ans);
end;
begin
assign(input,'cowfood.in');
reset(input);
assign(output,'cowfood.out');
rewrite(output);
FindSt;
Init;
Readp;
Solve;
Writep;
close(input);
close(output);
end.
今天我们来看两个稍微复杂一点的例子。
n皇后问题位运算版
n皇后问题是啥我就不说了吧，学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。初始时，upperlim:=(1 shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO，0.3s，暴爽。procedure test(row,ld,rd:longint);
var
pos,p:longint;
begin
{ 1} if row<>upperlim then
{ 2} begin
{ 3} pos:=upperlim and not (row or ld or rd);
{ 4} while pos<>0 do
{ 5} begin
{ 6} p:=pos and -pos;
{ 7} pos:=pos-p;
{ 8} test(row+p,(ld+p)shl 1,(rd+p)shr 1);
{ 9} end;
{10} end
{11} else inc(sum);
end;
乍一看似乎完全摸不着头脑，实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟，实在没研究出来再看下面的解说。
和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6x6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。前面说过-a相当于not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。
~~~~====~~~~===== 华丽的分割线 =====~~~~====~~~~
Gray码
假如我有4个潜在的GF，我需要决定最终到底和谁在一起。一个简单的办法就是，依次和每个MM交往一段时间，最后选择给我带来的“满意度”最大的MM。但看了dd牛的理论后，事情开始变得复杂了：我可以选择和多个MM在一起。这样，需要考核的状态变成了2^4=16种（当然包括0000这一状态，因为我有可能是玻璃）。现在的问题就是，我应该用什么顺序来遍历这16种状态呢？
传统的做法是，用二进制数的顺序来遍历所有可能的组合。也就是说，我需要以0000->0001->0010->0011->0100->...->1111这样的顺序对每种状态进行测试。这个顺序很不科学，很多时候状态的转移都很耗时。比如从0111到1000时我需要暂时甩掉当前所有的3个MM，然后去把第4个MM。同时改变所有MM与我的关系是一件何等巨大的工程啊。因此，我希望知道，是否有一种方法可以使得，从没有MM这一状态出发，每次只改变我和一个MM的关系（追或者甩），15次操作后恰好遍历完所有可能的组合（最终状态不一定是1111）。大家自己先试一试看行不行。
解决这个问题的方法很巧妙。我们来说明，假如我们已经知道了n=2时的合法遍历顺序，我们如何得到n=3的遍历顺序。显然，n=2的遍历顺序如下：
00
01
11
10
你可能已经想到了如何把上面的遍历顺序扩展到n=3的情况。n=3时一共有8种状态，其中前面4个把n=2的遍历顺序照搬下来，然后把它们对称翻折下去并在最前面加上1作为后面4个状态：
000
001
011
010 ↑
--------
110 ↓
111
101
100
用这种方法得到的遍历顺序显然符合要求。首先，上面8个状态恰好是n=3时的所有8种组合，因为它们是在n=2的全部四种组合的基础上考虑选不选第3个元素所得到的。然后我们看到，后面一半的状态应该和前面一半一样满足“相邻状态间仅一位不同”的限制，而“镜面”处则是最前面那一位数不同。再次翻折三阶遍历顺序，我们就得到了刚才的问题的答案：
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
这种遍历顺序作为一种编码方式存在，叫做Gray码（写个中文让蜘蛛来抓：格雷码）。它的应用范围很广。比如，n阶的Gray码相当于在n维立方体上的Hamilton回路，因为沿着立方体上的边走一步，n维坐标中只会有一个值改变。再比如，Gray码和Hanoi塔问题等价。Gray码改变的是第几个数，Hanoi塔就该移动哪个盘子。比如，3阶的Gray码每次改变的元素所在位置依次为1-2-1-3-1-2-1，这正好是3阶Hanoi塔每次移动盘子编号。如果我们可以快速求出Gray码的第n个数是多少，我们就可以输出任意步数后Hanoi塔的移动步骤。现在我告诉你，Gray码的第n个数（从0算起）是n xor (n shr 1)，你能想出来这是为什么吗？先自己想想吧。
下面我们把二进制数和Gray码都写在下面，可以看到左边的数异或自身右移的结果就等于右边的数。
二进制数 Gray码
000 000
001 001
010 011
011 010
100 110
101 111
110 101
111 100
从二进制数的角度看，“镜像”位置上的数即是对原数进行not运算后的结果。比如，第3个数010和倒数第3个数101的每一位都正好相反。假设这两个数分别为x和y，那么x xor (x shr 1)和y xor (y shr 1)的结果只有一点不同：后者的首位是1，前者的首位是0。而这正好是Gray码的生成方法。这就说明了，Gray码的第n个数确实是n xor (n shr 1)。
今年四月份mashuo给我看了这道题，是二维意义上的Gray码。题目大意是说，把0到2^(n+m)-1的数写成2^n * 2^m的矩阵，使得位置相邻两数的二进制表示只有一位之差。答案其实很简单，所有数都是由m位的Gray码和n位Gray码拼接而成，需要用左移操作和or运算完成。完整的代码如下：var
x,y,m,n,u:longint;
begin
readln(m,n);
for x:=0 to 1 shl m-1 do begin
u:=(x xor (x shr 1)) shl n; //输出数的左边是一个m位的Gray码
for y:=0 to 1 shl n-1 do
write(u or (y xor (y shr 1)),' '); //并上一个n位Gray码
writeln;
end;
end.
Matrix67原创
转贴请注明出处
Matrix67 |
2008-05-12 12:31 | 
