信息学-集训队作业

浅谈特殊穷举思想的应【，分析。认为穷举是解题时的有效思想应对其给予充分的重视。对于完，【关键字穷举完全/【引言【正文穷举的思的穷举对象可以使穷举获得很高的效率（1明的打字员题目大意1（Up/Down（Left/Right换（Swap0/Swap1）六个键的键盘，用最少的步数把一个6位数转化成另外一个1234566334511123456初步分Sap0/Swap16*106是不能胜是使用搜索就只好用效率较高的Hash+A或双向广度优先这虽然可以在规定时间内出解，但是效率仍然不高，而且编程复杂度很高。思考：使用穷举思，表面看来不能这样做。因为不能确定这两个键与加减1两键的使，事实上，可以看到，只要是对同一个数进行加减，Up/Down放在Swap0/Swap1前后实际上是等效的。例如，原来的数是133456，可以通过一个Up,一个Right,Swap0323456Right,Swap0,然后再用Up，也可以把它变成323456。因此，可以把任务分成两个阶段处在第2阶段中，由于已经没有了Swap0/Swap1，使问题大大简化。12001年青少年信息学竞例如样例中只有1，6位置可以不用额外的Left/Right进行调整，而要带来了很大的麻烦。不过，即使把每个位置能否调整的64种状态都考虑进460800.77%。完全可以接受。如果进一步分析，可以知道1这样2，3，4，5是否可能调整形成的状态只有{},{2},{2,3},{2,3,4},{2,3,4,5}6Swap1。两种解法的对比大O(720*10)常数辑岛题目大意在逻辑岛上有3种居民：说真话的神，说假话的恶魔和在白天说真话，3种Iam[not]Xis[not]Itis50。你的任务就是通过居民们说的话来判断他们的种初步分A:BisB:AisA:Bis如果由人来判断的话，A说了两句相互的话，显然这两句话都是，那BA2浙江大学评测系统AisBis，但是，当试图把这种思维方式用程序实现时发现情况非常复杂，很难，应用穷举策因为居民只有5个，而且每个居民都只有3种可能的种类，而时间也只有昼夜之35*2=486种，使用穷举完全可以接受。这就是选择的穷举对象。在穷举了每个居民的种类和时间之后只需判断输入的每句话是否符合这个小部分穷举思想——参变量基本思，落空。但是仍然有一些办法来打破这些限制。部分穷举的思想就是其中重，重要结以时间复杂度一般都是多项式级的，可以满足题目的要求。但是，有时也需那么参变量大于x1时也可行，而且题目要求的是参变量的最小值。这时，，对于一些范围比较小的题目，或者是解比较靠近边缘的题目可以使用第一，构，使划分的每一部分权值的最大值达到最小。这时候，往往采用部分题目大森林中的精灵们把这片草莓田分成k块种到k个空地中去以免被粗鲁的棕熊搞定义：sumi表示第i块草莓所有草莓重量的和（1ik）xminsumi|1ikx尽可能的大。附加的限初步分解决。首先把草莓作为树的节点。可以把某子树分成K份，所能达到k份，所能达到的最优解,nt个儿子32003年青少年信息学竞D(n,k)D(n,k)=MAX:对任意的一个k=a1+a2+… D(child2,a2),…,D(childt,at))+ni个儿子的调整值n，个儿子的调整值。要求得这一项需知道把第n个点和它的子孙节点构成k，选择参变，如果已知一个分割方案所对应的x如何去寻找一个解答，或者证明这种分，，这是使用参变量法的关键如果这个问题得以解决就可以应用部分穷x问题★的解答：动态规划或贪心，问题★事实上并不难解决。完全可以用动态规划的方法：设T(n)表示n和n的子孙分割成重量大于x的最大块数，而Left(n)表示进行这样的分割以后，所剩Left(n)0Left(n)等于所有这些重量。这样，得到状态转移方程如下如如果Left(child1)+Left(child2)+…+Left(childt)+第n株的重量≥x，那否则：T(n)=Left(n)=Left(child1)+Left(child2)+…+Left(childt)+第n株的重总体的解，这样利用参变量法解决了一个最小最大的问题。但是，如果把题目的要求，最大最小匹问题的提2的条件中，匹配边的最大权最小的匹配。x=max{匹配边的权},x最小的完备匹配。初步分而本题中的权需要取最小值，不是简单的相加关系。所以很难用网络流的方采用部分穷举的思如果已知一个x，是否可以很快产生一个满足题目要求的匹配如果解决了这个问题，那么就可以解决最大最小匹配问题。而这个问题权大于x的边都不可用。于是得到了一个不带权的二分图，如果可以在穷举方式选n2个，所以使用线形的穷举也并非不可。当然，从算法时间效率的一些扩【总结。，本文应用完全穷举和部分穷举两种穷举方法，处理了一些问题可以看出，穷举≠低效！对于完全穷举可以通过适当选取穷举对象来达到所。，好问题只要能找到参变量，总之，完全穷举和部分穷举是解题时的有效思想应对其给予充分的重，【参考文献NOI2001《图论的算法与程序设计》,吴，王建德著【附录1

，盘上没有数字键，而只有以下六个键：Swap0,Swap1,Up,Down,Left,Right，为了说明这6个键的作用先定义录入区的6个位置的，从左至右依次为，Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号Swap0键之后，录入区的数字不变；Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号Swap1键之后，录入区的数字不变；Up：按Up，光标位置不变，将光标所在位置的数字加1（除非该数字是92Up3；如果该9Up之后，数字不变，光标位置也不变；Down：按Down，光标位置不变，将光标所在位置的数字减1（除非该数字00Down之后，数字不变，光标位置也不变；Left：按Left，光标左移一个位置，如果光标已经在录入区的1号位置（左Right：按Right，光标右移一个位置如果光标已经在录入区的6号位（左现一个长度为6的初始，而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标，这时光标允许停在任何一个位置。，现在需要你的帮助，编写一个程序，求出录入一个需要的最少的，输入文件文件仅一行，含有两个长度为6的数，前者为初始，后者为目标，两个之间用一个空格隔开。输出文件输入样 输出样样例说明初始是123456，光标停在数字1上。对应上述最少击键次数的击键序（下划线表示光标所在位置1，聪明的打字员：programclever;d,f,t:array[1..6]ofswap:array[1..6of2..2;{swap0/swap1情况}procedurefori:=1to6doread(f[i]);fori:=1to6doread(d[i]);fori:=1to6doswap[i]:=-2;proceduresolve;procedurepswap;{进行交换操作proceduresw(varsw1,sw2:integer);forpi:=1to6doifswap[pi]=-1thenbeginelseifswap[pi]=1thenbeginfunctionmmc:integer;while(mj>0)and(t[mj]=d[mj])and(swap[mj]=0)domj:=mj-1;if(swap[6]=0)and(mj>5)and(ys6=true)thenmj:=5;ifmj=0thenbeginwri formi:=1to6domr:=mr+abs(d[mi]-t[mi]);whilek>0dobeginifswap[k]<2thenbeginifk=6thenbeginifnmin<minthenmin:=nmin;else IslandofTimelimit:1SecondsMemorylimit:32768KTotalSubmit:84AcceptedSubmit:35TheIslandofLogichasthreekindsofinhabitants:divinebeingsthatalwayslthetruth,evilbeingsthatalwayslie,andhumanbeingsthataretruthfulduringthedayandlieatnight.Everyinhabitantrecognizesthetypeofeveryotherinhabitant.Asocialscientistwantstovisittheisland.Becauseheisnotabletodistinguishthethreekindsofbeingsonlyfromtheirlooks,heasksyoutoprovidea yzerthatdeducesfactsfromconversationsamonginhabitants.Theinterestingfactsarewhetheritisdayornightandwhatkindofbeingsthespeakersare.Theinputcontainsseveraldescriptionsofconversations.Eachdescriptionstartswithanintegern,thenumberofstatementsintheconversation.Thefollowingnlineseachcontainonestatementbyaninhabitant.Everystatementlinebegins`:'.NextisoneofthefollowingkindsofIam[not](divine|human|evil|lying).Xis[not](divine|human|evil|lying).Itis(day|night).Squarebrackets[]meanthatthewordinthebracketsmayormaynotappear,roundbrackets()meanthatexactlyoneofthealternativesseparatedby|mustappear.XstandsforsomenamefromA,B,C,D,E.Therewillbenotwoconsecutivespacesinanystatementline,andatmost50statementsinaTheinputisterminatedbyatestcasestartingwithn=Foreachconversation, outputthenumberoftheconversationintheformatshowninthesampleoutput.Thenprint``Thisisimpossible.'',iftheconversationcannothappenaccordingtotherulesor``Nofactsarededucible.'',ifnofactscanbededuced.Otherwiseprintallthefactsthatcanbededuced.Deducedfactsshouldbeprintedusingthefollowingformats:Xis(divine|human|evil).Itis(day|night).Xistobereplacedbyacapitalletterspeakername.Factsaboutinhabitantsmustbegiven (inalphabeticalorder),thenitmaybestatedwhetheritisdayorTheoutputforeachconversationmustbefollowedbyasingleblankSample1A:Iam1A:Iam1A:Iam3A:BisB:AisA:Bis0SampleOutputConversation#1NofactsareConversation#2Thisisimpossible.Conversation#3Aishuman.ItisConversationAisBisReasoningmadeTomakethingsclearer,wewillshowthereasoningbehindthethirdinputexample,whereAsays``Iamevil.''.Whatcanbededucedfromthis?ObviouslyAcannotbedivine,since dbelying,similarlyAcannotbeevil,sincedlthetruth.Therefore,Amustbehuman,moreover,sincesheislying,itmustbenight.Sothecorrectoutputisasshown.Inthefourthinputexample,itisobviousthatAislyingsincehertwostatementsdivine.Balwayslsthetruth,thusAmustbeevil.Voil‘a!2，逻辑岛{comment:ZJU1252islandoflogic}typ:integer;{0-sb.issth.;1-sb.islying;2-It'sday/night}tp:array[1..5]ofinteger;st:array[1..50]ofsentence;lying:array[1..5]ofboolean;fact:array[1..5]ofinteger;{-1-unknown;0,1,2-seeabove;3-uncertain}procedureoutp;iffact[1]=-1thenwri n('Thisisimpossible.')elsebeginfori:=1to5 ffact[i]<>3thenbeginwrite(chr(i+64),'is');casefact[i] ifrtime<2thenifrtime=0then n('Itisday.')else n('It

ifnfact=0thenwri n('Nofactsarededucible.');procedurecombineresult;fori:=1to5iffact[i]=-1thenelseiffact[i]<>tp[i]thenfact[i]:=3;ifrtime=-1thenbeginifdaythenrtime:=0elsertime:=1;elseif(rtime=0)xordaythenrtime:=2;functioncheckt(ts:sentence):boolean;ifts.typ=0then elsecheckt:=falsexorlying[ts.speaker];elseifts.typ=1then elsecheckt:=falsexorlying[ts.speaker];elsecheckt:=not(dayxorts.isnotxorlying[ts.speaker]);functioncheck:boolean;fori:=1ton fnotcheckt(st[i])thenbeginprocedurenumber2st;iftnum>=243thenbeginelsefori:=1to5dobegintp[i]:=tnummod3;tnum:=tnumdiv3;fori:=1to5iftp[i]=0thenelseiftp[i]=2thenlying[i]:=falseelselying[i]:=notday;procedureinit;fori:=1tondobeginifpos('not',s)<>0thenst[i].isnot:=trueelsest[i].isnot:=false;ifcopy(s,1,4)='Iam'thenst[i].sb:=st[i].speakerelseifcopy(s,1,5)='Itis'thenst[i].typ:=3elsest[i].sb:=ord(s[1])-64;ifcopy(s,length(s)-3,4)='evil'thenelseifcopy(s,length(s)-4,5)='human'thenst[i].sth:=1elseifcopy(s,length(s)-5,6)='divine'thenst[i].sth:=2elseifcopy(s,length(s)-4,5)='lying'thenst[i].typ:=1elseifcopy(s,length(s)-4,5)='night'thenst[i].isnot:=falseelsest[i].isnot:=true;fornumber:=0to485dobeginifcheckthencombineresult;【题目背景。就会感到孤单，所以精灵们希望无论哪块空地含有草莓的总重量都不要太小天真的精。【任务描述定义：sumi表示第i块草莓所有草莓重量的和（1ik）kx尽可能的大。【输入说明n、mk，n表示草莓的株数，m表示触须的数目，knibiibimpqpqd【输出说明每行表示一块草莓田每行的第一个整数为ni，表示第i块的草莓株数第二个到第ni+1个整数为这些草莓的。请注意，这些草莓必然是通过触须相连接的。【输入样例79771646【输出样例72122345【评分方法102/berry1.in~2/berry10.in提交你的输出文件

放在你的选 下Yes的时候，你的输出才可以确认是可接受的。这里d为评分系数（输入数据中最后一行的整数），best为的最优结果。【你如何测试自己的输2/berry_check这个工具来测试你的输出文件是否是可接受的。使用这个工2/berry_check输入文件名输出文件名在你调用这个程序后，2/berry_check将根据你给出的输入和输出文件给出测试的结notconnectanswernotmatchx{comment:NOI2003berryfortree-likedatas}enode=recordv:integer;next:Penode;end;tnode=recordvalue:longin tr:array[1..maxn]oftnode;dp:array[1..maxn]ofPenode;vis,vis2:array[1..maxn]ofboolean;outlist:array[1..maxk]ofPenode;number:array[1..maxk]ofinteger;proceduredestroy(td:Penode);{一个链表iftd<>nilthenbeginprocedureoutp;{输出 fori:=1tokdobeginwhilet<>nildobeginwrite('',t^.v); procedureclean;{初始化fori:=1tokdodestroy(outlist[i]);procedurefillout(id:integer);{划分}whilet<>nildobeginifvis[t^.v]andnotvis2[t^.v]thenfunctionscan:boolean;{贪心法处理}used:array[1..maxn]ofboolean;tsum:array[1..maxn]oflongint;fori:=maxdepdownto1dobeginwhiletn1<>nildobeginifnk=kthenelsebeginwhiletn2<>nildoifvis[tn2^.v]andnotused[tn2^.v]thenbeginiftsum[tn1^.v]>=limitthenbeginend;{ifnk=k}ifnk=kthenscan:=trueelsescan:=false;functionifhi<lothenwork:=-1elseifhi=lothenbeginiftvthenwork:=loelsework:=-1;elsemid:=(lo+hi)div2;iftvthenbeginifmid=-1thenwork:=(lo+hi)div2elsework:=mid;elsework:=work(lo,mid-1);proceduredfs(id,dep:integer);ifdep>maxdepthenmaxdep:=