2017-C03-team1

从 Trac 迁移的文章

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

原文章内容如下：

== JSB ==

流水账：今天的状态十分糟糕。前期签到的时候，由于对一些模板化的做法接触地太多，并没有仔细地考虑时空效率，导致我一道字符串题先后换了后缀自动机、AC自动机，直到最后写了exkmp才过。3题后，我和shb学长通过不断地讨论（其实都是他在关键时刻反应过来），终于过了1005（应该说只有这道题是我在这场比赛里唯一满意的配合）。至此，比赛进行到2:17，我们过了四题，而且这之后再也没有提交了= =所以说，后半段的安排和思考已经不能用糟糕来形容了。我们最先关注1001（因为榜上过的队实在太多了），然而并没有什么可行的思路，只能构出大概2倍的情况。在这尴尬的卡题环节，我尝试去写1001的随机，希冀着能为我们带来一些想法，然后shb和lsmll学长开始讨论1009。然而结果都不尽人如意，随机没啥用，他们也捣鼓不出什么。在这段时间可以说我身心俱疲——这也暴露出我们队在这种时候没有任何救火措施，不堪一击。随后我和shb学长试着讨论了1006的线段树做法，虽然基本想出，但是可能思路有点偏，堡堡并不太能写出来；在他写的时候我也和lsmll学长试着讨论了1008，但没多想也放弃了。最后1h，主要由于榜的原因，我们重新一起看1001，然而直到最后都没能成功想出。

总结： 今天比赛暴露出了我们合作的很多问题，值得好好反思。
①有时候榜可能会歪，千万不要太轻信榜。当时在和shb学长想1006最后细节的时候，我甚至萌生出了“这题或许要刚一整场才能出，而1001这么多人过了肯定能轻松做出，做1006太不划算了”这种消极的想法，导致并不想细想，还把锅甩给了堡学长。像1001这种智商题，我们应该规定一个具体的时间，如果仍然没有任何思路就果断放弃。
②与上一点相似，最好我们有一个科学的规划，谁在机上写，谁去想（或者谁谁去讨论）哪一题，这样可能可以减少很多无效的思考。
③流水账题提到过，即使对于一些画风很熟悉的题，还是要多考虑考虑具体写法。很容易掉进一些时空限制的坑里，轻则增加些罚时，重则造成浪费大量时间。
④有关交流方面，虽然我觉得我已经很尽力了，但是我们仍然没有做到那种完全“畅快”的交流。可能是我们过于谨慎，喜欢在有一个成熟的想法再交流。这一点希望以后能进一步磨合，使三方更多能促进彼此的思维。
⑤有以上那么多的理由，也不足以解释为什么最后我们只过了四题。

其他：在搞学长的建议下，我去看了watashi学长的Final历程。即使没有找到传说中的源代码里的秘密，我还是被他的语言深深感动了。特别是他提到的“赛前我们也经过了不少的训练和调整，相识3年，磨合10月，才使得我们能有今天的表现”，“虽然即便不到5000小时也相差不远”……我看到了一位为了梦想而真正不懈追求的学长，我也希望能成为像他一样的人。

== shb ==

流水账：出门看了前几题。感觉1001和1002都不太会做，然后1003感觉像ramsey定理，但是有个不知所云的M，又有点不确定。过了一会儿改了题面，我感觉可以直接上。结果读入了3000*3000的矩阵，被坑了一发MLE。然后蒋爷爷跟我讲了1004，觉得是个SAM，我感觉很对，就让他上去写。过了一会儿过了样例，但是交上去T了。仔细看了一下，感觉字符集太大，其实还会MLE。于是又改成了AC自动机，结果T了。。。然后我们决定冷静一下，我看了一会儿， 感觉二分加hash就行了，跟蒋爷爷说了一下，他说这不就是扩展KMP么。于是我就上去敲了，过了样例就A了。过了以后sm学长表示会写1007的数位DP了，于是就让他上了，我们去努力淦1005。1007写了一会儿就过了。1005我猜了个结论，以为特判5就行了（naive），喜WA。修了半天，发nao现bu其实把两种情况扩充成四种就行了。这时候是2h17min，4题还可以接受。但是接下来的时间非常绝望。我们分头努力构造1001，但是到比赛结束都没有构造出来。中间讨论了一下1006，知道了做法，但是因为没有抽象成矩阵，所以每个节点要维护大量的信息，而且还有很多特殊情况，感觉并不能写。于是就悲惨地4题结束了。

总结： 
1、这场可以说是打的相当烂。按搞学长的说法这就是下限了（flag？）。之前两场因为题目简单所以排名还可以，但是这场题一难之前存在的问题就造成了严重的后果。首先是交流问题。比赛的时候能明显感觉到我们队太过安静了，大家都闷头想题，但是很多题都是一个人很难做的，需要在交流里互相推动各自的想法，这样才是有效率的。此外这样也会让队伍里的气氛比较沉闷，到很久没过题的后期思维强度肯定会下降，心态不好，效率会变得非常低。我感觉确实应该多说说话，就算是不成熟甚至好笑的想法，也可能推动其他人的思考。

2、感觉我们三个人似乎都不是很擅长构造一类的需要脑zhi洞shang的题。可能应该多做点TC什么的提高智商？

3、也许还应该学一波说学逗唱。。

4、下次不能开太多题。一旦过不了很可能对心态产生影响。此外要学会放弃淦不动的题，不要消耗太多的时间在同一个题上。

5、不要被榜搞的心态太崩，放轻松。我们可是要努力成为能带榜的人（雾）。很多时候有的题虽然没什么人过，但其实并不是太难。今天这个1008就完全是可做题，但是我们开的有点迟，如果心态不崩很有可能是能做出来的。

一起加油。。

== lsmll ==

流水账：还是从后面开始看。1011看到复杂的公式，试图理解了一会，没有成果，就跳过了，然后看1010，感觉也是难题没什么思路。后来看到有人过了1004，于是就开始讨论那题，后来决定由jsb学长写后缀自动机。于是我就开始看别的题。此时shb和我说了1003不会超过6个顶点的结论，我们不会证明但是感觉是对的，此时jsb的1004得到TLE，于是让shb去写1003，保险起见让他写的时候开了100的阈值。看了1009，推了一会方程感觉不太行，后来和shb一起初步讨论1001，并弄明白了什么是点覆盖。后来感觉没什么思路就开始看别的题，看了1007感觉一个不难的数位DP，想了一会感觉可做，此时jsb学长的1004遇到了问题。再次获得TLE，于是我就上机写，第一次写完WA了样例，于是打印后又让jsb改1003，期间我发现了代码的一个bug，之后jsb发现有点问题下机，于是我上机调试通过样例，提交后AC。之后就陷入了僵局，我再次推1009没有进展，试图证明小圆的圆心在一个圆上，没有成功。看到1008有人过了，我看一下感觉可能是DP，也可能是流，但是后来感觉不是流。我刚开始以为没有负权值于是想了一个来回走的结论，但是后来发现有负的，感觉可能不太好DP，而且1001过的人相比1008很多，于是后来我们全力想1001，但是我们以为非最优答案中的点连到答案中的点是对称的，导致没有得到正确答案，只能做到两倍。最后到比赛结束也没做出1001。

总结：本场比赛打得很不好，前期虽然还可以，但是第四题通过后的近三小时里就没了进展。我认为我们下次不应该卡在一题上，比如1001我们花了前后大概快三个小时了。一般来说，随着时间花的越多，越到后面做出一道题的概率就越低。我们当时应该及时换题，其实1008的DP方式我以前见到过，如果当时继续做1008的的话，我认为很有可能通过。教练组赛后指导的很对，我们要出线的话应该是带榜的，虽然榜固然有一定参考价值，但也不能太依赖于榜，陷入困境要果断作出调整。另外，我们确实三人沟通的还不够，以后也要注意。


== 题解 ==

http://www.cnblogs.com/post/readauth?url=/jiangshibiao/p/7399201.html  密码：dlajmgmomo

== 补题 ==

1001[jsb,lsmll]

1002[lsmll]

1006[jsb]

1008[jsb,lsmll,shb]

1009[shb]

1010[]

1011[]

[[Image(08.png)]]

JSB

流水账：今天的状态十分糟糕。前期签到的时候，由于对一些模板化的做法接触地太多，并没有仔细地考虑时空效率，导致我一道字符串题先后换了后缀自动机、AC自动机，直到最后写了exkmp才过。3题后，我和shb学长通过不断地讨论（其实都是他在关键时刻反应过来），终于过了1005（应该说只有这道题是我在这场比赛里唯一满意的配合）。至此，比赛进行到2:17，我们过了四题，而且这之后再也没有提交了= =所以说，后半段的安排和思考已经不能用糟糕来形容了。我们最先关注1001（因为榜上过的队实在太多了），然而并没有什么可行的思路，只能构出大概2倍的情况。在这尴尬的卡题环节，我尝试去写1001的随机，希冀着能为我们带来一些想法，然后shb和lsmll学长开始讨论1009。然而结果都不尽人如意，随机没啥用，他们也捣鼓不出什么。在这段时间可以说我身心俱疲——这也暴露出我们队在这种时候没有任何救火措施，不堪一击。随后我和shb学长试着讨论了1006的线段树做法，虽然基本想出，但是可能思路有点偏，堡堡并不太能写出来；在他写的时候我也和lsmll学长试着讨论了1008，但没多想也放弃了。最后1h，主要由于榜的原因，我们重新一起看1001，然而直到最后都没能成功想出。

总结： 今天比赛暴露出了我们合作的很多问题，值得好好反思。

①有时候榜可能会歪，千万不要太轻信榜。当时在和shb学长想1006最后细节的时候，我甚至萌生出了“这题或许要刚一整场才能出，而1001这么多人过了肯定能轻松做出，做1006太不划算了”这种消极的想法，导致并不想细想，还把锅甩给了堡学长。像1001这种智商题，我们应该规定一个具体的时间，如果仍然没有任何思路就果断放弃。

②与上一点相似，最好我们有一个科学的规划，谁在机上写，谁去想（或者谁谁去讨论）哪一题，这样可能可以减少很多无效的思考。

③流水账题提到过，即使对于一些画风很熟悉的题，还是要多考虑考虑具体写法。很容易掉进一些时空限制的坑里，轻则增加些罚时，重则造成浪费大量时间。

④有关交流方面，虽然我觉得我已经很尽力了，但是我们仍然没有做到那种完全“畅快”的交流。可能是我们过于谨慎，喜欢在有一个成熟的想法再交流。这一点希望以后能进一步磨合，使三方更多能促进彼此的思维。

⑤有以上那么多的理由，也不足以解释为什么最后我们只过了四题。

其他：在搞学长的建议下，我去看了watashi学长的Final历程。即使没有找到传说中的源代码里的秘密，我还是被他的语言深深感动了。特别是他提到的“赛前我们也经过了不少的训练和调整，相识3年，磨合10月，才使得我们能有今天的表现”，“虽然即便不到5000小时也相差不远”……我看到了一位为了梦想而真正不懈追求的学长，我也希望能成为像他一样的人。

shb

流水账：出门看了前几题。感觉1001和1002都不太会做，然后1003感觉像ramsey定理，但是有个不知所云的M，又有点不确定。过了一会儿改了题面，我感觉可以直接上。结果读入了3000*3000的矩阵，被坑了一发MLE。然后蒋爷爷跟我讲了1004，觉得是个SAM，我感觉很对，就让他上去写。过了一会儿过了样例，但是交上去T了。仔细看了一下，感觉字符集太大，其实还会MLE。于是又改成了AC自动机，结果T了。。。然后我们决定冷静一下，我看了一会儿， 感觉二分加hash就行了，跟蒋爷爷说了一下，他说这不就是扩展KMP么。于是我就上去敲了，过了样例就A了。过了以后sm学长表示会写1007的数位DP了，于是就让他上了，我们去努力淦1005。1007写了一会儿就过了。1005我猜了个结论，以为特判5就行了（naive），喜WA。修了半天，发nao现bu其实把两种情况扩充成四种就行了。这时候是2h17min，4题还可以接受。但是接下来的时间非常绝望。我们分头努力构造1001，但是到比赛结束都没有构造出来。中间讨论了一下1006，知道了做法，但是因为没有抽象成矩阵，所以每个节点要维护大量的信息，而且还有很多特殊情况，感觉并不能写。于是就悲惨地4题结束了。

总结：

1、这场可以说是打的相当烂。按搞学长的说法这就是下限了（flag？）。之前两场因为题目简单所以排名还可以，但是这场题一难之前存在的问题就造成了严重的后果。首先是交流问题。比赛的时候能明显感觉到我们队太过安静了，大家都闷头想题，但是很多题都是一个人很难做的，需要在交流里互相推动各自的想法，这样才是有效率的。此外这样也会让队伍里的气氛比较沉闷，到很久没过题的后期思维强度肯定会下降，心态不好，效率会变得非常低。我感觉确实应该多说说话，就算是不成熟甚至好笑的想法，也可能推动其他人的思考。

2、感觉我们三个人似乎都不是很擅长构造一类的需要脑zhi洞shang的题。可能应该多做点TC什么的提高智商？

3、也许还应该学一波说学逗唱。。

4、下次不能开太多题。一旦过不了很可能对心态产生影响。此外要学会放弃淦不动的题，不要消耗太多的时间在同一个题上。

5、不要被榜搞的心态太崩，放轻松。我们可是要努力成为能带榜的人（雾）。很多时候有的题虽然没什么人过，但其实并不是太难。今天这个1008就完全是可做题，但是我们开的有点迟，如果心态不崩很有可能是能做出来的。

一起加油。。

lsmll

流水账：还是从后面开始看。1011看到复杂的公式，试图理解了一会，没有成果，就跳过了，然后看1010，感觉也是难题没什么思路。后来看到有人过了1004，于是就开始讨论那题，后来决定由jsb学长写后缀自动机。于是我就开始看别的题。此时shb和我说了1003不会超过6个顶点的结论，我们不会证明但是感觉是对的，此时jsb的1004得到TLE，于是让shb去写1003，保险起见让他写的时候开了100的阈值。看了1009，推了一会方程感觉不太行，后来和shb一起初步讨论1001，并弄明白了什么是点覆盖。后来感觉没什么思路就开始看别的题，看了1007感觉一个不难的数位DP，想了一会感觉可做，此时jsb学长的1004遇到了问题。再次获得TLE，于是我就上机写，第一次写完WA了样例，于是打印后又让jsb改1003，期间我发现了代码的一个bug，之后jsb发现有点问题下机，于是我上机调试通过样例，提交后AC。之后就陷入了僵局，我再次推1009没有进展，试图证明小圆的圆心在一个圆上，没有成功。看到1008有人过了，我看一下感觉可能是DP，也可能是流，但是后来感觉不是流。我刚开始以为没有负权值于是想了一个来回走的结论，但是后来发现有负的，感觉可能不太好DP，而且1001过的人相比1008很多，于是后来我们全力想1001，但是我们以为非最优答案中的点连到答案中的点是对称的，导致没有得到正确答案，只能做到两倍。最后到比赛结束也没做出1001。

总结：本场比赛打得很不好，前期虽然还可以，但是第四题通过后的近三小时里就没了进展。我认为我们下次不应该卡在一题上，比如1001我们花了前后大概快三个小时了。一般来说，随着时间花的越多，越到后面做出一道题的概率就越低。我们当时应该及时换题，其实1008的DP方式我以前见到过，如果当时继续做1008的的话，我认为很有可能通过。教练组赛后指导的很对，我们要出线的话应该是带榜的，虽然榜固然有一定参考价值，但也不能太依赖于榜，陷入困境要果断作出调整。另外，我们确实三人沟通的还不够，以后也要注意。

题解

http://www.cnblogs.com/post/readauth?url=/jiangshibiao/p/7399201.html 密码：dlajmgmomo

补题

1001[jsb,lsmll]

1002[lsmll]

1006[jsb]

1008[jsb,lsmll,shb]

1009[shb]

1010[]

1011[]

附加文件