下雨了。

昨天考完要命的体系，灿哥带了我和光哥等三个人去外面吃饭，路上灿哥讲每天忙得要死，羡慕我们能去电影院看电影。

看起来我们以后的生活大概也会这个样子吧，不可避免……

最戏剧性的是本来灿哥要送我们回来再开个会的，结果回来的路上接到电话说儿子生病了，于是只好马上赶过去。。。

快乐在哪里，幸福又在哪里，到底应该过怎样的生活，这些到底是否轮得到我们来选择？

不知道，我只好督促自己再加油一点，暑假要抓紧时间做好事情……

晚上，不小心翻到了很多三联的东西，重温了一大堆的文字，虽然仅仅是一些文字，但是那是我整个高中生涯，整整4年的回忆吧。还看到了刚知道高考分数的时候，子玉在论坛发的恭喜贴，几年后回去看，又是一阵额外的感动，原来这些简单的文字，才是最能经得起时间考验的。

然而，回忆，不知道算不算是美好的，却只是我一个人的。自己已经完全不是当年的那个男孩了。在不一样的地方，接触不一样的人，听不一样的歌，玩不同的游戏，交不同的朋友，过着不同的生活。

前段日子很惊奇地在一个ACM群里发现了孟起马，居然现在还是一个高中生，一下子明白了很多，而现在看到，2002年的自己，也和他是一样的。

现在的三联早已物是人非，而我，一个过客，也会继续开拓我的新生活。好好努力，好好爱，让回忆放出激励的火花吧：）

下面是一些值得纪念的朋友。发在这里，他们看到的概率几乎为零，不过我希望他们一切都好，永远的朋友：

笨笨

乖乖

周羽

猫猫

12

黑色

霍光

文远

棍子

子玉

天杰星

猎雕

A Square Root Day      现场赛36.13% (155/429)/同步赛42.27% (290/686)
秒杀题，但是在题意方面出了一些问题，一种理解是日和月必须相同，于是一年最多只有一个Square Root Day，一年有一个Square Root Day当且仅当该年的最后2或3位是1-12的平方，这12个完全平方数中的一个。还有一种理解是日和月可以不相同，可以一个是后三位的平方根，另一个是后两位的平方根，于是会多几个日子，比如1225年5月15日。因为题意不清，所以最后两种理解都算过。

B Number of Containers      现场赛4.46% (32/717)/同步赛20.73% (102/492)
中等难度题，n可以很大，所以O(n)的算法显然是会TLE的。首先可以发现，f(n, x) = (n - x) / x，也就是n / x - 1，所以求解F(n)就是i从1到n，对n / i进行求和，最后再减去n就是答案。考察n / i随着i增大时候的情况，可以发现i越增大，n / i这个值变化得越小。于是可以把整个求和过程分成两块，对以1 <= i <= sqrt(n)，直接求每个f(n, i)进行累加；而对于sqrt(n) < i <= n，他们的n / i的取值范围为1 - sqrt(n)，也就是说，这个范围数虽然多，但是至多只有sqrt(n)种取值，于是我们改成枚举每种取值，求对应该取值的i的个数。这样两块的复杂度都是sqrt(n)，可以满足时限要求。还有一点是最后的结果会超出int范围，需要使用long long类型。
题目因为被修改了一下，所以也有个地方没说清楚，不过应该不会误导人，只是理解起来有点费力。比赛的时候被放到了B题的位置，结果N多的队伍直接就来个直接暴力的，下次这种题目应该靠后一点放……

C Rounding or Truncation      现场赛2.12% (7/330)/同步赛7.55% (34/450)
中等难度题，有不少的trick。主要要解决的问题就是通过一组m和p的值，来推测在两种策略下，文件总数可能的取值范围。可以解决这个的话，只要对每组m和p对应的区间求交然后判断交是非为空即可。对于Rounding模式，p可以上下分别浮动0.5个百分点，其中往上的浮动是刚好取不到的（否则就向上进位了）。对于Truncation模式，p可以向上浮动小于1个百分点。这里还有一个问题是p等于0和等于100的时候要特别处理下，p等于0的时候，文件总数的上限是无数；p等于100的时候，因为没有向上浮动的空间了，所以对于Rounding模式，只能向下浮动，对于Truncation模式则完全不能浮动，只能是确定的100。有了p的取值范围就可以去根据m来计算文件总数的范围了，可以用double直接计算，但是处理不好很可能会有误差，推荐直接用整数处理，对p乘以10后，浮动的百分点数也就是整数了。能处理好上面的各项后，应该就能AC了。

D Elune's Arrow      现场赛8.95% (12/134)/同步赛8.02% (11/137)
中等偏难的几何题，不是很好想到解法。题目的模型就是用一个固定速度的圆去撞击一个朝固定方向进行匀速直线运动的圆，要选择角度从而尽可能早撞到移动的圆，输出最早撞到的时间。所谓圆撞到圆，就是圆心距离等于半径和，这里可以作一个模型转换，把逃跑的圆看成一个点，把它的半径加到追击的圆上。于是现在就是一个圆去追击一个匀速直线运动的点，依然不是很好处理。因为圆可以向所有角度发射，所以假设圆初始半径为r，速度为v，则在某个t时刻，圆可能触碰到的位置为一个半径为r+vt的圆。于是模型又可以这样转化：一个有初始半径的圆以速度v扩大半径，求何时能碰到一个直线运动的点。因为刚撞到的时候恰好是点在圆上的时候，因此可以立一个关于t的一元二次方程，最后求解方程，如果两个解都小于0则无解，否则输出最小的正解。
PS，这题也可以用其他ws的方法来解决，比如我用枚举角度+三分过了。

E Beverages for Sale      现场赛0.00% (0/2)/同步赛0.00% (0/1)
压轴题。题目给出的是这样一个模型：有一个可分割货物的集合A和购买者的集合B，每个购买者有各自拥有的钱的数量，而每种货物也有各自的数量。其中每个购买者只会购买A的某一个子集。购买者对货物的种类不关心，只想获得最多数量的货物。购买者只会购买他感兴趣的货物中价格最便宜的那些。题目要分析出这样一个模型的稳定状态，也就是说确定各种货物的价格，使得所有货物都卖完，所有购买者的钱也都用完。
我们可以构这样的一个图，所有货物和所有对它们感兴趣的购买者之间连边，流量为无穷（如果某一个货物或者某一个购买者没有任何边，则直接输出Impossible）。对于每个购买者，向一个汇点sink连一条边，流量为他们各自的钱数。然后从一个源点source向每一种货物连一条边，边的流量为货物的价格x。我们首先假设所有货物的价格都是一样的，我们需要二分这个价格x，使得所有的货物刚好可以全部被卖出去，也就是说确定最大的x，使得(source, A B sink)是图的一个最小割。然后考察假设这个时候的残余网络，假设在残余网络中可以到达sink的节点集合为W，设S=A-W，则集合S的所有潜在购买者（对S中任意一个货物感兴趣的购买者）都已经用完了他们的钱，如果再增加x，则会导致S的货物剩余。于是我们可以把所有集合S中的货物价格设置为x。接着，我们把集合S和S的所有潜在购买者集合从网络中去除，提高剩余货物的价格继续前面的步骤，如此循环往复，就可以把所有货物的价格确定下来的。

F Calculate With Abacus      现场赛39.59% (118/298)/同步赛60.00% (240/400)
描述有点长的简单题。已经保证了输入的算盘都是合法的，于是只要计算出算盘所代表的数字即可。其中一种方法就是看每一列的上下部分的|位置，就可以推算出该列代表的数字。这次也没有trick，一般只要读懂题就可以写对了。

G Number Game      现场赛5.36% (11/205)/同步赛13.52% (43/318)
中等难度题。有三个数字，每次可以去掉一个，然后加上剩下两个的和减一。问是否可以从给定的三个数得到给定的另外三个数字。可以发现，如果正着推的话，每次有三种选择，无法有效判断最终的三个数字是否可达。于是考虑逆着推，已知当前的三个数，其中最大的那个一定是新加的，而次大的那个一定是再前一次新加的，于是可以推算出被擦掉的那个数为次大数加一减最小数。这样一来，可以有唯一确定的方法递推回去。不过需要注意的是，正推的第一步，因为当前的三个数不一定满足a+b=c-1这样的等式，所以逆推的时候是无法确定被擦掉的数是多少的。所以，可以对初始的三个数枚举第一次擦掉的数为哪个，得到三种满足等式的情况。于是逆推的时候，一旦能匹配其中的一个就可以了。还有一点就是，只有当三个数满足等式才可以逆推。
赛前JJ曾说这题可能比F还简单，结果不知道什么原因大家都不敢碰。。

H Cover the String      现场赛0.00% (0/13)/同步赛2.43% (1/41)
中等偏难的动态规划题，需要好好优化才能把复杂度降下来。我的做法是：首先用所有的tiles构造一个trie。用s[i, j]表示原串从i到j的子串。然后考虑从后往前用tile来覆盖串，根据规则，每次放的串起始位置要在上一个之前，结束位置也要在上一个之前。dp[i][j]表示覆盖原串从第i位开始到最后的子串，且最后一个使用的tile覆盖了s[i, j]的方法数。还有一个sum数组，sum[i]表示当前所有的覆盖中，最后一个tile开始于原串第i位或者之前，结束于第i位之后数量。
for i from n - 1 to 0
  for j from i to n - 1  // 考虑覆盖s[i, j]
    dp[i][j] = (number of tiles cover s[i, j]) * sum[j];
  for j from n - 1 to i + 1 // 更新sum数组
    sum[j - 1] += Sum(dp[i][j] .. dp[i][n - 1]);
最后Sum(dp[0][0] .. dp[0][n - 1])就是解。其中number of tiles cover s[i, j]可以用trie在O(1)时间内得到，Sum(dp[i][j] .. dp[i][n - 1])这块可以用一个临时变量累加来优化成O(1)，因此整个dp过程复杂度为O(1000^2)。考虑到子串的长度最多为200，因此可以把j这层循环变成tile的长度，这样复杂度变成O(1000*200)，不包括前面建trie的时间。
如果不想使用trie，可以用kmp算法来预处理，同样可以在O(1)时间得到number of tiles cover s[i, j]。

I Nine Interlinks      现场赛28.29% (116/410)/同步赛37.54% (202/538)
简单的动态规划题，应该不难找到递归方程，就算不会动规，应该也能找到规律来求解。要把前n个变成on，首先把前n-1个变成on，然后把前n-2个变成off，然后把第n个变成on，然后把前n-2个变成on。所以dp[1] = 1, dp[2] = 2, dp[i] = dp[i - 1] + dp[i - 2] * 2 + 1。

Division summary - 2009 TCO Algorithm - Elimination Round 1, division 1

 这要命的比赛，害我昨晚都没怎么睡着……攒rp。。。

好久没有写过一篇正常的日志了。

现在我的耳边环绕着N首曲子，有千千里的Zard，博客里的周惠，还有开老电脑的开机音乐。我觉得，我喜欢一切的音乐。

好像很多事情都是这样，我都喜欢，不知道这是好还是不好。也许是好吧，可能也不太好。

想写Marathon，想了一下，甚至把准备工作也都做好了，我还是放弃了。也许是这真的超出了我的能力范围，也许我本就不适合这个，也许是有了rating我不敢再乱玩了，又也许是我可以但却懒得懂脑子，总之，现在决定不去碰它。

回家了很奇怪，很多次睡不着，要起来看下推理/杀人故事才能睡着，很bt啊。。

很快就要回校了，还是听混沌的。

最近也发现，我比较喜欢回味过去，过去的痕迹。可惜已经回不去那个当时了，很多的事情我也早已想不起来，很多的痕迹，也早已经在岁月的擦洗中被抹去了。

停止一切声音，下面是我的时刻。

Division summary of ZJUer

好久没写过这么搓的250了，写的时候觉得脑子爆炸了，其实本来几行就可以搞定的，我用了个很麻烦的方法来算……还好500的时候恢复了点。1000的时候，也静不下心来想了。还好最后cha了100分，不然就跌了，cha王道啊……

Division summary of ZJUer

一场很水的比赛，神奇地cha了3个人拿了第一 -_-。。。没什么好说的……

Division summary of ZJUer

N个星期前的比赛了，因为TC统计的那个网站一直挂着所以到现在才写，是crazyb0y出的一套题。

250是很强大的暴力dfs，还好我很快就想到了，没浪费太多时间。

500又是暴力题，暴力枚举直接搞，写了N长N暴力的程序，还好最后过了。

1000是生成树计数，yy dp方法，最重还是不会……

Division summary of ZJUer

250就是一句GCD，我发呆然后在纸上推了好久才推出来，只有224分，太弱了。。。

600是找循环，很快就写完了，不过花了4分钟来测试，本来分数还可以高一点的，不过还是准确率第一。。

900我基本上找到了方法，但是复杂度估计错了，需要再优化一个地方才可以不TLE。。。

这次录了screencast，看了发现自己打字真慢，而且经常打错字，下次做的时候要刻意避免一下了。。

三个半路出家的人，给ZJU填上了新的一笔，感谢我的队友。

Focus，好好干活，准备Final。