2018-Helianthus-C04

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(1.jpg,1200px)]]

[/wiki/2018-team3 返回Helianthus]

== 流水账 ==

=== day-1 ===
下午到西安的飞机，晚点了一个小时。到了西安坐上了CJB预定的车车，在路上写了写codechef月赛的challenge题，用了一个很naive的优化居然做到了最高分（有一大堆最高分）。到了酒店，跟sub住一起，看了一波新的vocaloid周刊，又黑了一波苹果。中山大学领航者的林一诺过来BG二队，我开心的凑了上去蹭了顿BG。吃完回来洗个澡就睡觉了。

=== day0 ===
早上睡到快11点，下来发现人都齐了。到了西工大签到，拍队伍小视频的时候疯狂摸heltion肚肚。签到发了个蛮实用的包包，衣服也还行。去了食堂发现是固定菜品和窗口，饭菜难吃，随便吃了点就倒了。在食堂呆了一会儿就去开幕式了。开幕式好像没啥好说的，除了帅气的裁判长吉老师。后来就进体育馆热身赛了。热身赛的前两题傻乎乎的，最后一题是个杜教筛，heltion一个人推了好久，然后放弃了。热身赛排名是Helianthus < Reconquista < Legilimens，CJB就过来奶，“正式赛会反过来的，跟去年一样”。期间随便调试了一些东西，感觉还是比较正常的，还有PYTHON，只是数组越界会返回WA。

热身完，lgl跟着高中同学跑了，Legilimens全队也自己跑了，我和heltion就跟着一队继续在食堂吃，晚餐稍微好一点，有一个鸡腿可以啃，而且人比较饿，吃啥都香。在回酒店的路上发现了看起来不错的面包店，买了点东西。回了酒店，非常困，先睡了两个小时。起来看了眼QQ，发现灿哥在CJB房间开会，赶紧跑了过去。灿哥走了，我跑到队友寝室，稍微强调了下读题，就又跑到了CJB房间。旁观了yzc调焦作的C，调完还帮我写了codechef最后一个数据结构题，一下子就写完过了样例，扔给了我，我一交直接过了，yzcnb！sub又提出想再加强一下challenge题的算法，写了好久，尝试各种stl的危险操作，最后发现是根号算法会TLE，哭哭。回到房间，室友变成了jsb，jsb一顿吐槽，“CJB打鼾真的响！”。jsb惯例又在连麦，gtmd连麦狗！因为之前睡了会儿，不太困，水手机水到了两点，感觉不能水了，把手机扔远，但也过了好久才睡着。

=== day1 ===
酒店离学校近，可以七点四十才起床，比其他赛区好。早上在大厅退房，顺便喂了队友面包吃。退了房就赶到了西工大，在看台一角堆了行李，然后拖着一箱板子进了场馆。

开场还是老的开题顺序，我在机位登陆，heltion中间，lgl最后开始看题。我A题没读完，刷了刷榜发现D题已经被切了，叫heltion看了看题意，然后跟我说是个博弈，他不太会，我让他告诉我题意，我听完第一反应，“这不是比较一下大小就好了？”。heltion呆了下，点了点头，坐上机子签到，我继续读A，'''D1y10'''。我读完了A，猜了个等差数列的结论，WA了两发，感受到了这题的不可做性，放弃。看了看榜，发现L题被切，提醒队友做L题。我继续看B，直接感受到了不可做性，尝试性的翻了翻数列表，果然没有，放弃。队友讨论完L题，写了一半，突然吵了起来，heltion:“lgl你题意又读错了！” lgl：挠头。我继续看了看C，感觉也不可做。~~此时好像听到后面南大的calabash队说了什么中国剩余定理。~~期间队友还是有惊无险的过了L题，'''L2y48'''。heltion告诉了我E题题意，我上机猜了个结论，果然boom了，下机思考得到了枚举所有状态然后N方DP的方法，尝试思考N三方的DP，无果。lgl此时开出了I题，一会儿就过了，'''I1y84'''。

heltion跟我讨论了下计算几何F题，我直接说是肯定走切点，然后口胡了个证明，heltion又问怎么判是否跟圆交，我想了下感觉就是算出线段到点距离判一判，然后就交给了heltion推了推，heltion不知怎的就偷偷交了一发，WA了。期间我发现了道G题，感觉比较有趣且适合我，拉着lgl一起讨论，先猜了一个“只要符合基本条件就有解”的结论，然后直接选了个最直接的构造方法，挑相邻的B分到一组去，然后再考虑不同位置的C塞到哪里去，考虑了一会儿感觉大概会做了。heltion又偷偷交了一发，过了，'''F2y117'''。我上机写起了G，写了大概40分钟，期间理清了思路，又自信的用了简单的shift策略解决内部C放置位置和单次构造失败的问题。努力地测了测奇怪的数据，都可以，交了一发，RE，代码中的assert发挥了作用。检查了一下发现统计空余C的个数计错了，改了下，交了一发，WA。看了看榜，也有队伍在写这题，有点慌。我便写了个数据生成器和内部checker，对了下果然出了问题。此时队友已经会做了J，lgl上机码了起来，我在一旁看着调试信息。看了一会儿感觉输出方案很奇怪，发现上机把位移量还原的时候还原错了，上机改了改，又拍了一下，就交了，换lgl上机写J。pending了一会儿，返回一个correct，'''G3y227'''，看了下榜果然是一血，有点爽。然后让heltion跟我说了说J题题意，我听了一会儿，感觉时间还多，不太想仔细听，就让他两一起写，我去想剩下题里过的最多的C题。过了一会儿lgl写好，测了一些东西，感觉很对，交了一发，correct！'''J1y244'''。

接下来全队想C题，我和heltion先猜了个01串总数可能不多，写了个hash测验了下，发现个数很多，放弃这个想法。我就猜是不是根据4,9,25这种质数平方，做个crt筛一下~~然后就想起来之前听到了crt~~，感觉有可能，但是如果不确定mo某一质数平方时，heltion提议直接把这组删了，我本想暴搜，但觉得heltion的办
法靠谱点（实际上加上更多的平方质数暴搜反而能减枝，现场没有冷静思考），开始RUSH。抄crt的板子时还遇到了一些问题，解决了后通过了样例，交了一发，看了眼时间，只剩10min，过了一会儿，返回了个TLE。此时没什么办法，交了几发卡时，最后几发一直pending到赛后，都在WA和TLE间徘徊。

结束后，跟Legilimens和Reconquista交流了下，二队在A题上爆炸了，一队过了C，问了下方法，的确是暴搜啥的。颁奖典礼的时候本来想上去三次，领一次最快解题奖，帮高中同学领个银牌，再领个金牌，结果lgl想要领金牌，争不过lgl就让lgl去了。领完奖迅速地溜了。

这次ec final是我们队参赛以来发挥最好的一次，没有太多卡题，想法也来的比较快，码力发挥也正常。我们离第七题C题的正解也很近，只是差了些时间和运气。前期少浪费一些时间，再给C题留出30分钟左右，感觉我们是有机会做出C题的。如果七题就能亚军了。不过也只能想想。

Helianthus这赛季算是圆满结束了，赛季全金，最快解题奖，甚至假装在ecfinal出了个线，在此感谢两个队友 @jhguai @heltion。明年应该是旅游了，嘿嘿。

update:最后并没有出线

== 题解 & 补题 ==

== Standings ==
see the attachments

[/wiki/2018-team3 返回Helianthus]

流水账

day-1

下午到西安的飞机，晚点了一个小时。到了西安坐上了CJB预定的车车，在路上写了写codechef月赛的challenge题，用了一个很naive的优化居然做到了最高分（有一大堆最高分）。到了酒店，跟sub住一起，看了一波新的vocaloid周刊，又黑了一波苹果。中山大学领航者的林一诺过来BG二队，我开心的凑了上去蹭了顿BG。吃完回来洗个澡就睡觉了。

day0

早上睡到快11点，下来发现人都齐了。到了西工大签到，拍队伍小视频的时候疯狂摸heltion肚肚。签到发了个蛮实用的包包，衣服也还行。去了食堂发现是固定菜品和窗口，饭菜难吃，随便吃了点就倒了。在食堂呆了一会儿就去开幕式了。开幕式好像没啥好说的，除了帅气的裁判长吉老师。后来就进体育馆热身赛了。热身赛的前两题傻乎乎的，最后一题是个杜教筛，heltion一个人推了好久，然后放弃了。热身赛排名是Helianthus < Reconquista < Legilimens，CJB就过来奶，“正式赛会反过来的，跟去年一样”。期间随便调试了一些东西，感觉还是比较正常的，还有PYTHON，只是数组越界会返回WA。

热身完，lgl跟着高中同学跑了，Legilimens全队也自己跑了，我和heltion就跟着一队继续在食堂吃，晚餐稍微好一点，有一个鸡腿可以啃，而且人比较饿，吃啥都香。在回酒店的路上发现了看起来不错的面包店，买了点东西。回了酒店，非常困，先睡了两个小时。起来看了眼QQ，发现灿哥在CJB房间开会，赶紧跑了过去。灿哥走了，我跑到队友寝室，稍微强调了下读题，就又跑到了CJB房间。旁观了yzc调焦作的C，调完还帮我写了codechef最后一个数据结构题，一下子就写完过了样例，扔给了我，我一交直接过了，yzcnb！sub又提出想再加强一下challenge题的算法，写了好久，尝试各种stl的危险操作，最后发现是根号算法会TLE，哭哭。回到房间，室友变成了jsb，jsb一顿吐槽，“CJB打鼾真的响！”。jsb惯例又在连麦，gtmd连麦狗！因为之前睡了会儿，不太困，水手机水到了两点，感觉不能水了，把手机扔远，但也过了好久才睡着。

day1

酒店离学校近，可以七点四十才起床，比其他赛区好。早上在大厅退房，顺便喂了队友面包吃。退了房就赶到了西工大，在看台一角堆了行李，然后拖着一箱板子进了场馆。

开场还是老的开题顺序，我在机位登陆，heltion中间，lgl最后开始看题。我A题没读完，刷了刷榜发现D题已经被切了，叫heltion看了看题意，然后跟我说是个博弈，他不太会，我让他告诉我题意，我听完第一反应，“这不是比较一下大小就好了？”。heltion呆了下，点了点头，坐上机子签到，我继续读A，D1y10。我读完了A，猜了个等差数列的结论，WA了两发，感受到了这题的不可做性，放弃。看了看榜，发现L题被切，提醒队友做L题。我继续看B，直接感受到了不可做性，尝试性的翻了翻数列表，果然没有，放弃。队友讨论完L题，写了一半，突然吵了起来，heltion:“lgl你题意又读错了！” lgl：挠头。我继续看了看C，感觉也不可做。此时好像听到后面南大的calabash队说了什么中国剩余定理。期间队友还是有惊无险的过了L题，L2y48。heltion告诉了我E题题意，我上机猜了个结论，果然boom了，下机思考得到了枚举所有状态然后N方DP的方法，尝试思考N三方的DP，无果。lgl此时开出了I题，一会儿就过了，I1y84。

heltion跟我讨论了下计算几何F题，我直接说是肯定走切点，然后口胡了个证明，heltion又问怎么判是否跟圆交，我想了下感觉就是算出线段到点距离判一判，然后就交给了heltion推了推，heltion不知怎的就偷偷交了一发，WA了。期间我发现了道G题，感觉比较有趣且适合我，拉着lgl一起讨论，先猜了一个“只要符合基本条件就有解”的结论，然后直接选了个最直接的构造方法，挑相邻的B分到一组去，然后再考虑不同位置的C塞到哪里去，考虑了一会儿感觉大概会做了。heltion又偷偷交了一发，过了，F2y117。我上机写起了G，写了大概40分钟，期间理清了思路，又自信的用了简单的shift策略解决内部C放置位置和单次构造失败的问题。努力地测了测奇怪的数据，都可以，交了一发，RE，代码中的assert发挥了作用。检查了一下发现统计空余C的个数计错了，改了下，交了一发，WA。看了看榜，也有队伍在写这题，有点慌。我便写了个数据生成器和内部checker，对了下果然出了问题。此时队友已经会做了J，lgl上机码了起来，我在一旁看着调试信息。看了一会儿感觉输出方案很奇怪，发现上机把位移量还原的时候还原错了，上机改了改，又拍了一下，就交了，换lgl上机写J。pending了一会儿，返回一个correct，G3y227，看了下榜果然是一血，有点爽。然后让heltion跟我说了说J题题意，我听了一会儿，感觉时间还多，不太想仔细听，就让他两一起写，我去想剩下题里过的最多的C题。过了一会儿lgl写好，测了一些东西，感觉很对，交了一发，correct！J1y244。

接下来全队想C题，我和heltion先猜了个01串总数可能不多，写了个hash测验了下，发现个数很多，放弃这个想法。我就猜是不是根据4,9,25这种质数平方，做个crt筛一下然后就想起来之前听到了crt，感觉有可能，但是如果不确定mo某一质数平方时，heltion提议直接把这组删了，我本想暴搜，但觉得heltion的办

法靠谱点（实际上加上更多的平方质数暴搜反而能减枝，现场没有冷静思考），开始RUSH。抄crt的板子时还遇到了一些问题，解决了后通过了样例，交了一发，看了眼时间，只剩10min，过了一会儿，返回了个TLE。此时没什么办法，交了几发卡时，最后几发一直pending到赛后，都在WA和TLE间徘徊。

结束后，跟Legilimens和Reconquista交流了下，二队在A题上爆炸了，一队过了C，问了下方法，的确是暴搜啥的。颁奖典礼的时候本来想上去三次，领一次最快解题奖，帮高中同学领个银牌，再领个金牌，结果lgl想要领金牌，争不过lgl就让lgl去了。领完奖迅速地溜了。

这次ec final是我们队参赛以来发挥最好的一次，没有太多卡题，想法也来的比较快，码力发挥也正常。我们离第七题C题的正解也很近，只是差了些时间和运气。前期少浪费一些时间，再给C题留出30分钟左右，感觉我们是有机会做出C题的。如果七题就能亚军了。不过也只能想想。

Helianthus这赛季算是圆满结束了，赛季全金，最快解题奖，甚至假装在ecfinal出了个线，在此感谢两个队友 @jhguai @heltion。明年应该是旅游了，嘿嘿。

update:最后并没有出线

题解 & 补题

Standings

see the attachments

附加文件