这次比赛是晚上7点开始的，所以状态大概比上次好一些。不过还是有题错得蛋疼，算是熟悉Python过程中的一个教训吧。 A题可以算是水之又水，模拟也可以做，写几个if或者case语句也可以做，甚至直接打表也可以。不过还真有人做错，随手hack掉了。 B题大概就是推一个公式然后计算就可以。写的时候有个小地方写错了，resubmit了一次，貌似扣了一些分。 C题是说判断一个图是不是如下形状：有一个至少三个结点的环，环上每个结点下面都可以挂一棵树。我直接DFS了一下，不过判断连通的时候出了一个很恶心的问题：我的判断连通方法是，DFS之后看是不是访问了所有结点。结果Python的++i是0+0+i的意思，于是我写的一句++n直接没有作用而且还不报错……然后pretest又没有这种情况出现，于是这道题system test的时候挂掉了。写C++写习惯了，++、--操作符总是顺手用。这个习惯得改了…… D题看起来是概率题，实际上仔细想一想就知道，整体的概率大小和X无关，只和每个.和它后面第一个X的距离是奇数还是偶数有关。尽量保证结果是.X.X……的形式，然后在不影响总概率的情况下安排字典序（如：..X.X可以改为...XX），实际上这就成了一道构造题。代码写起来可能稍微乱一点，别的没难度。 E题貌似这次是Div 1的D题，比较难。有n*sqrt(n)的算法，但是最后也没写完，不知道能不能奏效。 最后挂了C题，E题没做。因为大部分人E都没做所以成绩还好，压线变紫。下次就要做Div 1了，Ganbatte！

最近突然来的兴致，于是又开始刷题了。现在在做的比赛有SRM和这个Codeforces的比赛。SRM还是用C++（因为不给开Python），这个就用来练Python了。 比赛刚刚结束，结果略坑爹。虽然速度搞出五道题然后hack了两个人暂时占领ranklist第二的位置，不过System Test直接挂了三道题。 A题是一道非常水的枚举，结果被我写挂了。原因是我偷懒没开二维数组存邻接矩阵（python开二维矩阵要写好长一段啊，用过的应该都知道吧……），然后直接存了边表。更坑爹的是边表里边的查找我随手写了个in，要知道Python的in可是线性复杂度啊，不过当时没看出来。这算是C++留下的后遗症呢还是Python不够熟练呢，总之光注意循环的复杂度没问题就没管这道题了。结果悲剧地TLE了。要是把边表存成一个set其实就OK了，不过可惜比赛时没注意到这一点。 B题也是水题，纯模拟，跳过。 C题是字符串处理，对于Python来说没有任何难度。只要注意最开始别直接转成int就行了，不然会爆掉（Python不会爆不过会TLE。。。大概）。 D题大概是线段树（树状数组？）+DP，可惜我已经好久没写代码了所以没敢下手，只写了一个离散化+DP。果断TLE掉。代码能力啊代码能力，这些算法怎么写都得补啊。。。以后应该还是有用的吧。。。其实这题算时间复杂度也出现了问题，(n/2) * (n/2)我竟然当成了n的复杂度，真不知道脑子在想什么。锁了题之后才发现这一点，不过已经晚了。测了极限数据过不了（顺便用这组极限数据hack了一个人），当时还心存侥幸，其实想想也知道这种比赛的数据肯定足够强。。。 update: D题其实只要把车站进入和离开的时间点排序就可以了，我想复杂了。。。坑爹啊。 E题是简单数学题（跟D题比真的简单不少），不过写的时候手贱了多打了点东西。。。于是就挂了。自作自受啊自作自受。不过就算是在当初状态最好的时候，能不能保证不出这个失误呢？还真不好说。 最后排名惨不忍睹了（就出了两道题还不是高分题），估计下次还要做Div 2了吧。SRM那边开的小号第一场倒运气不错，直接黄了，比大号的第一场分数都高——明明排名比大号的第一次比赛低不少。SRM的分数通货膨胀了么。 唉唉，这个总结就这样吧，恢复状态任重而道远啊。。。

  #include <iostream> using namespace std; class OutOfBound {}; class IllegalSize {}; template <class elemType> class list { public: virtual void clear() = 0; virtual int length() const = 0; virtual void insert(int i, const elemType &x) = 0; virtual … Continue reading →