《2015冬令营课件_倪昊斌-构造题选讲》由会员分享，可在线阅读，更多相关《2015冬令营课件_倪昊斌-构造题选讲（70页珍藏版）》请在金锄头文库上搜索。
1、构造题选讲 SJTU 作战动员TankEngineer倪昊斌 Trivial ConstructorFtiaschClass Ural1979 ResourcesDistribution 一个n n n的立方体 在外表面的6n 2个面上写上1 6n 2这些数字 使得从任意格子出发向任意一个方向走一圈和都相等 Solution 考虑对称性每个面和其对面一定会同时出现在某个环中1 6n 2 2 6n 2 1 VeryEasy ConstructorAngryBaconClass CF226D Thetable 有一个n m n m 100 的矩阵 元素绝对值 100 每次可以将一列取负或者将一行取
2、负 求一个方案使得每行每列的和都非负 Solution Naivealgorithm 每次看有没有行 列和为负 如果是就reverse 和递增 一定会结束 复杂度 操作次数 n Solution 每次至少使和增加2和最大100 3 最小 100 3复杂度 100 4 CF468C Hackit 求给出区间 l r 使得区间中的数的数位之和模a为0 l r 10 200a 10 18 Solution 令l 1r 10 19的数位和为s可以方便计算则l kr 10 19 k 1的数位和为s k 1 可构造答案 AndrewStankevichContest44 H HuffmanCodes 给出
3、n 100个哈夫曼编码当中的0 1个数 问是否存在可能的哈夫曼编码 Solution 自底向上构建哈夫曼树 0和1个数之和最大且1最多的点深度最深 且一定有一个1个数少10个数多一的点和其匹配 合并两个点 得到一个新点 不断重复至构建完成或出现矛盾 CF209C TrailsandGlades 有一张无向图 10 6 加最少的边使之有欧拉回路 Solution 如果图连通 那么只需把奇度点两两相连即可 如果图有k 1个连通块 则至少需要k 1条边把它们先连成一个连通块 优先选取奇度点向外连 Easy ConstructorArchDruidClass ZOJ3823 ExcavatorCont
4、est 在n n的网格上 由边界某个格子出发四连通经过所有格子一次且仅一次再回到边界上 要求拐弯的数量至少有n n 1 1次 Solution n 2 Solution n 3 Solution n 4 Solution n 5 Solution n 6 Solution 沿着左边沿和下边缘走一圈 接着递归套用n 2的构造方案 走左下边沿的方案奇偶略有区别 LatviaUContest14 G Mosaic 有三种颜色的珠子各a b c 2 31个 给出方案铺满若干层的三角形 且每层颜色必须相同 Solution 猜测 a b c为某个三角形数时必有解构造 每次用最多的颜色填最后一行反例 22
5、2or111 Solution 补丁 如果有两个2或者两个1无解n 1001trivialn 2111无解012003trivialn 3222否则必有一个 3 Solution n 3设a b c n n 1 2c3 n 1 知a n若n b只能放a转化为n 1否则称这一列为可选择的先放a Solution 若最后出现了222or111且前面存在可选择的列 找到最小的可选择的列k 则k和k 1列必然颜色不同 且交换k和k 1列的颜色必然是合法的 使之变成123或012即可 NEERC2013 K KidsinaFriendlyClass 一张图有黑点和白点 每个黑点和a条边和黑点相连b条边和
6、白点相连 每个白点有c条边和黑点相连有d条边和白点相连 a b c d 50 求一个方案使总点数最少 Solution 枚举黑点个数n 则白点有nb c个 连黑点和白点之间的边 trivial问题转化为给一个图如何使得每个点的度数都相等 WrongSolution 每次选两个剩余度最大的点相连 反例 62 Solution 每次选一个剩余度最大的点 将其与其余度最大的若干个点连接使其度满足要求 正确性 留给聪明的读者作为练习 可用于构造任意给定每个点度数的图 Nothard Constructordata hClass UdmurtSU IzhevskSTUcontest J Cranes 把
7、n个箱子从0号位置移动到m号位置 你可以使用k个机械手 每个机械手每个单位时间可以左右移动一格或不动 提起 放下箱子的时间可以忽略不计 求最短时间 n m k 10 6 Trivial 请大家手算数据体会一下3个机械手4个箱子长度5 Level0 Ans 20方案 来回两趟 Level1 Ans 15方案 最后可以不用回去 Level2 Ans 4 5 3 1 7or其他公式方案 Whatareyouthinking 反例 1机械手2个箱子长度5or其他反例 Level3 Ans 13方案 两个机械手直接走到5 另一个先走到4 两个到5的回去一个接好 走到4的再把另一个箱子送到5 Level4
8、 Ans 11方案 两个机械手直接送两个箱子到5 剩下一个把一个箱子运到3 再回去拿一个到5 两个机械手其中一只回到3去拿 Level5 Ans 9方案 机械手A 直接到5 回到3再拿一个机械手B 先送到3 回到1再拿一个机械手C 先送到1 再回去拿一个 更复杂的情况 Solution 每秒对于每个机械手采取这样的贪心行动 假设机械手数量小于等于箱子数量 且先考虑离m位置较靠后的手 1 如果有箱子在自己位置后面且没有被抓着 扔下手上的箱子 回去一步 2 否则自己当前位置必有没有抓的箱子 抓起它向前一步 Prove 这样使得所有手往回走的步数最少 UfaSATU BucharestUContes
9、t J ReverseSort 有n 32 10 3的一个序列 每次可以reverse一个区间 代价是区间长度 在总代价不超过4 10 6的条件下sort这个序列 Solution 根据给出的界的范围来考虑可能的构造 nlog 2n重要思路 模仿快速排序进行构造 Solution 快排每次确定一个元素的位置 再对左右两边进行分治 构造算法每次以不超过nlogn的代价确定一个元素的位置 再对左右两边进行分治 Solution 如果确定了中间元素 那么每个元素实际上只是0或者1对于一个01序列以nlogn代价进行排序 贪心 对于相连的一块0 1应一起处理 Solution 直接进行排序 每次交换相
10、邻两块 10101010 01010101 00101011 复杂度n 2 Solution 每次交换相邻两块 但间隔一组01 10101010 01100110 00011110 00001111可见开头的0的个数呈几何增长 故复杂度nlogn NotveryHard ConstructorrowdarkClass AndrewStankevichContest42 C ComparatorNetworks 一个比较器 i j ibj则会将它们交换 一个比较器网络是一系列依次执行的设定好参数的比较器 一个比较器网络对某个比特序列是排序的 当且仅当输入这个比特序列的输出是单调递增的 Andre
11、wStankevichContest42 C ComparatorNetworks 构造一个比较器网络 比较器 1000 使其对于输入的01序列 n 10 是非排序的 且对其他的所有01序列都是排序的 无解输出 1 例 一个选择排序网络 Solution 若输入已经排好序显然无解大胆猜测其他情况全有解 Solution 不是无解意味着最早出现的1在最晚出现的0前面 设其位置为p1 p0先使p0位置上是所有给定序列为0的位置中的最大值 再使p1是所有给定为1的位置的最小值 Solution 这时 显然只有给定序列会有p0是0且p1是1 先不看这两个位置 对其他位置进行全排序 Solution 设
12、给定序列0的个数是c个 有不等式p1 c p0 设其他某序列0的个数是d个 此时对于其他某序列有三种情况 Case1 c d此时必有p0位置上是1p1位置上是0且由p1 d p0知序列已经有序 任何比较都不变 Solution Case2 cd时未排序 则依次比较 c i p0 和 p0 n j i j都递增这里比较的顺序非常重要 Case3 c d对称 同理 CodeChefDEC14 Divideordie 给出平面上一个n度角 三点坐标 n是整数 求一个方案通过尺规作图将其n等分 无解输出 1 Solution 世界人民熟知不能三等分任意角 由大数学知 尺规扩张是最多是二次扩张 而三等分
13、60度角需求解的多项式是三次的 故60度不可三等分 Solution 考虑尺规直接画能画出什么度数的角 1度 2度与60度不可三等分矛盾 若3度角可以画出 利用角度的加减法 任何与不是3的倍数的整数度角都可以被等分 而所有3的倍数的角由于可被直接画出必然不能被等分 Solution 怎么画3度角 利用黄金分割三角形72度底角 sin72 sqrt 5 1 4 Solution sqrt 5 可通过直角边长为2比1的直角三角形得到 72度四等分得到18度 等边三角形60度四等分得到15度 相减得到3度角 WorldFinals2014 A Baggage 初始序列BABABA BA 长度2n 2
14、00 每次可以移动相邻的恰好两个元素到某两个连续空位 求一个方案在最短步骤内将其排为AA A若干空格BB B Solution n 3ans 3 BABABA ABB ABA ABBBAA AAABBB Solution n 4ans 4 ABBABAB A BABABABA ABBA BBAA A ABBBBAA AAAABBBB Solution n 5ans 5 BABABABABA ABBABABAB A ABBA BABBAA ABBAABB BAA A AABBBBBAA AAAAABBBBB Solution n 6ans 6 BABABABABABA ABBABAB ABABA
15、 ABBABABBAAB A ABBA BBAABBAA ABBAAABB BBAA A AAABBBBBBAA AAAAAABBBBBB Solution n 7ans 7 BABABABABABABA ABBABABAB ABABA ABBABA BBAABABA ABBABAABBBAAB A ABBA ABBBAABBAA A AAAABBBBBBBAA AAAAAAABBBBBBB ABBAAAABBB BBAA Solution n 8ans 8 BABABABABABABABA ABBABABABAB ABABA ABBA BABABBAABABA ABBAABBABABBAAB A ABBAABBA BBAABBAA ABBAA ABBBBAABBAA ABBAAAAABBBB BBAA A AAAAABBBBBBBBAA AAAAAAAABBBBBBBB Solution That sall thankyou
