SHTSC

今天是 SHTSC(上海市信息学组队选拔赛)最后一次考试,也是宣布分数的时候。先说一下结果,

Day One

24(70 分):一道算 24 点的题目,说是说高级 24 点计算,其实高级了之后就非常简单(这句话很辩证),我大概在 10 分钟就做好了,没想到很多同学想了很久,还想了一个很复杂的。个人认为还能加 30 分,系统说我和 LTY 都是同样的错误,但经过手算,我们的答案显然是正确的嘛,写测评程序的人还真没水准。

Typesetter(0分):题目还没发下来,我就和 JRZ 说,是不是要我们做一个公式编辑器,他说很可能。没办法,看到这种字符串处理的题目心里就有莫名的恐慌,思路很混乱,而且很难里清楚,总结下来原因是,以前看到这种题目,没有静下心来好好研究,导致今天的结果就是——开天窗了。

Cactus(50分):一个图的计数问题,不是很难,DFS加高精度就可以了。一开始测评系统告诉我0分,结果在测一次的时候就50分了。没有满分的原因是,题目理解错误。更深层次的原因是,题目里对一种树——仙人掌树的定义,我看了半天才看明白(最后还是在一个细节上理解错了)。而对于别人呢,以前看到过,所以最多就是在看一遍,看看有没有出路就可以了。

Day Two

Incredible(100分):表面上是一个求方程解数的问题,实质是简单的递推,只要想到就OK了(反言之,没想到就挂了),复杂度看似很高,但是经过我的论证,实际复杂度很低,绝对可以再5秒内出结果。呵呵,只要是递推的题目,那就是十拿九稳的。

kth(30分):一看就知道考数据结构的,恶心啊。考卷一发下来,听见 HG 大叫,平衡二叉树,我这时就很残念,心想这题挂了,于是直接做最后一题了,后来反过来做这题,发现还是可以混几分的,于是就编了一个 Find + Partition 的算法,没想到考试结束后,HG告诉我,他也是用我这个方法的,我晕啊~

Color(0分):给一个 n 阶完全图,给边染色,求本质不同的染色方案数。最大的失误就是这道题目,原来以为可以靠这道题目翻盘的,结果……看到题目很高兴,因为一看就觉得是用波利亚原理做的嘛,正巧考试前一天,我看了一下午的波利亚原理,心里这高兴的~没想到,由于太高兴了,把题目看错了,看成把定点染色,结果就挂了,辛辛苦苦变得一个程序就这样废掉了,不过如果题目改一改(就是改称我理解错的那种情况),我那个绝对是一个好的算法,而且算法复杂度极低。不过现在换成边了,我还在思考中,在车上我已经想到怎么做了,但是在计算机上实现还是有困难,需要进一步优化,通过这道题目,使我对波利亚原理有了一个更深刻的认识,更让我对置换、对象、染色在波利亚原理里的关系有了一个清楚的认识。

总结:最后没有进队,其实也无所谓,2 个月,一直在弄计算机,学了很多很多东西(几乎把算法导论里比较实用的算法都学了一次),关键问题是,由于我始终没有学习使用指针,导致我没有学很多数据结构(很多高级的结构都是需要指针来实现),所以数据结构方面的东西不熟悉,更不要说灵活应用了。不过还是很有收获,这些知识我终身受用,计算机是一个实用的东西,欧拉路、网络流、二分匹配、素性检验、RSA,更高级的,自动机,NP,P。我看见了这个领域有一个很大的黑洞——让我不得不被它吸引。但现在我不得不要放下它一段时间了,因为还有数学和物理……有时新一轮的奋斗。

Join the Conversation

4 Comments

  1. 大部分内容属于看不懂
    你大概针对上海竞赛的这种什么什么比机器什么的少了一点,但是你书看得那么多绝对有好处的。强啊

Leave a comment

Your email address will not be published. Required fields are marked *