CCC 2018 解题报告以及心得体会

2018-03-10

2018年3月8日，北京，清华大学，与滕老师、一群可爱的小伙伴们还有他们的家长一起参加了 CCC 2018 清华赛区的比赛。废话不多说，下方是我对各个题目的想法以及最后的总结。

本文迁移自老博客，原始链接为 https://lookas2001.com/ccc-2018-%e7%bb%93%e9%a2%98%e6%8a%a5%e5%91%8a%e4%bb%a5%e5%8f%8a%e5%bf%83%e5%be%97%e4%bd%93%e4%bc%9a/

Editor

题目解析

提供两个字符串，要求比较大小规则。首先需要对两个字符串的所有字符转换为小写字母，然后对两个字符串从左到右逐位比较，如果遇到一个位置上a字符串比b字符串在字典的位置靠前，输出该字符串；如果遇到一个字符串遇到结尾，输出该字符串。

算法设计

按照题目解析的方式进行模拟。

Tags: simulation

失误分析

最开始在写的时候，偷懒使用了全文翻译，结果没有完全理解题目的含义。

为了算法效率的优化，在每一次比较的时候进行小写转换，导致在第一次输出的时候出现了问题（后面的字符串还是大写，不过后来改正了）。

另外如果错了，那估计就是没有充足的测试？

得分预估

最高：100

Equation

题目解析

题目提供一个形如 p[]q=r 的算式，其中算式的操作符号可能是 + - *；其中 p q r 的部分数字被大写字母替换；如果一个字母是在 p q 或者是 r 的最高位，则该字母不能为 0 ；另外每一个字母所对应的数字不能相同。

算法设计

初步想法，从0-9枚举每一字母对应的数字并且带回验证，算法最坏复杂度为O(10^9)

考虑到每一个字母的对应的数字不能相同，可以对字母产生0-9的全排列，然后替换算式中相应的位置，带回验证。算法最坏复杂度为O(10!)

Tags: enumerate

失误分析

由于之前没有怎么接触过枚举（或者说暴力）的题目，或者说上次szr讲的那道暴力最终也没找时间写，对这种题目一下子就懵住了，尤其是对于字母的枚举，完全不知道如何下手。

过高的估计算法复杂度，认为10s的程序一定过不去，后来也就没有心情去做这道题了。

得分预估

最高：0

Count Path

题目解析

提供一个带有 n 个点的图，对于点 i ，有一个权值 ai ，对于 i j 两点；如果 i < j 则有 wij 条有向边从 i 指向 j ，求问从点 1 到点 n 总共有多少条路径。另外，最终结果需要mod一个数。

另外，定义有一个函数为 lcs(i, j) ，返回 i j 转换为二进制后从右看起共用1，比如 3 = (11)2 ， 5 = (101)2 则两者lcs后的结果为 1 = (1)2。

wij = (ai + lcs(ai, aj)) * (aj + lcs(ai, aj)) （印象里，这里应该是对 ai aj lcs）

算法设计

动态规划题目，定义 si 为为 i 到 n 的道路数，那么 si = s(i + 1) * wi(i + 1) + s(i + 2) * wi(i + 2) + ... + sn * win，其中 sn = 1。

Tags: bit_operation dp

失误分析

被数据范围给吓到了

lcs的时候提供的操作数错误（印象里是提供ai，aj而不是i，j）

忘记mod数了。

得分预估

最高：50

第四题

看不懂。

第五题

看不懂。

总结

失误分析

由于耍了些小聪明，用了全文翻译，结果机翻的结果搭配着图片版本因为bug最终没有显示的公式，实际上读题效率还不如查字典来的快。

对IDE的依赖性太强了，依靠着IDE的符号自动补全，没有自动补全后，写代码越写越烦躁。

对算法复杂度的估算（包括数据范围的分析）能力不行，心理承受能力太差。

由于被第二道题卡住，花费了过量的时间去看那些我并看不懂的4 5题，另外，搭配上考试前的睡眠不足，最后，心态爆炸。

还是要多写题啊。

总分预估

150左右浮动。

另附一幅合影~~，我才不会说在这么远照相是因为近的地方被一对夫妻拍婚纱照了呢~~。