神奇的二进制修订后的结果.doc

神奇的二进制浙江省镇海中学 贺洪鸣编者按：计算机只能认识二进制，二进制数也是大家非常熟悉的一种数字。其实，正因为二进制只有两种值0和1，使得它能很好地表示自然界中的某些正反两类事物，比如电灯的开关，硬币的正反两面等。本文正是充分地发掘了二进制的性质，加以巧妙利用，达到巧解问题的目的。例一：求am mod n的值，1m,n109。【问题分析】令m的二进制表示为brbr-1b2b1。则：公式中去掉g于是，可得以下算法：【算法】1 求得m的二进制表示brbr-1b2b12 ans13 For kr downto 1 do begin4 ans(ans*ans) mod n5 If bk=1 then ans(ans*a) mod n end6 输出ans此算法的时间复杂度仅为O(log(m)。例二：灯泡（试题来源：算法艺术与信息学竞赛第228页2.2.6，刘汝佳、黄亮，清华大学出版社。）【问题描述】有n个灯泡排列成环形（灯泡1左边是灯泡n， 灯泡2左边是灯泡1，灯泡3左边是灯泡2， ，灯泡n左边是灯泡n-1）。在时间0时，有的灯泡是亮的，有的是不亮。灯泡i在时间t+1（t0）改变状态（亮不亮，不亮亮）当且仅当灯泡i左边的灯泡在时间t是亮的。求在时间m时，每个灯泡的状态（n106，m109）。本题被作者用在了2007年宁波市决赛试题的第二题，要求时限1秒。【问题分析】 直接模拟，必然超时。考虑到时刻m最大达到109，而它的二进制表示最多只有30位。如果我们能够找到与例一相似的方法，计算时刻m时，只算log(m)次，则n个灯泡，只计算nlog(m)，最多约3000万次，就能在1秒的时限内出解了。1找规律我们从简单的情况入手，找规律。在时刻t时，以Xk=1表示第k个灯是亮的，以Xk=0表示第k个灯为暗的。如果时刻t时各灯状态分别为X1，X2，Xn，则时刻t+1时各灯状态为：X1 xor Xn，X2 xor X1，X3 xor X2，Xn xor Xn-1。时刻0时刻1时刻2时刻3时刻4时刻5时刻6时刻7时刻8时刻9时刻10时刻11时刻12时刻13时刻14时刻15时刻16灯11151413451225124523131235342412344535234515灯22122512452313123534241234453523451514134512灯33231312353424123445352345151413451225124523灯44342412344535234515141345122512452313123534灯55453523451514134512251245231312353424123445以n=5为例，当时刻0时，灯k的状态以Xk表示（为1表示亮，为0表示暗）。在上表中，简单地以数字k代表Xk。则：（1）时刻1时 灯1状态为：时刻0时灯5 状态xor 时刻0时灯1 状态，即X5 xor X1；表格中，简记为15。 灯2状态为：时刻0时灯1 状态xor 时刻0时灯2 状态，即X1 xor X2；表格中，简记为12。灯3状态为：时刻0时灯2 状态xor 时刻0时灯3 状态，即X2 xor X3；表格中，简记为23。灯4状态为：时刻0时灯3 状态xor 时刻0时灯4 状态，即X3 xor X4；表格中，简记为34。灯5状态为：时刻0时灯4 状态xor 时刻0时灯5 状态，即X4 xor X5；表格中，简记为45。（2）时刻2时灯1状态为：时刻1时灯5 状态xor 时刻1时灯1 状态，即：（X4 xor X5）xor（X5 xor X1）=X1 xor X4；表格中，简记为14。灯2状态为：时刻1时灯1 状态xor 时刻1时灯2 状态，即：（X5 xor X1）xor（X1 xor X2）=X5 xor X2；表格中，简记为25。灯3状态为：时刻1时灯2 状态xor 时刻1时灯3 状态，即：（X1 xor X2）xor（X2 xor X3）=X1 xor X3；表格中，简记为13。灯4状态为：时刻1时灯3 状态xor 时刻1时灯4 状态，即：（X2 xor X3）xor（X3 xor X4）=X2 xor X4；表格中，简记为24。灯5状态为：时刻1时灯4 状态xor 时刻1时灯5 状态，即：（X3 xor X4）xor（X4 xor X5）=X3 xor X5；表格中，简记为35。（3）其余时刻各盏灯的状态，也可以使用相同的方法求得。观察该表，发现规律：如果t时刻第p个灯状态为Yp，则t+2k时刻第p个灯泡状态为：t时刻第p个灯的状态 xor t时刻p朝左数2k个灯的状态。即Yp xor Y(p-2k-1)mod n+1。比如，我们求时刻13时各盏灯的状态，可以按以下的步骤求：由时刻0各盏灯的状态，求得时刻1时各盏灯的状态；由时刻1各盏灯的状态，求得时刻5时各盏灯的状态；由时刻5各盏灯的状态，求得时刻13时各盏灯的状态；一般地，因为时刻m可以表示为二进制数brbr-1b2b1，而其中的某位bk表示bk*2k-1(bk=1或0)。如果上述规律是正确的，则可以由时刻0的n个灯状态推得时刻b1*20的n个灯状态，由时刻b1*20推得时刻b2*21+b1*20的n个灯状态，由时刻b2*21+b1*20的n个灯状态推得时刻b3*22+b2*21+b1*20的n个灯状态，最后由时刻br-1*2r-2+b2*21+b1*20的n个灯状态推得时刻br*2r-1+b2*21+b1*20的n个灯状态。问题可以在O(nlog(m)的时间复杂度下解决。2规律的证明下面采用数学归纳法进行证明。（1）当k=0时，2k=1，结论就是问题的定义，显然成立。（2）假设当k=r-1（r1）时，结论成立。 如果时刻t时，第p个灯为Yp，第p左数2r-1个灯为Y(p-2r-1-1) mod n+1，第p左数2r个灯(即第p左数2r-1个后再左数2r-1个)为Y(p-2r-1) mod n+1。时刻t+2r-1时灯p状态为：时刻t时灯p的状态 xor 时刻t时灯p左数2r-1个灯的状态，即Yp xor Y(p-2r-1-1) mod n+1时刻t+2r-1时灯p左数2r-1个灯的状态为：时刻t时灯p左数2r-1个灯的状态 xor 时刻t时灯p左数2r个灯的状态，即Y(p-2r-1-1) mod n+1 xor Y(p-2r-1) mod n+1当时刻(t+2r-1)+2r-1时，灯p的状态为：时刻(t+2r-1)时灯p的状态 xor时刻(t+2r-1)时灯p左数2r-1个灯的状态，即：(Yp xor Y(p-2r-1-1) mod n+1) xor (Y(p-2r-1-1) mod n+1 xor Y(p-2r-1) mod n+1)= Yp xor Y(p-2r-1) mod n+1即当k=r时，结论也成立！由(1)和(2)知，对于任意大于等于0的整数k， 如果时刻t时灯p的状态为Yp，则时刻t+2k时，灯p的状态为Yp xor Y(p-2k-1) mod n+1。证毕！于是，可以将m分解为二进制表示，对于二进制对应的非0的第k位，如果原来第p（1pn）个灯状态为Xp，则时刻加上该位表示的值后，第p个灯状态为Xp xor X(p-2k-1-1) mod n+1。为节约空间，可以采用滚动数组来存储每个时刻各盏灯的状态。【算法】1、求得m的二进制表示：fr.1 2、根据输入数据得到n个灯泡的初始状态x0,1,x0,2,x0,3,x0,n 其中灯亮的取值1,不亮取值0;3、C0;/滚动数组，初始第0行4、For k1 to r do /扫描m的二进制各位5、 if fk=1 then begin6、 C1-c;7、 For j1 to n do8、 xc,jx1-c,j xor x1-c,(j-2k-1-1) mod n+n)mod n+1; end9、输出最终n个灯的状态:xc,1,xc,2,xc,3,xc,n在本刊第2期第32页有一篇例谈数学方法在编程中的应用，该文的例1和例2，也是两个类似的例子。其中的例2，如果限制每次取石子数不超过m，则成为算法艺术与信息学竞赛第237页的2.2.12题了。此时，因为对于m+1个石子，第一人取了k(1km)个，第二人总能取m+1-k个，使得一轮过后，刚好取走m+1个。于是，可以将每堆石子数取除以m+1后的余数，然后按照例谈数学方法在编程中的应用例2所提到的方法解决此题。二进制除了如上述各例所示，在优化算法时间效率上的应用外，还广泛应用于状态压缩和状态转换时，时间和空间效率的优化。例三：翻硬币（试题来源：算法艺术与信息学竞赛第12页1.2.5，刘汝佳、黄亮，清华大学出版社。）【问题描述】考虑一个翻硬币游戏，有n(1n50000)行硬币，每行有m(1m10)个硬币，排成一个n*m的方阵，有的正面朝上，有的反面朝上。我们每次可以把一整行或一整列的所有硬币翻过来，请问能得到的正面朝上的硬币最多为多少?本题被作者用作今年宁波市高中组比赛的第一题了，比赛时，要求时限1秒。【问题分析】 显然，两次翻转同一列或同一行，相当于不翻转。于是，所有列的翻转方案最多只有2m种。我们可以穷举2m个列的翻转方案，对于每个方案，扫描n行，对于每行中翻与不翻两种情况下正面朝上硬币数的较大者，进行累加。最终求得2m个累加和中的最大者。 以ai,j表示第i行第j列的硬币情况，为1表示正面朝上，为0表示反面朝上。则有以下算法：【算法1】1 输入a1.n,1.m /硬币正反面情况2 ans03 For j1 to m do fj0 /所有列不翻转4 While j0 do begin /以下第5行至第12行求当前的各列翻转方案下，最多能得到的硬币数5 For i1 to n do begin /扫描行6 sum10 /第i行不翻转时正面朝上硬币数7 sum20 /第i行翻转时正面朝上硬币数8 For k1 to m do begin /第k列翻转情况9 sum1sum1+ai,k xor fk10 sum2sum2+1 xor ai,k xor fk end11 sumsum+Maxsum1,sum2 end12 ansMaxans, sum /更新最大值 /以下第13至第17行，产生一个新的各列翻转方案13 jm14 While (j0) and (fj=1) do jj-115 If j0 then begin16 fj117 For kj+1 to m do fk0 endend此算法为O(n*m*2m)的，当n较大时（比如n达到20000以上），会超时。实际测试时，使用此算法的程序，会有三个点无法在1秒内出解。考虑到所有的硬币只有1（表示正面朝上）和0（表示反面朝上）两种取值，所有行和列的翻转情况也只有1（表示翻转）和0（表示不翻）两种取值，如果使用二进制数，以一个整数存储m位二进制，将程序“提速”m倍。1每一行中的所有m个硬币，看作一个m位的二进制数，则每行m个硬币可以以一个02m-1的十进制数来表示。2以0表示不翻，1表示翻转，并将m列的翻转情况看作一个m位的二进制数，则每种方案可以以02m-1的十进制数来表示。3列翻转方案的描述 如某行的硬币为(0000001001)2=9，列翻转方案为(0000011110)2=30(第6，7，8，9四列翻转)，则按列方案翻转后该行成为(0000010111)2=23,此时只要做一下9 xor 30即可。4按行翻转，对于某行的硬币，按列方案翻转后十进制值为x，则按行翻转后，十进制值为2m-1-x。5可以预先求得0，1，2，1023各数中的1的个数（即正面朝上硬币数），使用时查表即可。【算法2】1、求得01023中1的个数保存在f0.1023中;2、将输入数据转换成n个十进制数a1.n，每行一个3、ans0;4、for j0 to 2m-1 do begin /穷举列翻转方案5、 sum06、 for k1 to n do begin/扫描行7、 xak xor j;/按各列方案j翻转8、 sumsum+Maxfx,f2m-1-x/累加第k行翻与不翻中较大者 end;9、 if anssum then anssum end;10、输出ans 使用二进制优化后的算法2，复杂度成功地降为了O(n*2m)，对最坏情况下的数据，也能在1秒内出解。例四：费解的开关（试题来源：vijos1197）【问题描述】25盏灯排成一个55的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。现在给你n(1n500)个游戏的初始状态，如果某个状态能在6步以内使所有的灯都变亮，输出最少步数，否则输出-1。【问题分析】求最少步数，使用宽搜。因为n个状态的目标状态是相同的，可以考虑从目标状态逆向宽搜出所有状态，再作n次查找，找到的输出对应的最少步数，找不到则输出-1。1状态描述 有55共25盏灯，它们都以0或1表示。把这25个0或1以行优先的次序，组成一个25位的二进制数，则每个状态对应一个0至225-1=33554431的一个整数。如下图所示，第1行的第1、3、5列，第2行的第3列，第3行的第1列，共5盏灯关着，其余20盏灯开的状态，可以使用数字(1111111111111101101101010)2=(33553258)10表示。1234567891011121314151617181920212223242501010110110111111111111111111111111111101101101010第1位第2位第3位第2位第25位下面计算总的状态数。最多改变状态6次，如果有某2次作用在同一盏灯，则相当于这2次不起作用了。(1) 所有6次作用于不同灯，产生状态数C(25,6)= 177100;(2) 6次作用中，有2次相互抵销不起作用，只有4次起作用，产生状态数C(25,4)= 12650;(3) 6次作用中，有4次相互抵销不起作用，只有2次起作用，产生状态数C(25,2)= 300; 合计状态数= 177100+ 12650+300+1=190051。 于是，可以使用一个大小为999983的哈希表保存所有的状态，哈希函数采用关键码mod 999983，采用最简单的线性探测解决冲突。因为哈希表的总容量约为状态数的5倍，可以近似的认为，每次查找和插入哈希表，耗时O(1)。2在25个变化规则作用下，状态的改变(1) 改变第1盏灯时，同时改变第2和第6盏灯的状态，此时，只要将原状态与二进制数0000000000000000000100011作异或运算即可。该二进制数即十进制数20+21+25。(2) 改变第5盏灯时，同时改变第4和第10盏灯的状态，此时，只要将原状态与二进制数0000000000000001000011000作异或运算即可。该二进制数即十进制数23+24+29。(3) 改变第21盏灯时，同时改变第16和第22盏灯的状态，此时，只要将原状态与二进制数0001100001000000000000000作异或运算即可。该二进制数即十进制数215+220+221。(4) 改变第25盏灯时，同时改变第20和第24盏灯的状态，此时，只要将原状态与二进制数1100010000000000000000000作异或运算即可。该二