搜索
构造题选讲SJTU_作战动员TankEngineer倪昊斌TRIVIALConstructorFtiaschClassUral1979:ResourcesDistribution一个n*n*n的立方体，在外表面的6n^2个面上写上1~6n^2这些数字，使得从任意格子出发向任意一个方向走一圈和都相等。Solution考虑对称性每个面和其对面一定会同时出现在某个环中1+6n^2=2+6n^2-1…VERYEASYConstructorAngryBaconClassCF226D:Thetable有一个n*m(n,m=100)的矩阵(元素绝对值=100)，每次可以将一列取负或者将一行取负，求一个方案使得每行每列的和都非负。SolutionNaivealgorithm:每次看有没有行/列和为负，如果是就reverse。和递增，一定会结束。复杂度：操作次数*nSolution每次至少使和增加2和最大100^3，最小-100^3复杂度：100^4CF468C:Hackit!求给出区间[l,r]使得区间中的数的数位之和模a为0。l,r=10^200a=10^18Solution令l=1r=10^19的数位和为s可以方便计算则l=kr=10^19+k-1的数位和为s+k-1。可构造答案AndrewStankevichContest44:H.HuffmanCodes给出n=100个哈夫曼编码当中的0/1个数，问是否存在可能的哈夫曼编码。Solution自底向上构建哈夫曼树。0和1个数之和最大且1最多的点深度最深，且一定有一个1个数少10个数多一的点和其匹配。合并两个点，得到一个新点。不断重复至构建完成或出现矛盾。CF209C:TrailsandGlades有一张无向图=10^6。加最少的边使之有欧拉回路。Solution如果图连通，那么只需把奇度点两两相连即可。如果图有k1个连通块，则至少需要k-1条边把它们先连成一个连通块。优先选取奇度点向外连。EASYConstructorArchDruidClassZOJ3823:ExcavatorContest在n*n的网格上，由边界某个格子出发四连通经过所有格子一次且仅一次再回到边界上，要求拐弯的数量至少有n*(n-1)-1次。Solutionn=2Solutionn=3Solutionn=4Solutionn=5Solutionn=6Solution沿着左边沿和下边缘走一圈，接着递归套用n-2的构造方案。走左下边沿的方案奇偶略有区别。LatviaUContest14:G.Mosaic有三种颜色的珠子各a,b,c=2^31个，给出方案铺满若干层的三角形，且每层颜色必须相同。Solution猜测：a+b+c为某个三角形数时必有解构造：每次用最多的颜色填最后一行反例：222or111Solution补丁：如果有两个2或者两个1无解n=1001trivialn=2111无解012003trivialn=3222否则必有一个=3Solutionn3设a+b+c=n(n+1)/2c=b=a由n(n+1)/23(n-1)知a=n若nb只能放a转化为n-1否则称这一列为可选择的先放aSolution若最后出现了222or111且前面存在可选择的列。找到最小的可选择的列k，则k和k-1列必然颜色不同，且交换k和k-1列的颜色必然是合法的，使之变成123或012即可。NEERC2013:K.KidsinaFriendlyClass一张图有黑点和白点，每个黑点和a条边和黑点相连b条边和白点相连，每个白点有c条边和黑点相连有d条边和白点相连。(a,b,c,d=50)求一个方案使总点数最少。Solution枚举黑点个数n。则白点有nb/c个。连黑点和白点之间的边-trivial问题转化为给一个图如何使得每个点的度数都相等。WrongSolution每次选两个剩余度最大的点相连。反例：62Solution每次选一个剩余度最大的点，将其与其余度最大的若干个点连接使其度满足要求。正确性？留给聪明的读者作为练习。可用于构造任意给定每个点度数的图。NOTHARDConstructordata_hClassUdmurtSU+IzhevskSTUcontest:J.Cranes把n个箱子从0号位置移动到m号位置。你可以使用k个机械手。每个机械手每个单位时间可以左右移动一格或不动，提起/放下箱子的时间可以忽略不计，求最短时间。n,m,k=10^6Trivial?请大家手算数据体会一下3个机械手4个箱子长度5Level0Ans=20方案：来回两趟Level1Ans=15方案：最后可以不用回去……Level2Ans=4*5/3+1=7or其他公式方案：Whatareyouthinking?反例：1机械手2个箱子长度5or其他反例Level3Ans=13方案：两个机械手直接走到5，另一个先走到4，两个到5的回去一个接好，走到4的再把另一个箱子送到5。Level4Ans=11方案：两个机械手直接送两个箱子到5，剩下一个把一个箱子运到3，再回去拿一个到5。两个机械手其中一只回到3去拿。Level5Ans=9方案：机械手A：直接到5，回到3再拿一个机械手B：先送到3，回到1再拿一个机械手C：先送到1，再回去拿一个更复杂的情况？Solution每秒对于每个机械手采取这样的贪心行动（假设机械手数量小于等于箱子数量，且先考虑离m位置较靠后的手）：1.如果有箱子在自己位置后面且没有被抓着，扔下手上的箱子，回去一步。2.否则自己当前位置必有没有抓的箱子，抓起它向前一步。Prove这样使得所有手往回走的步数最少。UfaSATU+BucharestUContest:J.ReverseSort有n=32*10^3的一个序列，每次可以reverse一个区间，代价是区间长度。在总代价不超过4*10^6的条件下sort这个序列。Solution根据给出的界的范围来考虑可能的构造≈nlog^2n重要思路：模仿快速排序进行构造Solution快排每次确定一个元素的位置，再对左右两边进行分治。构造算法每次以不超过nlogn的代价确定一个元素的位置，再对左右两边进行分治。Solution如果确定了中间元素，那么每个元素实际上只是0或者1对于一个01序列以nlogn代价进行排序。贪心：对于相连的一块0/1应一起处理Solution直接进行排序，每次交换相邻两块。10101010-01010101-00101011…复杂度n^2Solution每次交换相邻两块，但间隔一组01。10101010-01100110-00011110-00001111可见开头的0的个数呈几何增长，故复杂度nlogn。NOTVERYHARDConstructorrowdarkClassAndrewStankevichContest42:C.ComparatorNetworks一个比较器(i,j)(ij)会比较i和j这两个位置的比特bi,bj，若bibj则会将它们交换。一个比较器网络是一系列依次执行的设定好参数的比较器。一个比较器网络对某个比特序列是排序的，当且仅当输入这个比特序列的输出是单调递增的。AndrewStankevichContest42:C.ComparatorNetworks构造一个比较器网络(比较器=1000)，使其对于输入的01序列(n=10)是非排序的，且对其他的所有01序列都是排序的。无解输出-1。例：一个选择排序网络Solution若输入已经排好序显然无解大胆猜测其他情况全有解Solution不是无解意味着最早出现的1在最晚出现的0前面。设其位置为p1p0先使p0位置上是所有给定序列为0的位置中的最大值。再使p1是所有给定为1的位置的最小值。Solution这时，显然只有给定序列会有p0是0且p1是1。先不看这两个位置，对其他位置进行全排序。Solution设给定序列0的个数是c个。有不等式p1=cp0。设其他某序列0的个数是d个。此时对于其他某序列有三种情况：Case1:c=d此时必有p0位置上是1p1位置上是0且由p1=dp0知序列已经有序。任何比较都不变。SolutionCase2:cd则p1上是0p0上不确定由不等式p1=cp0则只可能p0上是1p0=d或p0上是0p0d时未排序。则依次比较(c+i,p0)和(p0,n-j)i,j都递增这里比较的顺序非常重要。Case3:cd对称，同理。CodeChefDEC14:Divideordie给出平面上一个n度角（三点坐标，n是整数）。求一个方案通过尺规作图将其n等分。无解输出-1。Solution世界人民熟知不能三等分任意角。由大数学知，尺规扩张是最多是二次扩张。而三等分60度角需求解的多项式是三次的，故60度不可三等分。Solution考虑尺规直接画能画出什么度数的角。1度/2度与60度不可三等分矛盾。若3度角可以画出，利用角度的加减法，任何与不是3的倍数的整数度角都可以被等分。而所有3的倍数的角由于可被直接画出必然不能被等分。Solution怎么画3度角。利用黄金分割三角形72度底角！sin72=(sqrt(5)-1)/4Solutionsqrt(5)可通过直角边长为2比1的直角三角形得到。72度四等分得到18度。等边三角形60度四等分得到15度。相减得到3度角。WorldFinals2014:A.Baggage初始序列BABABA…BA(长度2n=200)，每次可以移动相邻的恰好两个元素到某两个连续空位，求一个方案在最短步骤内将其排为AA…A若干空格BB…B。Solutionn=3ans=3BABABAABB__ABAABBBAA__AAABBB____Solutionn=4ans=4ABBABAB__ABABABABAABBA__BBAAA__ABBBBAAAAAABBBBSolutionn=5ans=5BABABABABAABBABABAB__AABBA__BABBAAABBAABB__BAAA__AABBBBBAAAAAAABBBBBSolutionn=6ans=6BABABABABABAABBABAB__ABABAABBABABBAAB__AABBA__BBAABBAAABBAAABB__BBAAA__AAABBBBBBAAAAAAAABBBBBBSolutionn=7ans=7BABABABABABABAABBABABAB__ABABAABBABA__BBAABABAABBABAABBBAAB__AABBA__ABBBAABBAAA__AAAABBBBBBBAAAAAAAAABBBBBBBABBAAAABBB__BBAASolutionn=8ans=8BABABABABABABABAABBABABABAB__ABABAABBA__BABABBAABABAABBAABBABABBAAB__AABBAABBA__BBAABBAAABBAA__ABBBBAABBAAABBAAAAABBBB__BBAAA__AAAAABBBBBBBBAAAAAAAAAABBBBBBBBSolutionThat’sall,thankyou!