2018-Helianthus-C02
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.jpg,1000px)]]
[/wiki/2018-team3 返回Helianthus]
== 流水账 ==
'''DAY -1'''
早上坐高铁，中午到了北京，啥事也没干。
'''DAY 0'''
去北大签到，开幕式，热身赛。热身赛都是往年北京的题，A题大前天刚训过，我开心的回忆了一遍代码，抢了个一血。之后给lgl敲了BC，蛇形矩阵敲了半天。D题是去年北京的几何题，想随便判一判，结果又卡死了，De出了一堆bug后终于过了。晚饭蹭了北京的高中同学的生日饭，但路上北京的冷风吃太多了，涨的基本没吃啥。回了宾馆发现没带英语字典，四处借了半天发现隔壁sample_text就有。跟队友随便聊了聊就睡觉去了。
'''DAY 1'''
早饭又去吃了KFC。到场馆里的时候已经挺晚了，大部分队伍都在了。开始之后我搞了下登录，读了读A题，发现是个签到题，写了一发，WA了。突然发现我判环写成了判树，马上改成了跑DAG的方式，'''A2y18'''。之后队友给我说B题，也是个模拟题，我码了好一会儿，又拉着队友测了测各种情况，结果还是WA了一发。我又测了测几组数据，发现提取不到之后没有空格或回车的最后一个单词，改了就过了，'''B2y54'''。
heltion开出了D，上机敲了一会儿，WA了。期间lgl又跟我说了一道I题，我一个人补充了细节，上机写I，在位数上纠结了一会儿，所幸1A了，'''I1y98'''。期间heltion改过几次D，都WA了。之后heltion继续修改D，我和lgl讨论了H题。想了一会儿我就想到了数位DP套AC自动机的正解，而heltion也终于过了D，'''D5y104'''。lgl上机写起了H，我和heltion讨论了一会儿其他题。heltion问我关于C题的勾股数生成公式，以及G题的韦达定理，我说翻翻数学手册，但是没有去细翻。之后感觉J题很可做，我也马上提出了一个极角排序转圈圈的做法，维护90度和180度的xy坐标和，用叉积就可以快速求出很多三角形的面积和。lgl的H很快写完过了，'''H1y128'''。
J题大致思路有了，我就上机开始写。一开始我试图在固定基点，旋转主轴时维护四个象限内的xy值，考虑到1e18的范围和出题人是jls，判断90度和180度的方法都采用了叉积和点乘。写了很久之后发现过不了样例，看了看那个样例，发现三点共线时可能会转回来。期间heltion和lgl讨论别的题目也没有讨论出来，就来帮我debugJ题。heltion说可以两倍点数来判，并且让我删掉两个象限，但还是会卡在那个样例上，于是又加了一些其他的特判，终于过了样例，此时已经临近封榜，交了一发，TLE了。之后手造了一些数据，又发现了一些错误，不断修改，可始终是WA。莽了几发之后写了个对拍和数据生成器，发现答案相差很大，对拍一看还是三点共线的问题。但是我们所加的特判都没有能解决掉所有的情况。
== 总结 ==
=== LYK ===
前期A题我又傻逼了一下，觉得是签到题就没有细心想怎么判环，不小心判成了以小编号为父亲的树。B题我感觉写的还算稳健。heltion的D题不太清楚怎么回事会WA这么多发，GTMD何训。I题虽然lgl给我的做法比正解麻烦，但我也比较快地写出来了。H题我和lgl思考以及码代码的时间都很短，过的比较快。前面五题虽然AD有5发罚时，但因为节奏比较快，过的比较快，5题罚时还算优秀。
J题的思路其实比较简单，就是难在转圈圈的细节上。因为前期节奏快，lgl过了H后，我没怎么考虑J题细节就上机开始写了，第一次的写法比较麻烦，写的不是很久，但是时间一直花费在debug上。之后heltion在旁边辅助我debug，也还是没有debug出来。以前也补过类似的题，但是对三点共线或者精度的要求没有这么高。这个J题我写到后来，感觉就是在瞎凑边界的条件，根本没有冷静思考什么情况会出错，怎么去特判掉。
因为J题卡着，而队友也没有想出其他题目，所以机位一直是我的，我就一直在对着数据debug，效率低下，情绪烦躁。赛后想想CFG题其实都是有可能出的题。F题bitset暴力分块，我在赛后也大致往这个方向想过，但听到JSB就是这么过的，还是怀疑了一下复杂度。这题感觉lgl是可能想得到的。heltion也是有可能开出C题或者G题，但明知道数学手册上很可能有却不翻。如果有人上机把我从机位赶下来，让我下机冷静思考一下，我反而更有机会调出来。
滚完榜惊奇的发现没有同题队过第六个题，也就是说滚完榜我们名次没有变，五题RK6。但是RK1,2,3,4分别是10,9,8,7题，被一顿爆踩，根本开心不起来。
大概总结了下面几点：
* 写题前还是要多思考，哪怕有机位也要考虑清楚
* 比赛卡题不要紧张，不然交流的时候没有效率，也没法冷静思考，就像吉林的G题，北京的J题
* 感觉对着数据debug效率很容易烦躁，下机看看自己的代码，想想哪儿会出错，可能更好
* lyk回去多写写几何题
* heltion回去把数学手册全部扫一遍看看有啥
* lgl回去多涨涨姿势，后期不要发呆，努力多做出一题
* 接下来就训一训第一委员会出的题
=== Jhguai ===
=== Heltion ===
== 题解 & 补题 ==
* J ：赛后想清楚了细节，补题时1A了。思路比较简单，主要讲讲实现。极角排序同角度按幅长为第二关键字排序。转圈圈的时候先扩展两倍，用指针维护90/180度覆盖范围，除了90/180度限制外，还要判断：覆盖点数不能超过总点数；加入的下一点如果恰好同角度，则长度须大于当前轴。这样才能保证这个范围是正确的90/180度范围，不会出现绕了一圈回到自己这条轴的情况。
* F ：补题的时候把大致写法都想好了，写完过了编译就AC，很爽。做法：找出SCC后缩点。跑一遍DAG，用bitset统计每个点能到哪些点。统计时枚举异或值，从大到小，以32为一块，枚举这一块异或值（比如0-31）的总数，再与K判断，如果第K大在这块里面，就进去一个一个找。复杂度 MN/32+32QN
[/wiki/2018-team3 返回Helianthus]
流水账
DAY -1
早上坐高铁，中午到了北京，啥事也没干。
DAY 0
去北大签到，开幕式，热身赛。热身赛都是往年北京的题，A题大前天刚训过，我开心的回忆了一遍代码，抢了个一血。之后给lgl敲了BC，蛇形矩阵敲了半天。D题是去年北京的几何题，想随便判一判，结果又卡死了，De出了一堆bug后终于过了。晚饭蹭了北京的高中同学的生日饭，但路上北京的冷风吃太多了，涨的基本没吃啥。回了宾馆发现没带英语字典，四处借了半天发现隔壁sample_text就有。跟队友随便聊了聊就睡觉去了。
DAY 1
早饭又去吃了KFC。到场馆里的时候已经挺晚了，大部分队伍都在了。开始之后我搞了下登录，读了读A题，发现是个签到题，写了一发，WA了。突然发现我判环写成了判树，马上改成了跑DAG的方式，A2y18。之后队友给我说B题，也是个模拟题，我码了好一会儿，又拉着队友测了测各种情况，结果还是WA了一发。我又测了测几组数据，发现提取不到之后没有空格或回车的最后一个单词，改了就过了，B2y54。
heltion开出了D，上机敲了一会儿，WA了。期间lgl又跟我说了一道I题，我一个人补充了细节，上机写I，在位数上纠结了一会儿，所幸1A了，I1y98。期间heltion改过几次D，都WA了。之后heltion继续修改D，我和lgl讨论了H题。想了一会儿我就想到了数位DP套AC自动机的正解，而heltion也终于过了D，D5y104。lgl上机写起了H，我和heltion讨论了一会儿其他题。heltion问我关于C题的勾股数生成公式，以及G题的韦达定理，我说翻翻数学手册，但是没有去细翻。之后感觉J题很可做，我也马上提出了一个极角排序转圈圈的做法，维护90度和180度的xy坐标和，用叉积就可以快速求出很多三角形的面积和。lgl的H很快写完过了，H1y128。
J题大致思路有了，我就上机开始写。一开始我试图在固定基点，旋转主轴时维护四个象限内的xy值，考虑到1e18的范围和出题人是jls，判断90度和180度的方法都采用了叉积和点乘。写了很久之后发现过不了样例，看了看那个样例，发现三点共线时可能会转回来。期间heltion和lgl讨论别的题目也没有讨论出来，就来帮我debugJ题。heltion说可以两倍点数来判，并且让我删掉两个象限，但还是会卡在那个样例上，于是又加了一些其他的特判，终于过了样例，此时已经临近封榜，交了一发，TLE了。之后手造了一些数据，又发现了一些错误，不断修改，可始终是WA。莽了几发之后写了个对拍和数据生成器，发现答案相差很大，对拍一看还是三点共线的问题。但是我们所加的特判都没有能解决掉所有的情况。
总结
LYK
前期A题我又傻逼了一下，觉得是签到题就没有细心想怎么判环，不小心判成了以小编号为父亲的树。B题我感觉写的还算稳健。heltion的D题不太清楚怎么回事会WA这么多发，GTMD何训。I题虽然lgl给我的做法比正解麻烦，但我也比较快地写出来了。H题我和lgl思考以及码代码的时间都很短，过的比较快。前面五题虽然AD有5发罚时，但因为节奏比较快，过的比较快，5题罚时还算优秀。
J题的思路其实比较简单，就是难在转圈圈的细节上。因为前期节奏快，lgl过了H后，我没怎么考虑J题细节就上机开始写了，第一次的写法比较麻烦，写的不是很久，但是时间一直花费在debug上。之后heltion在旁边辅助我debug，也还是没有debug出来。以前也补过类似的题，但是对三点共线或者精度的要求没有这么高。这个J题我写到后来，感觉就是在瞎凑边界的条件，根本没有冷静思考什么情况会出错，怎么去特判掉。
因为J题卡着，而队友也没有想出其他题目，所以机位一直是我的，我就一直在对着数据debug，效率低下，情绪烦躁。赛后想想CFG题其实都是有可能出的题。F题bitset暴力分块，我在赛后也大致往这个方向想过，但听到JSB就是这么过的，还是怀疑了一下复杂度。这题感觉lgl是可能想得到的。heltion也是有可能开出C题或者G题，但明知道数学手册上很可能有却不翻。如果有人上机把我从机位赶下来，让我下机冷静思考一下，我反而更有机会调出来。
滚完榜惊奇的发现没有同题队过第六个题，也就是说滚完榜我们名次没有变，五题RK6。但是RK1,2,3,4分别是10,9,8,7题，被一顿爆踩，根本开心不起来。
大概总结了下面几点：
- 写题前还是要多思考，哪怕有机位也要考虑清楚
- 比赛卡题不要紧张，不然交流的时候没有效率，也没法冷静思考，就像吉林的G题，北京的J题
- 感觉对着数据debug效率很容易烦躁，下机看看自己的代码，想想哪儿会出错，可能更好
- lyk回去多写写几何题
- heltion回去把数学手册全部扫一遍看看有啥
- lgl回去多涨涨姿势，后期不要发呆，努力多做出一题
- 接下来就训一训第一委员会出的题
Jhguai
Heltion
题解 & 补题
- J ：赛后想清楚了细节，补题时1A了。思路比较简单，主要讲讲实现。极角排序同角度按幅长为第二关键字排序。转圈圈的时候先扩展两倍，用指针维护90/180度覆盖范围，除了90/180度限制外，还要判断：覆盖点数不能超过总点数；加入的下一点如果恰好同角度，则长度须大于当前轴。这样才能保证这个范围是正确的90/180度范围，不会出现绕了一圈回到自己这条轴的情况。
- F ：补题的时候把大致写法都想好了，写完过了编译就AC，很爽。做法：找出SCC后缩点。跑一遍DAG，用bitset统计每个点能到哪些点。统计时枚举异或值，从大到小，以32为一块，枚举这一块异或值（比如0-31）的总数，再与K判断，如果第K大在这块里面，就进去一个一个找。复杂度 MN/32+32QN
附加文件
- 1.jpg by lyk248289469