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

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

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左右浮动。

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

合影

发表评论

电子邮件地址不会被公开。 必填项已用*标注