2020-team2-017
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2020-team2 返回]
[[Image(Rank.png,1000px)]]
= 概述 =
solved: 6/12
rank: 14
= 流水账 =
开场十分顺利。yyc把A的式子写给pb，pb光速写完'''A1Y3'''（差点一血*1)。yyc翻了翻题面发现G最短，瞄了一眼发现是签到，告诉了在机上的pb，由于爆long long WA了一发，'''G2Y15'''（差点一血*2），此后pb将E丢给了cxt，cxt发现这个E直接平衡树枚举所有情况就好了，正好手里有一份之前准备好的pbds可以用，于是立马上场码码码，一交过了'''E1Y31'''(好像是一血？），F是个结论题，yyc找pb验了一下后上机'''F1Y41'''，这是看榜发现已经登顶了。K和之前训练赛的一个题很像，cxt上机，'''K1Y65'''。
pb在机下读到了C，发现是个计算几何，pb觉得比较好写，于是没有让本来约定好写几何的yyc上机，而是自己去写，由于写的是解析几何导致特殊情况很多，一直无法通过，最后cxt帮助修改了计算长度的部分后'''C6Y118'''。
这时榜上有B的提交和I的通过，cxt认为I更适合pb，于是等pb下机，B是个数据结构，yyc接着读别的题，D看着比较可做，H是个计数，J是个字符串，yyc觉得都不可做，又读到了L，于是把下一道题锁定为D和L，yyc发现了L的一些性质后和cxt说了L的做法，cxt优化了一下写法后上机，最后TLE了，仔细观察随机数生成器，发现数据并不是完全随机，答案不超过log的性质是错的。pb想了个I的做法提交后也WA了。pb和yyc尝试一起fixI的做法，但是从解方程和消出一组正交基的方向考虑都是错的。cxt推了推Ldp方程的优化，再次上机，写完后提交依然WA，手动和暴力对拍拍上了，于是开始怀疑人生。pb尝试修改I的做法也没能通过。最后决定放弃I。
pb和yyc想了想榜上较多人过的B，发现很轻松就得到了n^2^logn的做法，pb快速写完后发现莫名其妙的RE，最后发现是代码中一些for(j=1;j<=n;i++)之类的错误，提交后TLE了，cxt提出用并查集优化但是没有时间写了。
赛后：
cxt发现虽然L代码有一些小错误，但最大的错误还是yyc的从两边做的结论也是错的。
I的做法虽然是消出一组基，但并不是正交基。
pb补了B用时1.6h，他推断如果在赛时要用1h+3发左右罚时。
sub跑过来问我们为什么没做J，听过切割方案很少的结论后发现J并不是不可做题...
C的出题人声明C的std出锅了。
= 总结 =
=== pb： ===
这场自己的发挥并不好，dirt率高貌似成了我的"比赛风格"了，但是这肯定是不好的。这大概还是源于平时训练产生的不好的习惯吧，在整只队伍发挥正常的时候，dirt1~2次耽误的时间并不会影响队伍通过'''大部分'''队伍能开出来的题。
但是当题目有一定难度时，或者说难度有小段层时，中后期每通过一题队伍的rank提升都是巨大的，那么在前期题上面浪费的罚时就会产生很大的影响，要么耽误中后期题成功做出来，要么在大量同题数区域落于下风。
今天去写几何一是觉得自己想的比较清楚，二是觉得队伍里如果只有一个能写几何的人，还是不太行（原因之前提到过），虽然可能今天真的受到了std出错的影响，但是昨天的几何写的也不是很顺利，说明最近一直没有进行的个人训练还是产生了挺大的影响吧，要把个人训练捡起来。
=== Creatix： ===
这场其实有很多问题。
最令我百思不得其解的是，为什么我'''没有过L'''？
具体来说，我写出了一个我认为95%是正确的做法，但是一提交，wa。
我认为这就是所谓的'''意外'''。
'''意外不可怕，可怕的是 a）意外经常发生。b）意外产生的影响太大。'''
从 a）的角度来讲，我想'''给队友提提意见'''。（'''如果我说的没有道理，请喷回来'''）
pb 您能不能少出点锅？昨天的 F 也是，今天的 C 也是，为什么意外那么多啊？
yyc 您能不能写计算几何稳一点，来几次畅快的 1A 啊？考虑到您昨天的H，我们今天没敢直接把C丢给您也有这方面的原因吧。
从 b）的角度来说，我想喷一下自己。你今天L的这个意外导致的影响太大了。
你这个L的卡题，很可能直接就导致了全队少 3 道题。
如果全力想 I，再努力一下J，说不定就多3题了呢？
anyway，我们只训练了15场而已哦
anyway, 我们金了不是吗，连续两天一块省赛金，一块国赛金
好好训练吧
upd:草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草
=== yyc： ===
~~AK了一场CF，yeah~~
首先是C的问题，当时我并不知道pb要上去写什么，本来应该由我来写的（虽然不知道我写会发生什么情况，且C本来就是一个有问题的题）
对于我计算几何1A率低的问题，其实也只能多练解决。毕竟队内没有什么擅长写几何题的人。另外几何题也不是那么容易1A。（但是上一场的H耽误了很长时间确实要背锅，别的队从第一次提交到AC一般只用了0.5h，我没考虑corner case确实不应该）
然后是比赛策略的问题。是不是应该把在L上的cxt拉过来看一看I，毕竟榜上L是一个很多人尝试但无一通过的题，而I pb和yyc已经fix不出正确做法但是榜上有较多的队通过，按照道理来说一个队一起想都不会是不太可能的。4h之后想出了B，接下来的策略可能如下：1.cxt机下调L，pb写B争取2题；2.一直让cxt调L，保住1题；3.pb写B，cxt想I，争取2题。在赛时甚至未曾设想第三种策略，选择了比较激进的1。“两个人不会的题要让第三个人想一想”，这个在去年trac上的tips，怎么现在就忘了呢。
还有做题顺序的问题。由于做出F甚至C的时候，我们都处于一个带榜的位置，榜上的I被认定为是pb擅长的题，剩下没有别的题了，所以我们去想L和D是没有任何问题的，但是在L卡了一段时间榜上有了B和H后，是不是应该考虑暂时放弃。
J的问题我认为是合理且很难避免的。1.J是队内不擅长的字符串题；2.榜上很晚才有人通过。所以我们并没有道理放弃有做法的L，B和通过人数较多的I。
另外是我个人的问题。L两边分别做假了的原因是因为最开始我的写法是维护答案相同的区间，这种做法这样是对的，但是由于不是随机数据导致了复杂度不对，而优化后的做法这样就不对了，在以前写题或者与队友交流做法的时候，我也出现过类似的问题。在与队友交流时，应该注意一下做法的兼容性。
= 题解 =
* A：签到
* B：枚举边界并查集维护
* C：假题，和出题人心意相通就过了
* D：
* E：pbds
* F：树的连通块全不选，别的都选
* G：特判+数论分块
* H：
* I：{u,v}向量的合法变换一定是{u+kv,v}，那么只考虑一维是辗转相除，都是合法变换，两维就是维护(x1,y1),(0,y2)，注意爆longlong
* J：枚举宽度，不要的部分只有o（n）种可能，先把字符串哈希后再把每种方案哈希。复杂度调和级数
* K：树dp，f[i][0/1]表示完成i的子树，完成后是否将军队移动回i点。细节注意一下就好了。
* L：这是一道需要一点时间的题，四个单调队列即可。[/wiki/2020-team2 返回]
概述
solved: 6/12
rank: 14
流水账
开场十分顺利。yyc把A的式子写给pb，pb光速写完A1Y3（差点一血*1)。yyc翻了翻题面发现G最短，瞄了一眼发现是签到，告诉了在机上的pb，由于爆long long WA了一发，G2Y15（差点一血*2），此后pb将E丢给了cxt，cxt发现这个E直接平衡树枚举所有情况就好了，正好手里有一份之前准备好的pbds可以用，于是立马上场码码码，一交过了E1Y31(好像是一血？），F是个结论题，yyc找pb验了一下后上机F1Y41，这是看榜发现已经登顶了。K和之前训练赛的一个题很像，cxt上机，K1Y65。
pb在机下读到了C，发现是个计算几何，pb觉得比较好写，于是没有让本来约定好写几何的yyc上机，而是自己去写，由于写的是解析几何导致特殊情况很多，一直无法通过，最后cxt帮助修改了计算长度的部分后C6Y118。
这时榜上有B的提交和I的通过，cxt认为I更适合pb，于是等pb下机，B是个数据结构，yyc接着读别的题，D看着比较可做，H是个计数，J是个字符串，yyc觉得都不可做，又读到了L，于是把下一道题锁定为D和L，yyc发现了L的一些性质后和cxt说了L的做法，cxt优化了一下写法后上机，最后TLE了，仔细观察随机数生成器，发现数据并不是完全随机，答案不超过log的性质是错的。pb想了个I的做法提交后也WA了。pb和yyc尝试一起fixI的做法，但是从解方程和消出一组正交基的方向考虑都是错的。cxt推了推Ldp方程的优化，再次上机，写完后提交依然WA，手动和暴力对拍拍上了，于是开始怀疑人生。pb尝试修改I的做法也没能通过。最后决定放弃I。
pb和yyc想了想榜上较多人过的B，发现很轻松就得到了n2logn的做法，pb快速写完后发现莫名其妙的RE，最后发现是代码中一些for(j=1;j<=n;i++)之类的错误，提交后TLE了，cxt提出用并查集优化但是没有时间写了。
赛后：
cxt发现虽然L代码有一些小错误，但最大的错误还是yyc的从两边做的结论也是错的。
I的做法虽然是消出一组基，但并不是正交基。
pb补了B用时1.6h，他推断如果在赛时要用1h+3发左右罚时。
sub跑过来问我们为什么没做J，听过切割方案很少的结论后发现J并不是不可做题...
C的出题人声明C的std出锅了。
总结
pb：
这场自己的发挥并不好，dirt率高貌似成了我的"比赛风格"了，但是这肯定是不好的。这大概还是源于平时训练产生的不好的习惯吧，在整只队伍发挥正常的时候，dirt1~2次耽误的时间并不会影响队伍通过大部分队伍能开出来的题。
但是当题目有一定难度时，或者说难度有小段层时，中后期每通过一题队伍的rank提升都是巨大的，那么在前期题上面浪费的罚时就会产生很大的影响，要么耽误中后期题成功做出来，要么在大量同题数区域落于下风。
今天去写几何一是觉得自己想的比较清楚，二是觉得队伍里如果只有一个能写几何的人，还是不太行（原因之前提到过），虽然可能今天真的受到了std出错的影响，但是昨天的几何写的也不是很顺利，说明最近一直没有进行的个人训练还是产生了挺大的影响吧，要把个人训练捡起来。
Creatix：
这场其实有很多问题。
最令我百思不得其解的是，为什么我没有过L？
具体来说，我写出了一个我认为95%是正确的做法，但是一提交，wa。
我认为这就是所谓的意外。
意外不可怕，可怕的是 a）意外经常发生。b）意外产生的影响太大。
从 a）的角度来讲，我想给队友提提意见。（如果我说的没有道理，请喷回来）
pb 您能不能少出点锅？昨天的 F 也是，今天的 C 也是，为什么意外那么多啊？
yyc 您能不能写计算几何稳一点，来几次畅快的 1A 啊？考虑到您昨天的H，我们今天没敢直接把C丢给您也有这方面的原因吧。
从 b）的角度来说，我想喷一下自己。你今天L的这个意外导致的影响太大了。
你这个L的卡题，很可能直接就导致了全队少 3 道题。
如果全力想 I，再努力一下J，说不定就多3题了呢？
anyway，我们只训练了15场而已哦
anyway, 我们金了不是吗，连续两天一块省赛金，一块国赛金
好好训练吧
upd:草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草草
yyc：
AK了一场CF，yeah
首先是C的问题，当时我并不知道pb要上去写什么，本来应该由我来写的（虽然不知道我写会发生什么情况，且C本来就是一个有问题的题）
对于我计算几何1A率低的问题，其实也只能多练解决。毕竟队内没有什么擅长写几何题的人。另外几何题也不是那么容易1A。（但是上一场的H耽误了很长时间确实要背锅，别的队从第一次提交到AC一般只用了0.5h，我没考虑corner case确实不应该）
然后是比赛策略的问题。是不是应该把在L上的cxt拉过来看一看I，毕竟榜上L是一个很多人尝试但无一通过的题，而I pb和yyc已经fix不出正确做法但是榜上有较多的队通过，按照道理来说一个队一起想都不会是不太可能的。4h之后想出了B，接下来的策略可能如下：1.cxt机下调L，pb写B争取2题；2.一直让cxt调L，保住1题；3.pb写B，cxt想I，争取2题。在赛时甚至未曾设想第三种策略，选择了比较激进的1。“两个人不会的题要让第三个人想一想”，这个在去年trac上的tips，怎么现在就忘了呢。
还有做题顺序的问题。由于做出F甚至C的时候，我们都处于一个带榜的位置，榜上的I被认定为是pb擅长的题，剩下没有别的题了，所以我们去想L和D是没有任何问题的，但是在L卡了一段时间榜上有了B和H后，是不是应该考虑暂时放弃。
J的问题我认为是合理且很难避免的。1.J是队内不擅长的字符串题；2.榜上很晚才有人通过。所以我们并没有道理放弃有做法的L，B和通过人数较多的I。
另外是我个人的问题。L两边分别做假了的原因是因为最开始我的写法是维护答案相同的区间，这种做法这样是对的，但是由于不是随机数据导致了复杂度不对，而优化后的做法这样就不对了，在以前写题或者与队友交流做法的时候，我也出现过类似的问题。在与队友交流时，应该注意一下做法的兼容性。
题解
- A：签到
- B：枚举边界并查集维护
- C：假题，和出题人心意相通就过了
- D：
- E：pbds
- F：树的连通块全不选，别的都选
- G：特判+数论分块
- H：
- I：{u,v}向量的合法变换一定是{u+kv,v}，那么只考虑一维是辗转相除，都是合法变换，两维就是维护(x1,y1),(0,y2)，注意爆longlong
- J：枚举宽度，不要的部分只有o（n）种可能，先把字符串哈希后再把每种方案哈希。复杂度调和级数
- K：树dp，f[i][0/1]表示完成i的子树，完成后是否将军队移动回i点。细节注意一下就好了。
- L：这是一道需要一点时间的题，四个单调队列即可。