2016-C03-team5

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 流水账 ==
=== jcq1234 === 
今天前期还不错，学长们很强势，分别拿下了I题和F题的FB。后面感觉选题有问题，点开了几道题感觉都不太可做，
最后决定做C题和D题，D题很快就有思路了，但是没想到欧洲的自然数是从1开始的，一直WA，然后也找不出bug，一共
提交了20次都没过...
C题看到时限只有0.1s，感觉应该是个推公式的题目，但是最终还是没有推出来。正常比赛主要浪费了大量时间在D题，
代码逻辑正确但是以为有错，疯狂debug，应该用枚举题意的方法。

== 总结 ==

=== jcq1234 ===
 * 数学题一时半会做不出来就该果断弃掉，太浪费时间。
 * 题意不清时要按照一定顺序枚举题意，不能太死板
 * 选题目还是要选对，这次就没发现H题可以做
 * 总是还是缺少比赛经验

=== wtthhh ===
 * 今天题目比较难，选题比较重要
 * 写完前两题之后想写A题的，但写到一半的时候突然感觉这个数据可以出的非常严格，很容易卡掉随机化。。但实际上并没有，应该坚持写掉A题的
 * 放弃A题之后写B题，场上想的算法感觉时间复杂度比较极限。。结果最后也没过掉。。发现是LCA倍增开小了，应该开到20以上，少算了一个0。。。但是赛后测还是T了，这种题应该放在比赛最后做，不应该中场去做没有把握的题
 * H题是比较可做的题，如果比赛的时候多花点时间的话应该能过掉。。但是时间全浪费在B了
 * 总体来说还是要注意做题顺序，正确性没有把握的题即使有思路也不要马上写，很容易被卡全场

=== triomino === 
 * G题想到做法但是程序写差wa了两次，应该多手测几组数据再交。
 * D题占用太多时间，并且没有发现H可做。（事实上稍微想了一下H，但是没有深入思考）

 == 题解 ==


=== B ===
修改多，询问少，应该考虑修改复杂度较低，询问复杂度稍高的算法。
分块，O(1)修改，sqrt(n)查询

=== E ===
对所有点跑最短路，之后用K^4的状压DP


=== D ===
如果a和b不相等，a+n和b+n的最大公约数一定是|b-a|的一个约数，枚举|b-a|的约数g，对每个g，找到这样的数对i和j,
使g*i和g*j分别是a+n和b+n，且i，j互质，可以用O(1)的时间找到。

流水账

jcq1234

今天前期还不错，学长们很强势，分别拿下了I题和F题的FB。后面感觉选题有问题，点开了几道题感觉都不太可做，

最后决定做C题和D题，D题很快就有思路了，但是没想到欧洲的自然数是从1开始的，一直WA，然后也找不出bug，一共

提交了20次都没过...

C题看到时限只有0.1s，感觉应该是个推公式的题目，但是最终还是没有推出来。正常比赛主要浪费了大量时间在D题，

代码逻辑正确但是以为有错，疯狂debug，应该用枚举题意的方法。

总结

jcq1234

• 数学题一时半会做不出来就该果断弃掉，太浪费时间。
• 题意不清时要按照一定顺序枚举题意，不能太死板
• 选题目还是要选对，这次就没发现H题可以做
• 总是还是缺少比赛经验

wtthhh

• 今天题目比较难，选题比较重要
• 写完前两题之后想写A题的，但写到一半的时候突然感觉这个数据可以出的非常严格，很容易卡掉随机化。。但实际上并没有，应该坚持写掉A题的
• 放弃A题之后写B题，场上想的算法感觉时间复杂度比较极限。。结果最后也没过掉。。发现是LCA倍增开小了，应该开到20以上，少算了一个0。。。但是赛后测还是T了，这种题应该放在比赛最后做，不应该中场去做没有把握的题
• H题是比较可做的题，如果比赛的时候多花点时间的话应该能过掉。。但是时间全浪费在B了
• 总体来说还是要注意做题顺序，正确性没有把握的题即使有思路也不要马上写，很容易被卡全场

triomino

• G题想到做法但是程序写差wa了两次，应该多手测几组数据再交。
• D题占用太多时间，并且没有发现H可做。（事实上稍微想了一下H，但是没有深入思考）

题解

B

修改多，询问少，应该考虑修改复杂度较低，询问复杂度稍高的算法。

分块，O(1)修改，sqrt(n)查询

E

对所有点跑最短路，之后用K^4的状压DP

D

如果a和b不相等，a+n和b+n的最大公约数一定是|b-a|的一个约数，枚举|b-a|的约数g，对每个g，找到这样的数对i和j,

使g*i和g*j分别是a+n和b+n，且i，j互质，可以用O(1)的时间找到。