第1页 / 共95页
第2页 / 共95页
第3页 / 共95页
第4页 / 共95页
第5页 / 共95页
第6页 / 共95页
第7页 / 共95页
第8页 / 共95页
Codeforces题目泛做解题报告许昊然.pdf
Codeforces题题题目目目泛泛泛做做做 解解解题题题报报报告告告
南京外国语学校 许昊然
Contents
1 Solution
2
2
1.1 Codeforces 7E Dening Macros . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2 Codeforces 8D Two Friends . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Codeforces 8E Beads
4
1.4 Codeforces 10E Greedy Change
. . . . . . . . . . . . . . . . . . . . . . . . . .
5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Codeforces 15E triangles
7
1.6 Codeforces 17C Balance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.7 Codeforces 17E Palisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.8 Codeforces 19E Fiary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.9 Codeforces 23D Tetragon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.10 Codeforces 23E Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.11 Codeforces 26E Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.12 Codeforces 28D Do not fear, DravDe is kind . . . . . . . . . . . . . . . . . . . 12
1.13 Codeforces 30D Kings Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.14 Codeforces 30E Tricky and Clever Password . . . . . . . . . . . . . . . . . . . 13
1.15 Codeforces 32E Hide-and-Seek . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.16 Codeforces 35E Parade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.17 Codeforces 36E Two paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.18 Codeforces 37E Trial for Chief
1.19 Codeforces 39C Moon Craters
. . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.20 Codeforces 39A C*++ Calculations . . . . . . . . . . . . . . . . . . . . . . . . 18
1.21 Codeforces 39E What Has Dirichlet Got to Do with That? . . . . . . . . . . . 18
1.22 Codeforces 40E Number Table . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.23 Codeforces 43E Race
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.24 Codeforces 44J Triminoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.25 Codeforces 45G Prime Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.26 Codeforces 45E Director
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.27 Codeforces 46F Hercule Poirot Problem . . . . . . . . . . . . . . . . . . . . . . 23
1.28 Codeforces 47E Cannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.29 Codeforces 49E Common ancestor . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.30 Codeforces 51F Caterpillar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.31 Codeforces 53E Dead Ends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1
1.32 Codeforces 57D Journey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.33 Codeforces 226E Noble Knight’s Path . . . . . . . . . . . . . . . . . . . . . . . 28
1.34 Codeforces 217D Bitonix’ Patrol
. . . . . . . . . . . . . . . . . . . . . . . . . . 28
. . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.35 Codeforces 67E Save the City!
1.36 Codeforces 67C Sequence of Balls
. . . . . . . . . . . . . . . . . . . . . . . . . 30
1.37 Codeforces 70D Professors task . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.38 Codeforces 70E Information Reform . . . . . . . . . . . . . . . . . . . . . . . . 31
1.39 Codeforces 156E Mrs. Hudson’s Pancakes . . . . . . . . . . . . . . . . . . . . . 32
1.40 Codeforces 105D Entertaining Geodetics
. . . . . . . . . . . . . . . . . . . . . 33
1.41 Codeforces 193D Two Segments . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.42 Codeforces 75E Ship’s Shortest Path . . . . . . . . . . . . . . . . . . . . . . . . 35
1.43 Codeforces 76F Tourist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.44 Codeforces 76A Gift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.45 Codeforces 77E Martian Food . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.46 Codeforces 79D Password . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.47 Codeforces 81E Pairs
1.48 Codeforces 82E Corridor
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.49 Codeforces 83E Two Subsequences . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.50 Codeforces 85E Guard Towers . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.51 Codeforces 86E Long sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1.52 Codeforces 89D Space Mines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.53 Codeforces 91D Grocer’s Problem . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.54 Codeforces 93D Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.55 Codeforces 97C Winning Strategy . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.56 Codeforces 97A Domino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.57 Codeforces 98D Help Monks
1.58 Codeforces 98C Help Greg the Dwarf
. . . . . . . . . . . . . . . . . . . . . . . 49
. . . . . . . . . . . . . . . . . . . . . . . . . . 50
1.59 Codeforces 191D Metro Scheme
1.60 Codeforces 164D Minimum Diameter
. . . . . . . . . . . . . . . . . . . . . . . 51
1.61 Codeforces 150E Freezing with Style . . . . . . . . . . . . . . . . . . . . . . . . 52
1.62 Codeforces 101E Candies and Stones
. . . . . . . . . . . . . . . . . . . . . . . 53
1.63 Codeforces 103E Buying Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.64 Codeforces 105E Lift and Throw . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.65 Codeforces 107D Crime Management
. . . . . . . . . . . . . . . . . . . . . . . 55
1.66 Codeforces 113D Museum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.67 Codeforces 115D Unambiguous Arithmetic Expression . . . . . . . . . . . . . . 57
1.68 Codeforces 120I Luck is in Numbers . . . . . . . . . . . . . . . . . . . . . . . . 58
1.69 Codeforces 123E Maze
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
1.70 Codeforces 125E MST Company . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.71 Codeforces 193E Fibonacci Number . . . . . . . . . . . . . . . . . . . . . . . . 61
1.72 Codeforces 145D Lucky Pair . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2
1.73 Codeforces 132E Bits of merry old England . . . . . . . . . . . . . . . . . . . . 62
1.74 Codeforces 138D World of Darkraft . . . . . . . . . . . . . . . . . . . . . . . . 63
1.75 Codeforces 140F New Year Snowake . . . . . . . . . . . . . . . . . . . . . . . 64
1.76 Codeforces 147B Smile House . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.77 Codeforces 152D Frames
1.78 Codeforces 183D T-shirt
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
1.79 Codeforces 217E Alien DNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
1.80 Codeforces 135E Weak Subsequence . . . . . . . . . . . . . . . . . . . . . . . . 68
1.81 Codeforces 163D Large Refrigerator . . . . . . . . . . . . . . . . . . . . . . . . 69
1.82 Codeforces 167E Wizards and Bets
. . . . . . . . . . . . . . . . . . . . . . . . 70
1.83 Codeforces 232D Fence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
1.84 Codeforces 175E Power Defence . . . . . . . . . . . . . . . . . . . . . . . . . . 71
1.85 Codeforces 176D Hyper String . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.86 Codeforces 178F Representative Sampling . . . . . . . . . . . . . . . . . . . . . 73
1.87 Codeforces 178E The Beaver’s Problem II . . . . . . . . . . . . . . . . . . . . . 73
1.88 Codeforces 180B Divisibility Rules . . . . . . . . . . . . . . . . . . . . . . . . . 74
. . . . . . . . . . . . . . . . . . . . . . . . 75
1.89 Codeforces 185D Visit of the Great
1.90 Codeforces 187D BRT Contract
. . . . . . . . . . . . . . . . . . . . . . . . . . 76
1.91 Codeforces 176E Archaeology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
1.92 Codeforces 196D The Next Good String . . . . . . . . . . . . . . . . . . . . . . 77
1.93 Codeforces 198E Gripping Story . . . . . . . . . . . . . . . . . . . . . . . . . . 78
1.94 Codeforces 200E Tractor College . . . . . . . . . . . . . . . . . . . . . . . . . . 79
1.95 Codeforces 200A Cinema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.96 Codeforces 201E Thoroughly Bureaucratic Organization . . . . . . . . . . . . . 81
1.97 Codeforces 201D Brand New Problem . . . . . . . . . . . . . . . . . . . . . . . 82
1.98 Codeforces 204E Little Elephant and Strings . . . . . . . . . . . . . . . . . . . 83
1.99 Codeforces 207B Military Trainings . . . . . . . . . . . . . . . . . . . . . . . . 83
1.100 Codeforces 207A Beaver’s Calculator
. . . . . . . . . . . . . . . . . . . . . . . 84
1.101 Codeforces 167D Wizards and Roads
. . . . . . . . . . . . . . . . . . . . . . . 85
. . . . . . . . . . . . . . . . . . . . . . . . 87
1.102 Codeforces 209C Trails and Glades
1.103 Codeforces 212B Polycarpus is Looking for Good Substrings
. . . . . . . . . . 88
1.104 Codeforces 212D Cutting a Fence . . . . . . . . . . . . . . . . . . . . . . . . . 88
1.105 Codeforces 212C Cowboys
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
1.106 Codeforces 213E Two Permutations . . . . . . . . . . . . . . . . . . . . . . . . 90
1.107 Codeforces 217C Formurosa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
1.108 Codeforces 229E Gifts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
2 Special Thanks
93
3
1 Solution
1.1 Codeforces 7E Dening Macros
通通通过过过情情情况况况
AC
关关关键键键词词词
表达式计算 dp
题题题目目目大大大意意意
题目给了一系列C++的宏定义，问你一个表达式是否是\安全"的。安全的定义是，展开后的
表达式中，所有的宏在计算过程中都被作为一个整体运算。
如#dene sum x+y 后， 2 sum就会被替换乘2 x + y，此时因为乘号优先级比加号高，
导致sum宏在实际计算中被拆开了，可能产生错误。
宏的个数 100, 每个表达式长度 100. 只有四则运算和括号。
算算算法法法讨讨讨论论论
我们考虑一个宏是否是\安全"的，经过观察和一些实验，可以发现，只有以下4种状态：
状态1(s1)： 这个宏完全安全，以任何方式使用该宏都没问题。
状态2(s2)： 这个宏不安全，只要表达式中出现该宏，都会导致表达式不安全。
状态3(s3)： 这个宏部分安全，仅当这个宏与’*’,’/’连接时，或出现在’-’后面时，才会使
表达式不安全。
状态4(s4)： 这个宏部分安全，仅当这个宏出现在’/’后面时，才会使表达式不安全。
有了这4个状态，我们只需推出状态之间的转移即可。
如果表达式没有使用任何运算符或括号或宏（也就是s仅仅是个单独的变量），那么安
全级别显然是s1
如果表达式s是(t)的形式（被一对括号括起来的表达式t），那么如果t的状态不是s2，
则s的状态是s1，否则s的状态是s2
我们找到表达式s中，最后一次运算的符号，设其为op，设其两侧表达式分别为t1和t2。
我们进行以下分类讨论：
{ 显然，如果t1或t2的安全状态是s2，则s的状态也是s2;
{ 如果op是’+’，那么s的状态是s3;
{ 如果op是’-’，那么，如t2状态是s3，则s状态是s2，否则s状态是s3
{ 如果op是’*’，那么，如t1或t2状态是s3，则s状态是s2，否则s状态是s4
{ 如果op是’/’，那么，如t1或t2状态是s3，或t2状态是s4，则s状态是s2，否则s状态是s4
于是，此题得到了解决。 时间复杂度O(n len2)，如果愿意追求更好的复杂度，可以建
出表达式树，从而做到O(N len)
4
特特特别别别注注注意意意
此题在tsinsen上的版本有多组数据，因此要特判n = 0的情况。
1.2 Codeforces 8D Two Friends
通通通过过过情情情况况况
AC
关关关键键键词词词
计算几何 二分答案
题题题目目目大大大意意意
平面上有3个点：A，B，C. 现在Alice和Bob都在A，Alice想要走到B，走的路线长度不得超
过LA，Bob想经过C然后到B， 走的路线长度不得超过LB。
要求设计他们的路线，使得从A开始的公共部分尽可能长（也就是一旦两人分开，即使重
新会合也不计入公共部分的长度了）
算算算法法法讨讨讨论论论
首 先 ， 如 果Alice可 以 先 陪Bob直 线 走 到 点C， 再 陪Bob走 到 点A， 那 么Alice显 然 可 以 陪
伴Bob全程，答案是min(LA; LB).
进一步观察，易发现答案具有单调性。故考虑二分答案。
设我们即将验证答案S的可行性。 因为我们之前已经特判了Alice陪Bob一起去点C的情
况，因此我们现在可以假设，走了公共的S路程后，Bob还没去过点C.
因为一旦分离，即使再次重合也不再计入公共路径长度，所以接下来我们可以分开单独
考虑Alice和Bob，而且应该让他们尽快到点B（当然Bob还得经过商店）。 分离后，Alice的
路线显然应该直线去点B。而Bob的路线显然是直线去点C，然后直线去点B。因此分离点必
须满足：
分离点必然在以点A为中心，S为半径的圆内。（因为Alice和Bob一起走的长度为S）
分离点必然在以B为中心，LA S为半径的圆内。（为了让Alice能在剩下的LA S时
间内到达点B）
分离点必然在以C为中心，LB S dist(B; C)的圆内。 （为了让Bob能在剩下的LB
S时间内到达点C然后去点B）
如果存在任一分离点能同时满足上述3条要求，则S可行。
于是问题被转化为了纯计算几何问题：给定3个圆，判断其是否又公共部分。 这个问题十
分经典，解决方法也五花八门，暴力找关键点+分类讨论、二分x轴等方法都是可行的。
特特特别别别注注注意意意
注意实数精度问题。
5
1.3 Codeforces 8E Beads
通通通过过过情情情况况况
AC
关关关键键键词词词
数位dp
题题题目目目大大大意意意
将所有n位二进制串（允许前导0）中同时满足字典序不小于其逆序串、取反串和逆序取反串
的串提取出来，按字典序排序，求第m个。 n 50; k 1016
算算算法法法讨讨讨论论论
首先显然满足题意的二进制串的首位必须是0.
考虑一位一位地确定答案串。假设已经确定了答案串的前k位，我们假设第k + 1位是0，
则要设法统计出满足条件的串的个数s。
那么如果s < m，则答案串第k + 1位为1，同时m = m s；否则答案串第k + 1位为0.
于是问题转化为，统计所有长度为n的，前缀为pref ix的二进制串中，满足题目要求的串
的个数。
这是一类与数位有关的统计问题，于是很容易想到数位dp。
状态dp[i][rev][inv]表示，当前已经确定了前i位和末i位， rev表示前i位与末i位的逆序是
否相等，inv表示前i位与末i位的逆序取反后是否相等。
状态转移比较显然，我们枚举第i + 1位和第n i位的取值，如果它满足pref ix的限制，且
新的串没有违反题目要求（可以利用rev,inv和取值判断）， 那么更新rev和inv的状态，并累
加到对应的新状态上。
时间复杂度O(16 N 2)
特特特别别别注注注意意意
注意如果n为奇数，那么dp到正中间一位的时候，这一位会同时作为前i位和末i位的组成部
分，需要特判。
1.4 Codeforces 10E Greedy Change
通通通过过过情情情况况况
AC
关关关键键键词词词
论文题 结论题
6
题题题目目目大大大意意意
给定n种货币，每种货币数量无限。
现在要求以最少的货币数目表示一个数S。 一种方法当然是DP求一个最优解了， 当然正
常人的做法是贪心：每次取最大的不超过当前待表示数的货币。
现在，你的任务是证明正常人的表示法不一定最优：找到最小的S，使得正常人的表示法
比理论最优解差，或说明这样的S不存在。
n 300
算算算法法法讨讨讨论论论
首先这是一道论文结论题。 有一篇论文专门讨论了这个问题（其实CF上的题目描述和论文
里的几乎一个字都没变，连举的例子都是一样的）
这篇论文题目是《A Polynomial-time Algorithm for the Change-Making Problem》， 可
以在这里下载
其实我们可以感性的猜想出一个\看起来很靠谱"的算法：
首先把所有货币从大到小排序。
考虑某个大于w[i]但小于w[i 1]的数的表示方法。我们为了让正常人的贪心算法得到很
差的解，应该让这个数恰好超过w[i]一点点， 可以想象，必须让人贪心掉w[i]后发现剩下的
数必须用一大陀小货币才能拼出。
我们需要确定这个数S贪心掉w[i]后，到底会用多小的货币才能表示出来。于是我们找
一个j，使得w[j + 1] < S w[i] < w[j]，作为贪心后最大可用货币。 我们枚举这个j，找出利
用i + 1到j种货币能拼出的最大的严格小于w[i]的价格是多少，然后把这个值加上w[j]。
我们检验所有这样的值，找到最小的一个即可。
这个做法直观感觉比较靠谱。事实上我们可以严格证明这个算法的正确性，但比较复杂，有
兴趣可以自行参考论文。
特特特别别别注注注意意意
无
1.5 Codeforces 15E triangles
通通通过过过情情情况况况
AC
关关关键键键词词词
递推 组合数学 找规律
题题题目目目大大大意意意
给定一个有规律的金字塔形的图形，其中一部分三角形是黑色的（见图）。
7
要求统计所有从最顶端出发，沿着黑线走了一条闭合简单路径又回到最顶端，且没有任
何黑色三角形在闭合简单路径内部的路径条数。 n 106
算算算法法法讨讨讨论论论
我们显然需要分析可行路线的形式，以得出有用的性质。
观察发现，金字塔被中间一竖列的黑色三角形分成了左右两个部分，路径只有3种形式：
没有进入过左部，也没有进入右部。 这类路径很少，可以手工统计。
只进入了左部或只进入了右部。 因为左右对称，这两小类路径条数相等，不妨设其均
为S。
进入了左部，然后回来到左右部的交汇点（也就是第二条横线的中点），然后进入右
部，再回来。 或先进入右部再进入左部。因为左右独立且对称，显然这类路径共有2S2种。
于是我们只需统计从出发点进入左部，然后回交汇点的方案数。
观察这些路径，可以发现一些共性：
一定有一个到达的最深层数。
从出发点每次往下走一层时，都有个类似\巷子"的结构，可以选择进去；也可以选择
不进去，直接往下走（见下图）。
到达最深层后，返回出发点的路线唯一。
于是我们只需计算每层的\巷子"进入后再回来的方案数目。 可以容易的发现，第i层
的\巷子"方案数是f (i) = 2i 3种。
于是我们可以简单的用乘法原理算出对于某个给定的最深层的方案数： g(i) = f (1)
最终答案就是 g(n) g(n) 2 + 2 g(n) + k. 分别对应3类路径、2类路径、1类路径的条
f (2) ::: f (i)
数。（k值需手算）
特特特别别别注注注意意意
无
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
