2019-team11/summary-190814

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
~~两个学数学的excrt搞到这么晚才开出来，怎么说呢……~~
大家开门发现E能做但是略烦，B一万支队全过了，H也可以做。xtx写了一会B，但是细节有些没想清楚就下来了。ln上H。35min。
xtx把B换了个思路然后WA了，看了半天发现是个很trivial的错误。67min+1。
xtx开码E，调了一定时间调出来了。95min。
接下来看全世界人民都过了的D、F、J，然后就死掉了……一个半小时签完水水水水水水题，然后水题就签不动了……封完榜才过了个D，太惨了。279min+2。
xtx一直在攻F，思索了好久思索出了一个复杂度科学但是常数不定的nlogn算法，一交就T，直至结束，原因仍不明。赛后发现没有注意到某个条件的妙用，注意到就能直接上线段树然后常数就科学了……
ln和kc想G，想的是枚举两边中点然后再搞个极角排序然后再扫一扫判一判，隐隐约约觉得这样是正确的，但感觉写起来麻烦得不得了就不想动。赛后讨论发现有结论可以用，这样写起来就快很多了。
ln看到韩信点兵悲哀地发现自己连crt都忘光了，找kc回忆了一下crt后感觉好累于是陷入自闭，但看到全国人民都过了D想想还是硬攻一下好了。ln把复杂度和题目估了一下后想到自己写过excrt的板子，翻出来发现可以用，但因为数据范围要用python重写。然后！因为exgcd里面ln傻逼地把一个x抄成了y导致样例都过不去，于是ln和kc发现等价的算法在C里正确而在python里错误。研究了好久的python特性，全局变量特性运算符顺序等搞了半天才print局部变量发现exgcd抄错了……贡献了约60min的时间浪费+2发罚时，喜失*2。太惨烈了。
xtx和kc推J推了一定时间后发现这东西要优化但是我们没人会优化……弃之，在F中越陷越深。
== 个人总结 ==
ln：要对自己有信心，相信能找得到原题。相信自己以前做过的题能有帮助。还要要记得归纳总结，数论的一些内容该捡也该捡了。
ln：下次抄东西一定要看有没有地方抄错了！！！有没有什么本该对称的地方不对称了，提升校验能力，不要总想其他稀奇古怪的方向……
xtx：打代码要快准狠。每次写签到题都慢的要死，码力不够。
== 补题 ==
A：不会的逆向背包dp（模型都没建出来，哭了）
B：递归做
C：
D：韩信点兵
E：
F：线段树维护每个方向的最大值，枚举另一个方向的情况，直接暴力删点->求max->加回来就能过。其实写个可更新点的大根堆一样做，但代码一样长，复杂度也一样。
G：
H：把deg排个序，剩下两种看deg=3的点的邻点。
I：
J：？？？二分/分治优化？/斜率优化？

流水账

两个学数学的excrt搞到这么晚才开出来，怎么说呢……

大家开门发现E能做但是略烦，B一万支队全过了，H也可以做。xtx写了一会B，但是细节有些没想清楚就下来了。ln上H。35min。

xtx把B换了个思路然后WA了，看了半天发现是个很trivial的错误。67min+1。

xtx开码E，调了一定时间调出来了。95min。

接下来看全世界人民都过了的D、F、J，然后就死掉了……一个半小时签完水水水水水水题，然后水题就签不动了……封完榜才过了个D，太惨了。279min+2。

xtx一直在攻F，思索了好久思索出了一个复杂度科学但是常数不定的nlogn算法，一交就T，直至结束，原因仍不明。赛后发现没有注意到某个条件的妙用，注意到就能直接上线段树然后常数就科学了……

ln和kc想G，想的是枚举两边中点然后再搞个极角排序然后再扫一扫判一判，隐隐约约觉得这样是正确的，但感觉写起来麻烦得不得了就不想动。赛后讨论发现有结论可以用，这样写起来就快很多了。

ln看到韩信点兵悲哀地发现自己连crt都忘光了，找kc回忆了一下crt后感觉好累于是陷入自闭，但看到全国人民都过了D想想还是硬攻一下好了。ln把复杂度和题目估了一下后想到自己写过excrt的板子，翻出来发现可以用，但因为数据范围要用python重写。然后！因为exgcd里面ln傻逼地把一个x抄成了y导致样例都过不去，于是ln和kc发现等价的算法在C里正确而在python里错误。研究了好久的python特性，全局变量特性运算符顺序等搞了半天才print局部变量发现exgcd抄错了……贡献了约60min的时间浪费+2发罚时，喜失*2。太惨烈了。

xtx和kc推J推了一定时间后发现这东西要优化但是我们没人会优化……弃之，在F中越陷越深。

个人总结

ln：要对自己有信心，相信能找得到原题。相信自己以前做过的题能有帮助。还要要记得归纳总结，数论的一些内容该捡也该捡了。

ln：下次抄东西一定要看有没有地方抄错了！！！有没有什么本该对称的地方不对称了，提升校验能力，不要总想其他稀奇古怪的方向……

xtx：打代码要快准狠。每次写签到题都慢的要死，码力不够。

补题

A：不会的逆向背包dp（模型都没建出来，哭了）

B：递归做

C：

D：韩信点兵

E：

F：线段树维护每个方向的最大值，枚举另一个方向的情况，直接暴力删点->求max->加回来就能过。其实写个可更新点的大根堆一样做，但代码一样长，复杂度也一样。

G：

H：把deg排个序，剩下两种看deg=3的点的邻点。

I：

J：？？？二分/分治优化？/斜率优化？