算法合集之浅谈信息学竞赛中的“0”和“1”资料下载.pdf

算法合集之浅谈信息学竞赛中的“0”和“1”资料下载.pdf

《算法合集之浅谈信息学竞赛中的“0”和“1”资料下载.pdf》由会员分享，可在线阅读，更多相关《算法合集之浅谈信息学竞赛中的“0”和“1”资料下载.pdf（29页珍藏版）》请在冰点文库上搜索。

二进制思想在数据结构中的应用例题一：

例题一：

MatrixMatrix提供一个M*N的矩阵，其中每一个格子中的数不是1就是0，初始时每一个格子的值为0，我们可以修改这个矩阵中的数字，每次给出矩阵的左上角坐标（x1,y1），以及右下角的坐标（x2,y2），并且将矩阵中的数字全部取反（原来是1现在变成0，原来是0现在变成1）,还可以每次查询第x行第y列的格子中的数字是什么。

分析：

根据这个题目中介绍的这个矩阵中的数的特点不是1就是0，这样我们只需记录每个格子改变过几次，即可判断这个格子的数字。

第一步第一步我们不妨把这道题目简化一下，假定题目中给定的是长度为N的一列格子。

d第3页共29页这样，这道题目就变得简单了。

每次修改的时候，给定一个格子修改的范围，这样我们不妨（）yx,把这个范围变成两个点,一个为更改的初始节点，另一个为更改的x终止节点，然后往这列格子中的这两个节点中加1。

1+y每次询问的时候只需计算出这样就可以求出第个x=xiixdSum1x格子被修改过几次，输出的答案就是。

xSummod2通过以上的方法，我们用一般的数据结构就可使得插入的复杂度第4页共29页为，查询的复杂度为。

（）NOlog（）NOlog这样一维的问题我们就完美的解决了！

第二步第二步我们已经解决了一维的问题，接下来我们就可以看看题目中的二维情况。

我们能不能用上面的方法解决这一道题目呢？

通过分析我们只改变两个格子的数字保证不了要求的性质（只改变矩阵中的数字而不改变其他的数字），由于一维的时候，我们加的两个点实际上给改变的区间定了一个范围，那么二维的情况，我们也给它设定一个范围，加上四个格子每次插入的时候往这四个格子中（）（）（）（）1,1,1,1,22211211+yxyxyxyx加1。

查询的时候输出即可。

（）yx,=yjxijijiyxdSum,0,0,第5页共29页这样做是否正确呢？

证明证明：

假设：

插入四个值，查询（）（）（）（）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个区域时，会受到的影响，（）ba,baSum,（）（）1,2111+yxyx相比以前会增加2，答案是mod2，结果不受影响，这个baSum,baSum,更改是正确的。

当属于第9个区域时，会受到（）ba,baSum,的影响，相比以前会增加4，（）（）（）（）1,1,1,1,22211211+yxyxyxyxbaSum,答案是mod2，结果不受影响，这个更改是正确的。

baSum,证明完毕。

通过证明我们发现以上的方法是正确的。

第三步第三步那么二维的可以解决，三维的呢？

N维的呢？

根据上面的方法，我们不难想到，如果是三维的话，应该在长方体的周围加入8个点，N维的情况，应该在N维图形周围加入个点n2来处理这些情况。

统计即可。

niiiSum.,21第四步第四步这道题的方法我们已经很明确了，要用到数据结构来解决，但是用线段树等数据结构的话，如果推广到二维或者三维，可能写起来就相当复杂，并且出错的概率相当大，那么有没有一个写起来既简单快捷又易推广的数据结构呢？

树状数组！

第7页共29页树状数组就是二进制思想的经典应用。

树状数组中的每一个元素的编号变成了二进制编码，如：

，再通过这些二进制编码末尾的0的个数来决定存储什么2）1011（11=信息，假设节点编号为x，那么这个节点存储数据的区间为（其k2中k为x二进制末尾0的个数）个元素。

因为这个区间最后一个元素必然为,这个区间存储的数据为。

xA.12nAnAk+算出2k可以直接运用位运算：

插入或删除操作就可以写成查询操作就可以写成这样，插入、删除和查询的最坏时间复杂度为O（logN），丝毫不逊色与其它数据结构。

2k：

XandXWhilex0doBeginSum:

=sum+cx;

X:

=x-（xandx）;

End;

第8页共29页X-（xandx）这一步实际上等价于将x的二进制的最后一个1减去。

而x的二进制里最多有log（n）个1，所以查询效率是log（n）。

至于修改，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log（n）的祖先。

所以修改效率是log（n）。

证明完毕。

总结：

在数据结构中的运用二进制思想，创造出了一种新的数据结构树状数组。

其思想核心在于运用了十进制数与二进制数之间的联系，通过数的二进制形式来决定储存信息，把复杂的问题简单化,方法简单巧妙。

树状数组的优势在于代码长度短，不易出错，思想巧妙，算法复杂度低，维护简单，易推广到二维甚至三维等等。

对于数据结构要求操作不复杂的题目，是上佳的选择。

第二章：

二进制思想在解题思路中的应第二章：

二进制思想在解题思路中的应用第9页共29页例题二：

例题二：

SudokuSudoku数独盘面是个九宫，每一宫又分为九个小格。

在这八十一格中给出一定的已知数字，利用逻辑和推理，在其他的空格上填入1-9的数字。

使1-9每个数字在每一行、每一列和每一宫中都只出现一次。

第一步第一步这是一道经典的数独题目，通过给定的数字进行分析和排除，算出其他格子的数字。

一种比较容易想到的做法,按照顺序枚举格子中的数，进行搜索，直到搜完为止。

但是数独中的数字排列千变万化，那么究竟有多少种终盘的数字组合呢？

6,670,903,752,021,072,936,960（约有6.6710的21次方）种组合，单凭这样简单的搜索是不可能完成的。

第二步第二步第10页共29页我们需要非常有效的剪枝来提高搜索效率。

把每一个空格子可能放的数字记录到表格中，把可能性唯一的数字进行填充，然后按可能放的数的个数进行排序，按可能的个数从小到大进行搜索，每次搜索到一个格子的时候，随机选择的一个可以放得数字填到空格中，并继续进行搜索，但是在实现起来相当困难，每次填一个数字后，该格子所在的行、列以及3*3的格子，可以填的数字个数都得修改，修改完了还需要排序，并且写完之后，结果发现还是TLE!

第三步第三步应用二进制思想，把状态进行状态压缩，将每一个格子想象成一个9位的二进制数，使第1位第9位，分别表示数字19是否能放，每个数位上用0或1来表示，0表示这个数字可以放，1表示这个数字不能放。

这样就把每个格子表示成0511中的一个数，这样每次搜索的时候，就直接枚举一个数字，通过位运算计算出这行、列以及3*3的块中是否可放即可，通过这样的状态压缩，不用其它的剪枝就可以解决这道题目了。

当然再加上按可能放的数的个数进行排序，按可能的个数从小到大进行搜索之类的优化可以很完美的解决这道题目！

例题三：

RequirementsRequirements第11页共29页给定N（1=N=100000）个五维的点，求两个（）54321,xxxxxA点和，使得他们的哈密顿距离（即（）54321,xxxxxX（）54321,yyyyyY）最大。

5544332211yxyxyxyxyx+分析：

第一步第一步显然，暴力枚举的O（N2）的算法会超时，那么怎么办呢？

通过读题，我们发现维数远远小于点数，这个信息有用吗？

我们不妨先分析一下这个问题的退化版本。

我们先来看看给定的是N个一维点，那么算法很明显，只需扫描一边，记录下最大值、最小值即可得出答案。

但是，我们还没有看到这道题目的本质。

我们来分析一下如果是N个二维的点，那么我们可以怎么用较快的方法求出的解呢？

（）jjiiyxyx+max通过简单的数学变形，我们可以得到这样的数学公式：

第12页共29页（）（）（）（）（）（）（）（）+=+=+jjiijjiijjiijjiijjiijjiijjiijjiijjiiyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyx,max,max通过观察，我们发现每一对相同元的符号必定相反，如：

，于是我们有了一个二进制思想的思路，那就是枚举这些二iiyx维的点的x轴y轴前的正负号，这样就可以用一个03的数的二进制形式来表示每个元素前面的正负号，如：

号表示号，表示+012表示的二进制位形式为表示。

这样我们就可以通过22*N210jixx次记录下这些二元组的不同的符号的数值，对于每个二进制来表示的不同的式子只需记录下他们的值，这样我们只需求iminmax和i出这些相同的二进制表示的式子，最后我们就可以解出iiminmax这个问题的解：

=221100minmaxminmaxminmaxmaxAns但是这个解对吗？

证明：

首先，我们要证明如下公式的正确性,第13页共29页（）（）（）（）（）（）（）（）+=+=+jjiijjiijjiijjiijjiijjiijjiijjiijjiiyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyx,max,max设，。

iiyxa=jjyxb=若0=ba不妨设.0=a则bbba=+当时，成立。

0bbbb=当时，i成立。

0ba不妨设baba且0,0则成立babababab+=+a若0a0,0且则成立bababababa+=+所以公式得证。

jjiijjiijjiijjiijijiyxyxyxyxyxyxyxyxyyxx+=+,maxmaxmax定义集合第14页共29页DCBAXyxyxDyxyxCyxyxByxyxAjjiijjiijjiijjii=+=+=+=+=改变搜索最大值的顺序XDCBAyxyxyxyxyxyxyxyxjjiijjiijjiijjiimaxmax,max,max,maxmax,maxmax=+命题成立这样我们就完美的解决了二维情况下的问题。

第二步第二步对于二元组这个方法是正确的。

对于三维的情况，通过类比的方法，可想而知方法也是正确的，那么我们可以把这个方法推广到三维、四维以及五维中（要求2dN，d为维数），这样这道题目我们就完美的解决了！

例题四：

CowCowXorXor农民约翰在喂奶牛的时候被另一个问题卡住了。

他的所有N（1=N1022xiix每次维护这棵01树，进行插入和查询，即可得到最后的答案，这样的时间复杂度为O（NlogN）.这样就可以完美的解决这道题目了！

第19页共29页总结总结总结总结本文通过几个例子说明了二进制思想在信息学竞赛中的应用。

在数据结构中，不仅巧妙地设计出了一种新的数据结构，而且既操作简单，应用方便，又时间空间复杂度不逊色于其他任何数据结构，更是把数据结构难于向多维拓展成为可能。

树状数组在信息学竞赛中已经占有了一席地位。

在解题中，将二进制思想引入，运用十进制数与二进制数之间的关系，不仅可以用于状态压缩，还可以用与构建新的数学模型，不仅可以优化算法，还可以降低编程的复杂度。

从而达到转十为二，事半功倍的效果！

所以说，二进制的方法不仅仅可以使算法得到优化，更是一种解题思想。

参考文献参考文献参考文献参考文献1.算法艺术与信息学竞赛，刘汝佳、黄亮著，清华大学出版社，2004年1月第一版第20页共29页2.PekingUniversityJudgeOnlinehttp:

/UniversityJudgeOnlinehttp:

/ComputingOlympiadhttp:

/anN*NmatrixA,whoseelementsareeither0or1.Ai,jmeansthenumberinthei-throwandj-thcolumn.InitiallywehaveAi,j=0（1=i,j=N）.Wecanchangethematrixinthefollowingway.Givenarectanglewhoseupper-leftcorneris（x1,y1）andlower-rightcorneris（x2,y2）,wechangealltheelementsintherectanglebyusingnotoperation（ifitisa0thenchangeitinto1otherwisechangeitinto0）.Tomaintaintheinformationofthematrix,youareaskedtowriteaprogramtoreceiveandexecutetwokindsofinstructions.第21页共29页1.Cx1y1x2y2（1=x1=x2=n,1=y1=y2=n）changesthematrixbyusingtherectanglewhoseupper-leftcorneris（x1,y1）andlower-rightcorneris（x2,y2）.2.Qxy（1=x,y=n）querysAx,y.InputInputInputInputThefirstlineoftheinputisanintegerX（X=10）representingthenumberoftestcases.ThefollowingXblockseachrepresentsatestcase.ThefirstlineofeachblockcontainstwonumbersNandT（2=N=1000,1=T=50000）representingthesizeofthematrixandthenumberoftheinstructions.ThefollowingTlineseachrepresentsaninstructionhavingtheformatQxyorCx1y1x2y2,whichhasbeendescribedabove.OutputOutputOutputOutputForeachqueryingoutputoneline,whichhasanintegerrepresentingAx,y.Thereisablanklinebetweeneverytwocontinuoustestcases.SampleSampleSampleSampleInputInputInputInput1第22页共29页210C2122Q22C2121Q11C1121C1212C1122Q11C1121Q21SampleSampleSampleSampleOutputOutputOutputOutput1001SourceSourceSourceSourcePOJMonthly,LouTiancheng第23页共29页例题二原题：

例题二原题：

SudokuSudokuSudokuSudokuDescriptionDescriptionDescriptionDescriptionInthegameofSudoku,youaregivenalarge99griddividedintosmaller33subgrids.Forexample,Givensomeofthenumbersinthegrid,yourgoalistodeterminetheremainingnumberssuchthatthenumbers1through9appearexactlyoncein

（1）eachofnine33subgrids,

（2）eachoftheninerows,and（3）eachoftheninecolumns.2738.1.1.6735.293.5692.8.6.1745.364.9518.7.8.6534.第24页共29页InputInputInputInputTheinputtestfilewillcontainmultiplecases.Eachtestcaseconsistsofasinglelinecontaining81characters,whichrepresentthe81squaresoftheSudokugrid,givenonerowatatime.Eachcharacteriseitheradigit（from1to9）oraperiod（usedtoindicateanunfilledsquare）.Youmayassumethateachpuzzleintheinputwillhaveexactlyonesolution.Theend-of-fileisdenotedbyasinglelinecontainingtheword“end”.OutputOutputOutputOutputForeachtestcase,printalinerepresentingthecompletedSudokupuzzle.SampleSampleSampleSampleInputInputInputInput.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.endSampleSampleSampleSampleOutputOutputOutputOutput527389416819426735436751829375692184194538267268174593643217958951843672782965341第25页共29页416837529982465371735129468571298643293746185864351297647913852359682714128574936SourceSourceSourceSourceStanfordLocal2006例题三原题：

例题三原题：

RequirementsRequirementsRequirementsRequirementsTimeLimit:

5SecondsMemoryLimit:

32768KBAnundergraduatestudent,realizingthatheneedstodoresearchtoimprovehischancesofbeingacceptedtograduateschool,decidedthatitisnowtimetodosomeindependentresearch.Ofcourse,hehasdecidedtodoresearchinthemostimportantdomain:

therequirementshemustfulfilltograduatefromhisundergraduateuniversity.First,hediscovered（tohissurprise）thathehastofulfill5distinctrequirements:

thegeneralinstituterequirement,thewritingrequirement,thesciencerequirement,theforeign-languagerequirement,andthefield-of-specializationrequirement.Formally,arequirementisafixednumberofclasses第26页共29页thathehastotakeduringhisundergraduateyears.Thus,forexample,theforeignlanguagerequirementspecifiesthatthestudenthastotake4classestofulfillthisrequirement:

FrenchI,FrenchII,FrenchIII,andFrenchIV.Havinganalyzedtheimmensemultitudeoftheclassesthatneedtobetakentofulfillthedifferentrequirements,ourstudentbecamealittledepressedabouthisundergraduateuniversity:

therearesomanyclassestotake.Dejected,thestudentbeganstudyingtherequirementsofotheruniversitiesthathemighthavechosenafterhighschool.Hefoundthat,infact,otheruniversitieshadexactlythesame5requirementsashisownuniversity.Theonlydifferencewasthatdifferentuniversitieshaddifferentnumberofclassestobesatisfiedineachofthefiverequirement.Still,itappearedthatuniver