2020-team2-003

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team2 返回]

= 概述 =

 solved: 6/13

 rank: 21



= 流水账 =
今天队长考六级去了，于是pb和Creatix'''双打'''。

开局分别读题，pb看到D之后觉得直接做就行了，于是上机拿了'''一血'''，D1(15)，同时发现E过得很多，Creatix很快会了做法，上机写完之后有一些bug，

找出了边表没有清空和把双向边看成单向边的问题，同时发现题目'''并未定义'''n=1时如何输出，于是猜了一下题意。改了几发之后过了，E4(57)。

pb在帮Creatix看E的同时大概开出了K是个反演，两个人大概讨论了一下找了找规律，确定了做法，上机边想边做比较慢，但是'''1A'''了，K1(124)。

然后发现B过得很多，pb原来做过类似的题，猜了个结论证了一下，Creatix想好了怎么实现，于是上机写得很快，但是交了RE了，发现了一个小bug，fix之后过掉了，B2(163)。

pb在Creatix写B的时候开出了M，是个计算几何，之前写过类似的于是上去抄板子，写得很烦，然后WA掉了。于是pb怀疑自己凸包又写错了，print之后开始看。

Creatix开出了L，上机开始写FFT，pb看了一会上机测了几个样例，改了一下又WA了一发，又过了一会发现前后写的不一致，果然凸包又错了。改了之后M3(216)

Creatix上机写完了L，调了一会过了样例两个人很'''激动'''，'''没删调试'''就交了，数组还开小了于是WA了两发，L3(238)

pb在这个过程中觉得自己做出了I，于是上机写，最后改了很多bug还是没有过，离比赛结束还有8分钟的时候被Creatix叉掉了，算法假了，遂弃疗


= 总结 =

=== pb： ===

今天还是有一些Dirt的，跟去年一样，写凸包，然后抄线段相交板子，然后WA。感觉写几何题的时候并不是很自信，觉得细节很多，没有1A的感觉，还是要多练习。
然后要注意考虑更一般性的情况，后期提出的算法其实是漏洞很大的，非常容易从cha掉，但是并没有cha掉，感觉自己还是过于“果断”导致有些盲目，以后要更冷静

=== Creatix： ===
 * 今天3题分别有（2，1，2）发罚时，都是一些低级错误。
 主要是感觉在组队赛的时候'''心态不正确'''，很多时候一方面想着可以靠队友提醒，一方面想着可以依靠提交反馈结果，一方面没能静下心来，以至于常常忘记关注基础问题。
 记得在个人赛的时候大多数题目都是1发ac的，可见组队赛时的问题单纯只是心态问题。
 以后应该在训练中注意'''不要太激动'''，提交前仔细检查。

 * 第二个问题是最近三场比赛中都存在的，即难以'''在嘈杂的环境中深入思考'''。
 以后可以适当锻炼这方面的能力。

 * 第三个问题是开场'''读错了3道题'''。
 包括把单向边看成双向边，把子序列看成字串，等等。
 问题3发生原因其实和问题1/2类似。

 * 关于与队友的合作方面，此次'''成功依靠合作'''更快的解决了B题，即我想好了各个部分的细节，pb给出关键的思路方向，再由我上机，感觉这是一次成功的合作。以后可以多多对一些榜上过的多但是个人一时没思路的题目进行这样的讨论。

= 题解 =

 * A：
 * B：题意：要求支持在末尾加入一个元素 & 求出区间的线性基，强制在线。

 对每个i维护出，当把元素按i到1的顺序加入线性基时，线性基发生变化的位置，保存在g[i]这个vector中，显然g[i]的大小是log级别的。

 如果询问x，y，则只需调取g[y]即可。

 * C：

 * D：签到

 * E：水题，最短路+网络流。

 * F：

 * G：

 * H：

 * I：在子序列自动机上贪心，只要保证个数满足要求即可

 * J：

 * K：

 * L：操作顺序无关。

 * M：直线Ax+By+C=0把平面两侧分成的区域满足Ax+By+C>0,Ax+By+C<0。通过乘一个-可以交换两边的符号。

[/wiki/2020-team2 返回]

概述

solved: 6/13

rank: 21

流水账

今天队长考六级去了，于是pb和Creatix双打。

开局分别读题，pb看到D之后觉得直接做就行了，于是上机拿了一血，D1(15)，同时发现E过得很多，Creatix很快会了做法，上机写完之后有一些bug，

找出了边表没有清空和把双向边看成单向边的问题，同时发现题目并未定义n=1时如何输出，于是猜了一下题意。改了几发之后过了，E4(57)。

pb在帮Creatix看E的同时大概开出了K是个反演，两个人大概讨论了一下找了找规律，确定了做法，上机边想边做比较慢，但是1A了，K1(124)。

然后发现B过得很多，pb原来做过类似的题，猜了个结论证了一下，Creatix想好了怎么实现，于是上机写得很快，但是交了RE了，发现了一个小bug，fix之后过掉了，B2(163)。

pb在Creatix写B的时候开出了M，是个计算几何，之前写过类似的于是上去抄板子，写得很烦，然后WA掉了。于是pb怀疑自己凸包又写错了，print之后开始看。

Creatix开出了L，上机开始写FFT，pb看了一会上机测了几个样例，改了一下又WA了一发，又过了一会发现前后写的不一致，果然凸包又错了。改了之后M3(216)

Creatix上机写完了L，调了一会过了样例两个人很激动，没删调试就交了，数组还开小了于是WA了两发，L3(238)

pb在这个过程中觉得自己做出了I，于是上机写，最后改了很多bug还是没有过，离比赛结束还有8分钟的时候被Creatix叉掉了，算法假了，遂弃疗

总结

pb：

今天还是有一些Dirt的，跟去年一样，写凸包，然后抄线段相交板子，然后WA。感觉写几何题的时候并不是很自信，觉得细节很多，没有1A的感觉，还是要多练习。

然后要注意考虑更一般性的情况，后期提出的算法其实是漏洞很大的，非常容易从cha掉，但是并没有cha掉，感觉自己还是过于“果断”导致有些盲目，以后要更冷静

Creatix：

今天3题分别有（2，1，2）发罚时，都是一些低级错误。

主要是感觉在组队赛的时候心态不正确，很多时候一方面想着可以靠队友提醒，一方面想着可以依靠提交反馈结果，一方面没能静下心来，以至于常常忘记关注基础问题。

记得在个人赛的时候大多数题目都是1发ac的，可见组队赛时的问题单纯只是心态问题。

以后应该在训练中注意不要太激动，提交前仔细检查。

第二个问题是最近三场比赛中都存在的，即难以在嘈杂的环境中深入思考。

以后可以适当锻炼这方面的能力。

第三个问题是开场读错了3道题。

包括把单向边看成双向边，把子序列看成字串，等等。

问题3发生原因其实和问题1/2类似。

关于与队友的合作方面，此次成功依靠合作更快的解决了B题，即我想好了各个部分的细节，pb给出关键的思路方向，再由我上机，感觉这是一次成功的合作。以后可以多多对一些榜上过的多但是个人一时没思路的题目进行这样的讨论。

题解

A：
B：题意：要求支持在末尾加入一个元素 & 求出区间的线性基，强制在线。

对每个i维护出，当把元素按i到1的顺序加入线性基时，线性基发生变化的位置，保存在g[i]这个vector中，显然g[i]的大小是log级别的。

如果询问x，y，则只需调取g[y]即可。

C：
D：签到
E：水题，最短路+网络流。
F：
G：
H：
I：在子序列自动机上贪心，只要保证个数满足要求即可
J：
K：
L：操作顺序无关。
M：直线Ax+By+C=0把平面两侧分成的区域满足Ax+By+C>0,Ax+By+C<0。通过乘一个-可以交换两边的符号。