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。我看见了这个领域有一个很大的黑洞——让我不得不被它吸引。但现在我不得不要放下它一段时间了，因为还有数学和物理……有时新一轮的奋斗。