《算法合集之《浅谈信息学竞赛中的“0”和“1”》》由会员分享，可在线阅读，更多相关《算法合集之《浅谈信息学竞赛中的“0”和“1”》（29页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 29 页浅谈信息学竞赛中的浅谈信息学竞赛中的浅谈信息学竞赛中的浅谈信息学竞赛中的“0 0 0 0”和和和和“1 1 1 1”二进制思想在信息学竞赛中的应用二进制思想在信息学竞赛中的应用二进制思想在信息学竞赛中的应用二进制思想在信息学竞赛中的应用河北省石家庄二中河北省石家庄二中河北省石家庄二中河北省石家庄二中武森武森武森武森前言前言前言前言在德国图灵根著名的郭塔王宫图书馆（SchlossbiliothkezuGotha）保存着一份弥足珍贵的手稿，其标题为：“1 与 0，一切数字的神奇渊源。这是造物的秘密美妙的典范，因为，一切无非都来自上帝。”众所周知，二进制是计算技术中广泛采用的
2、一种数制,现代的电子计算机技术全部采用的是二进制，因为它只使用 0、1 两个数字符号，非常简单方便，易于用电子方式实现。计算机内部处理的信息，都是采用二进制数来表示的。二进制（Binary）数用 0和 1 两个数字及其组合来表示任何数。进位规则是“逢 2 进 1”，数字 1 在不同的位上代表不同的值，按从右至左的次序，这个值以二倍递增。除了数值外，英文字母、符号、汉字、声音、图象等数据在计算机内部也采用二进制数的形式来编码。目前最常用的是使用国际标准代码 ASCII 码（美国标准信息交换码）。二进制思想在信息学竞赛中也有广泛的应用。本文通过几个例子，总结了二进制思想在信息学竞赛中的应用。关键字
3、关键字关键字关键字二进制 十进制 树状数组 状态压缩 01 二叉树第 2 页 共 29 页正文正文正文正文第一章：二进制思想在数据结构中的应用第一章：二进制思想在数据结构中的应用例题一：例题一：MatrixMatrix提供一个 M*N的矩阵，其中每一个格子中的数不是 1 就是0，初始时每一个格子的值为0，我们可以修改这个矩阵中的数字，每次给出矩阵的左上角坐标(x1,y1)，以及右下角的坐标(x2, y2)，并且将矩阵中的数字全部取反（原来是 1 现在变成0，原来是0 现在变成1）,还可以每次查询第 x 行第 y 列的格子中的数字是什么。分析：根据这个题目中介绍的这个矩阵中的数的特点不是 1 就
4、是0，这样我们只需记录每个格子改变过几次，即可判断这个格子的数字。 第一步第一步我们不妨把这道题目简化一下， 假定题目中给定的是长度为 N 的一列格子 。d第 3 页 共 29 页这样，这道题目就变得简单了。每次修改的时候，给定一个格子修改的范围，这样我们不妨()yx,把这个范围变成两个点,一个为更改的初始节点 ，另一个为更改的x终止节点，然后往这列格子中的这两个节点中加1。1+y每次询问 的时候只需计算出这样就可以求出第 个x=xiixdSum1x格子被修改过几次，输出的答案就是。xSummod2通过以上的方法，我们用一般的数据结构就可使得插入的复杂度第 4 页 共 29 页为，查询的复杂度
5、为。()NOlog()NOlog这样一维的问题我们就完美的解决了！ 第二步第二步我们已经解决了一维的问题， 接下来我们就可以看看题目中的二维情况。我们能不能用上面的方法解决这一道题目呢？通过分析我们只改变两个格子的数字保证不了要求的性质(只改变矩阵中的数字而不改变其他的数字)，由于一维的时候，我们加的两个点实际上给改变的区间定了一个范围，那么二维的情况，我们也给它设定一个范围，加上四个格子每次插入的时候往这四个格子中() () () ()1, 1,1, 1,22211211+yxyxyxyx加1。查询的时候输出即可。()yx,=yjxijijiyxdSum,0,0,第 5 页 共 29 页这样
6、做是否正确呢？证明证明：假设：插入四个值，查询() () () ()1, 1,1, 1,22211211+yxyxyxyx。不妨分类讨论：()ba,如上图所示。当属于第1、2、3、4 或 7 这五个区域时，计算不受插()ba,baSum,入的影响；当属于第 5 个区域时，会受到的影响，()ba,baSum,()11,yxbaSum,相比以前会增加1，这个更改是正确的。当属于第 6 个区域时，会受到的影响，()ba,baSum,() ()1211, 1,yxyx+第 6 页 共 29 页相比以前会增加2，答案是mod2，结果不受影响，这个baSum,baSum,更改是正确的。当属于第 8 个区域
7、时，会受到的影响，()ba,baSum,() ()1,2111+yxyx相比以前会增加2，答案是mod2，结果不受影响，这个baSum,baSum,更改是正确的。当属 于 第9个 区 域 时 ，会 受 到()ba,baSum,的影响，相比以前会增加4，() () () ()1, 1,1, 1,22211211+yxyxyxyxbaSum,答案是mod2，结果不受影响，这个更改是正确的。baSum,证明完毕。通过证明我们发现以上的方法是正确的。 第三步第三步那么二维的可以解决，三维的呢？N 维的呢？根据上面的方法，我们不难想到，如果是三维的话，应该在长方体的周围加入 8 个点，N 维的情况，应该
8、在 N 维图形周围加入个点n2来处理这些情况。统计即可。niiiSum.,21 第四步第四步这道题的方法我们已经很明确了，要用到数据结构来解决，但是用线段树等数据结构的话，如果推广到二维或者三维，可能写起来就相当复杂，并且出错的概率相当大，那么有没有一个写起来既简单快捷又易推广的数据结构呢？树状数组！ ！ ！第 7 页 共 29 页树状数组就是二进制思想的经典应用。树状数组中的每一个元素的编号变成了二进制编码，如：，再通过这些二进制编码末尾的 0 的个数来决定存储什么2)1011(11=信息，假设节点编号为 x，那么这个节点存储数据的区间为（其k2中 k 为 x 二进制末尾 0 的个数）个元素
9、。因为这个区间最后一个元素必然为,这个区间存储的数据为。xA.12nAnAk+算出 2k 可以直接运用位运算：插入或删除操作就可以写成查询操作就可以写成这样，插入、删除和查询的最坏时间复杂度为 O(logN)，丝毫不逊色与其它数据结构。证明证明：2k：X and XWhile x0 doBeginSum:=sum+cx;X:=x-(x andx);End;第 8 页 共 29 页X-（x and x）这一步实际上等价于将 x 的二进制的最后一个 1 减去。而 x 的二进制里最多有 log(n)个 1，所以查询效率是 log(n)。至于修改，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一
10、个元素，最多有 log(n)的祖先。所以修改效率是log(n)。证明完毕。总结：总结：在数据结构中的运用二进制思想，创造出了一种新的数据结构树状数组。其思想核心在于运用了十进制数与二进制数之间的联系，通过数的二进制形式来决定储存信息，把复杂的问题简单化,方法简单巧妙。树状数组的优势在于代码长度短，不易出错，思想巧妙，算法复杂度低，维护简单，易推广到二维甚至三维等等。对于数据结构要求操作不复杂的题目，是上佳的选择。第二章：二进制思想在解题思路中的应第二章：二进制思想在解题思路中的应用第 9 页 共 29 页例题二：例题二：SudokuSudoku数独盘面是个九宫，每一宫又分为九个小格。在这八十一
11、格中给出一定的已知数字，利用逻辑和推理，在其他的空格上填入 1-9 的数字。使 1-9 每个数字在每一行、每一列和每一宫中都只出现一次。分析： 第一步第一步这是一道经典的数独题目，通过给定的数字进行分析和排除，算出其他格子的数字。一种比较容易想到的做法,按照顺序枚举格子中的数，进行搜索，直到搜完为止。但是数独中的数字排列千变万化，那么究竟有多少种终盘的数字组合呢？6,670,903,752,021,072,936,960（约有 6.6710的 21 次方）种组合，单凭这样简单的搜索是不可能完成的。 第二步第二步第 10 页 共 29 页我们需要非常有效的剪枝来提高搜索效率。把每一个空格子可能放
12、的数字记录到表格中，把可能性唯一的数字进行填充，然后按可能放的数的个数进行排序，按可能的个数从小到大进行搜索，每次搜索到一个格子的时候，随机选择的一个可以放得数字填到空格中，并继续进行搜索，但是在实现起来相当困难，每次填一个数字后，该格子所在的行、列以及 3*3的格子，可以填的数字个数都得修改，修改完了还需要排序，并且写完之后，结果发现还是 TLE! 第三步第三步应用二进制思想，把状态进行状态压缩，将每一个格子想象成一个 9 位的二进制数，使第 1 位第 9 位，分别表示数字 19是否能放，每个数位上用 0 或 1 来表示，0 表示这个数字可以放，1 表示这个数字不能放。这样就把每个格子表示成
13、 0511 中的一个数，这样每次搜索的时候，就直接枚举一个数字，通过位运算计算出这行、列以及 3*3 的块中是否可放即可，通过这样的状态压缩，不用其它的剪枝就可以解决这道题目了。当然再加上按可能放的数的个数进行排序，按可能的个数从小到大进行搜索之类的优化可以很完美的解决这道题目！例题三：例题三：RequirementsRequirements第 11 页 共 29 页给定 N(1 =N= 100000)个五维的点，求两个()54321,xxxxxA点和，使得他们的哈密顿距离（即()54321,xxxxxX()54321,yyyyyY）最大。5544332211yxyxyxyxyx+分析：分析：
14、 第一步第一步显然，暴力枚举的 O(N2)的算法会超时，那么怎么办呢？通过读题，我们发现维数远远小于点数，这个信息有用吗？我们不妨先分析一下这个问题的退化版本。我们先来看看给定的是 N 个一维点，那么算法很明显，只需扫描一边，记录下最大值、最小值即可得出答案。但是，我们还没有看到这道题目的本质。我们来分析一下如果是 N 个二维的点，那么我们可以怎么用较快的方法求出的解呢？()jjiiyxyx+max通过简单的数学变形，我们可以得到这样的数学公式：第 12 页 共 29 页()()()()()()()()+=+=+jjiijjiijjiijjiijjiijjiijjiijjiijjiiyxyxy
15、xyxyxyxyxyxyxyxyxyxyxyxyxyxyxyx,max,max通过观察，我们发现每一对相同元的符号必定相反，如：，于是我们有了一个二进制思想的思路，那就是枚举这些二iiyx维的点的 x 轴 y 轴前的正负号，这样就可以用一个 03 的数的二进制形式来表示每个元素前面的正负号，如：号表示号，表示+012 表示的二进制位形式为表示。 这样我们就可以通过 22*N210jixx次记录下这些二元组的不同的符号的数值，对于每个二进制来表示的不同的式子只需记录下他们的值，这样我们只需求iminmax和i出这些相同的二进制表示的式子，最后我们就可以解出iiminmax这个问题的解：=2211
16、00minmaxminmaxminmaxmaxAns但是这个解对吗？证明：证明：首先，我们要证明如下公式的正确性,第 13 页 共 29 页()()()()()()()()+=+=+jjiijjiijjiijjiijjiijjiijjiijjiijjiiyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyx,max,max设，。iiyxa=jjyxb=若0=ba不妨设.0=a则bbba=+当时，成立。0bbbb=当时，i 成立。0ba不妨设baba且0, 0则成立babababab+=+a若0a0, 0且则成立bababababa+=+所以公式得证。jjiijjiijjiij
17、jiijijiyxyxyxyxyxyxyxyxyyxx+=+,maxmaxmax定义集合第 14 页 共 29 页DCBAXyxyxDyxyxCyxyxByxyxAjjiijjiijjiijjii=+=+=+=+=改变搜索最大值的顺序XDCBAyxyxyxyxyxyxyxyxjjiijjiijjiijjiimaxmax,max,max,maxmax,maxmax=+命题成立这样我们就完美的解决了二维情况下的问题。 第二步第二步对于二元组这个方法是正确的。对于三维的情况，通过类比的方法，可想而知方法也是正确的，那么我们可以把这个方法推广到三维、四维以及五维中（要求 2dN，d 为维数），这样这道
18、题目我们就完美的解决了！例题四：例题四：CowCow XorXor农民约翰在喂奶牛的时候被另一个问题卡住了。 他的所有N(1=N1022xiix每次维护这棵 01 树，进行插入和查询，即可得到最后的答案，这样的时间复杂度为 O(NlogN).这样就可以完美的解决这道题目了！第 19 页 共 29 页总结总结总结总结本文通过几个例子说明了二进制思想在信息学竞赛中的应用。在数据结构中，不仅巧妙地设计出了一种新的数据结构，而且既操作简单，应用方便，又时间空间复杂度不逊色于其他任何数据结构，更是把数据结构难于向多维拓展成为可能。 树状数组在信息学竞赛中已经占有了一席地位。在解题中，将二进制思想引入，运
19、用十进制数与二进制数之间的关系，不仅可以用于状态压缩，还可以用与构建新的数学模型，不仅可以优化算法，还可以降低编程的复杂度。从而达到转十为二，事半功倍的效果！所以说，二进制的方法不仅仅可以使算法得到优化，更是一种解题思想。参考文献参考文献参考文献参考文献1. 算法艺术与信息学竞赛 ，刘汝佳、黄亮著，清华大学出版社，2004 年 1 月第一版第 20 页 共 29 页2. Peking University Judge Online http:/ ZheJiang University Judge Online http:/ USA Computing Olympiad http:/ an N*
20、N matrixA,whose elements are either0or 1. Ai,jmeansthe number in the i-th row and j-th column. Initially we have Ai,j=0(1=i,j= N).Wecan changethematrix inthefollowing way. Givenarectangle whoseupper-left corneris(x1, y1) and lower-right corneris(x2, y2),wechangeall theelements intherectangle by usin
21、g not operation (ifit is a0 thenchangeitinto 1 otherwise changeitinto 0).Tomaintaintheinformationofthematrix, youareaskedtowriteaprogramtoreceive and execute twokinds ofinstructions.第 21 页 共 29 页1.Cx1 y1 x2 y2 (1 = x1 = x2 =n,1= y1 = y2 = n) changesthematrix by usingtherectangle whose upper-left cor
22、neris(x1, y1) andlower-right corneris(x2, y2).2.Q x y(1 =x,y= n) querys Ax, y.InputInputInputInputThe first line oftheinputisan integerX(X = 10) representingthenumber oftestcases. ThefollowingXblocks each representsatest case.The first line of each block contains two numbersNandT(2 =N=1000,1=T= 5000
23、0) representingthesize ofthematrix andthenumber oftheinstructions. The followingTlines each represents aninstruction havingtheformat Qxy orC x1 y1 x2 y2, which has beendescribed above.OutputOutputOutputOutputFor each querying output one line, which has an integer representing Ax,y.Thereis ablank lin
24、e between every two continuous test cases.SampleSampleSampleSample InputInputInputInput1第 22 页 共 29 页2 10C 2 1 2 2Q 2 2C 2 1 2 1Q 1 1C 1 1 2 1C 1 2 1 2C 1 1 2 2Q 1 1C 1 1 2 1Q 2 1SampleSampleSampleSample OutputOutputOutputOutput1001SourceSourceSourceSourcePOJMonthly,LouTiancheng第 23 页 共 29 页例题二原题：例题
25、二原题：SudokuSudokuSudokuSudokuDescriptionDescriptionDescriptionDescriptionIn the game ofSudoku, you are givenalarge99grid divided intosmaller33subgrids. For example,Given some of the numbers in the grid, your goalisto determine theremaining numbers such that the numbers1through9appear exactlyonce in (
26、1) each of nine33subgrids, (2) eachof the nine rows, and (3)each ofthe nine columns.2 7 3 8.1.1.6 7 3 5.2 93.5 6 9 2.8.6.1 7 4 5.36 4.9 5 1 8.7.8.6 5 3 4.第 24 页 共 29 页InputInputInputInputThe input testfilewillcontain multiple cases. Each testcase consists ofasingle line containing 81 characters, whi
27、ch represent the 81 squares of theSudoku grid, given one rowat atime. Each characteriseitheradigit(from1to 9) oraperiod (usedto indicate an unfilled square). You mayassume that each puzzle in the inputwillhave exactly one solution. Theend-of-fileisdenoted byasingle line containing the word“end”.Outp
28、utOutputOutputOutputFor eachtest case, printaline representing the completed Sudoku puzzle.SampleSampleSampleSample InputInputInputInput.2738.1.1.6735.293.5692.8.6.1745.364.9518.7.8.6534.52.8.4.3.9.5.1.6.2.7.3.6.1.7.4.3.endSampleSampleSampleSample OutputOutputOutputOutput5273894168194267354367518293
29、75692184194538267268174593643217958951843672782965341第 25 页 共 29 页416837529982465371735129468571298643293746185864351297647913852359682714128574936SourceSourceSourceSourceStanford Local2006例题三原题：例题三原题：RequirementsRequirementsRequirementsRequirementsTime Limit:5SecondsMemory Limit: 32768 KBAn undergr
30、aduate student, realizing that he needs to doresearch to improve his chances of being accepted to graduateschool, decided thatit isnow time to do some independentresearch. Of course, he has decided to do research in the mostimportant domain: the requirements he must fulfill to graduate fromhis under
31、graduate university. First, he discovered (to his surprise)that he has to fulfill5distinct requirements: the general instituterequirement, the writing requirement, the science requirement, theforeign-language requirement, and the field-of-specializationrequirement. Formally,arequirementis afixed num
32、ber of classes第 26 页 共 29 页that he has to take during his undergraduate years. Thus, forexample, the foreign language requirement specifies that thestudent has to take4classes to fulfill this requirement: FrenchI,French II, French III, and French IV. Having analyzed the immensemultitude of the class
33、es that need to be taken to fulfill the differentrequirements, our student becamealittle depressed about hisundergraduate university: there are so many classes to take.Dejected, the student began studying the requirements of otheruniversities that he might have chosen after high school. He foundthat
34、, in fact, otheruniversities had exactly the same5requirements as his own university. The only difference was thatdifferent universities had different number of classes to be satisfiedin each of the five requirement.Still,itappeared that universities have pretty similarrequirements (all of them requ
35、irealot of classes), so hehypothesized that no two universities are very dissimilar in theirrequirements. He defined the dissimilarity of two universitiesXandY as|x1-y1| + |x2-y2| + |x3-y3| + |x4-y4| + |x5-y5|, where anxi(yi)isthe number of classes in the requirementiof universityX(Y) multiplied by
36、an appropriate factorthat measures hardness ofthe corresponding requirement at the correspondinguniversity.第 27 页 共 29 页InputInputInputInputThere are several test cases. The first line of each case containsan integern(1 =N= 100000), the number of considereduniversities. The followingNlines each desc
37、ribe the requirementsofauniversity.AuniversityX isdescribed by the five non-negativereal numbers x1 x2 x3 x4 x5. The input ends up withacaseN=0OutputOutputOutputOutputFor each test case, onasingle line, print the dissimilarity valueof the two most dissimilar universities. Your answer should berounde
38、d to exactly two decimal places.SampleSampleSampleSample InputInputInputInput32 5 6 21.51.23 2 5 47 5 3 2 50SampleSampleSampleSample OutputOutputOutputOutput12.80第 28 页 共 29 页Source: MITMITMITMIT ProgrammingProgrammingProgrammingProgramming Contest,Contest,Contest,Contest, 2005.02.262005.02.262005.0
39、2.262005.02.26例题四原题：CowCowCowCow XORXORXORXORAdrian Vladu-2005Farmer Johnisstuck with another problem while feeding his cows.AllofhisN(1 N 100,000) cows (numbered 1.N) are lined up in front ofthe barn, sorted by their rank in their social hierarchy. Cow #1 has thehighest rank; cow#N has the least ra
40、nk. Every cow had additionally beenassignedanon-unique integer number in the range 0.(221-1).Help FJchoosewhich cowswillbe fed first byselectingasequence ofconsecutive cows in the line such that the bitwise xor between theirassigned numbers has the maximum value.Ifthere are severalsuchsequences, cho
41、osethe sequence forwhich itslastcowhas the highestrank.Iftherestill is atie, choose the shortest sequence.PROGRAMPROGRAMPROGRAMPROGRAMNAME:NAME:NAME:NAME: cowxorcowxorcowxorcowxorINPUTINPUTINPUTINPUT FORMATFORMATFORMATFORMATLine1:Asingle integerN第 29 页 共 29 页Lines 2.N+1:Nintegers ranging from0 to 22
42、1-1,representingthecows assigned numbers. Linejdescribes cow ofsocialhierarchyj-1.SAMPLESAMPLESAMPLESAMPLE INPUTINPUTINPUTINPUT (file(file(file(file cowxor.in)cowxor.in)cowxor.in)cowxor.in)510542INPUTINPUTINPUTINPUT DETAILS:DETAILS:DETAILS:DETAILS:Thereare 5cows. Cow #1 hadbeenassigned with 1; cow #
43、2 with 0; cow#3with 5; cow #4with 4; cow#5 with 2.OUTPUTOUTPUTOUTPUTOUTPUT FORMATFORMATFORMATFORMATLine1:Three space-separated integers,respectively:themaximumrequested value,theposition wherethesequence begins,theposition wherethesequence ends.SAMPLESAMPLESAMPLESAMPLE OUTPUTOUTPUTOUTPUTOUTPUT (file(file(file(file cowxor.out)cowxor.out)cowxor.out)cowxor.out)6 4 5OUTPUTOUTPUTOUTPUTOUTPUT DETAILS:DETAILS:DETAILS:DETAILS:4xor2=6(001) xor(010) = (011)
