2019-team11/summary-190815

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
开门ln看D短短的很可爱大家过得也很快就觉得这个题是能签的，然后……卡了整场比赛，一直想一直想头都想秃了还是一点想法也莫得。这个D真他娘的可爱。赛后发现这又是原题……怎么大家都做过原题orz（不知道有谁能现场推出类欧几里得算法的……这nm是欧几里得再世吧
xtx后半场都在搞A推了老半天的式子思来想去最后上个厕所发现倒着做复杂度就正确了……然而这时候比赛只剩2min了。凉凉。
看到F感觉好复杂不好dp就没怎么想结果发现读题也读错了这可以积分做而且被积函数都是多项式函数……如果这么想的话后半场可能就不会盯着D发呆了？还是做的题太少了，尤其这种考点不常见的题目。（暗指某CE题
J是个dp，G是个线段树，xtx签的。这些比赛都这么狠的么……拿dp拿线段树签到，涩会涩会。48min。2h19min+1。
之后发现M全世界都做了，就想了一想。ln模拟了一下样例后想按位处理然后推了一些结论然后就上去了，复杂度都没怎么估。因为没有考虑m=0的情形喜+2。（一般不都是+1的么！喜+2太惨了8 3h43min+2
然后就是日常卡题orz螺旋卡题=》花式爆炸.jpg
ln最后10min看了一下I口胡了一个塑料算法但是细节碰到了点问题就扔掉了。早看这题的话后期可能也不会无聊的说。
== 个人总结 ==
ln：以后不能看到某些题目就蜜汁执着，比如A比如D。休息一下上上厕所吹吹风，回来先看看其他题，保持清醒。
ln：学类欧几里得算法。
xtx：每天要好好睡觉。CF 还是要多打，从 218 回来人就一直发呆。
== 补题 ==
A：每段连续 j 个点不被选中且其两边点被选中，这些点构成的面积对答案的贡献是 S*C(n-j-2, k-2)/C(n, k)
B：瞎判。
C：
D：类欧几里得模板题。
E：
F：从叶子网上 dp 多项式求定积分。
G：求有无矩形相交。先离散化。考虑每个矩形横着的边对后面矩形的影响，按 x 坐标排序加矩形，建线段树记录每个 y 上的横边能到的最远距离求区间最大值，每次查询 (y1,y2) 是否大于等于 x1 ，没有将矩形加入。然后 x y 对换再做一遍。
H：
I：
J：f[i][j] 表示母串前 i 位匹配了子串前 j 个的时候子串最晚开始位置，最终答案为 sum{i*f[i][m]}
K：
L：
M：智商题。通过第一条和中间那条信息来考虑首位，然后看看合不合法，再递归进去。注意给出的信息中只出现了n以下个数字也要特判不合法。还有m=0要特判。

流水账

开门ln看D短短的很可爱大家过得也很快就觉得这个题是能签的，然后……卡了整场比赛，一直想一直想头都想秃了还是一点想法也莫得。这个D真他娘的可爱。赛后发现这又是原题……怎么大家都做过原题orz（不知道有谁能现场推出类欧几里得算法的……这nm是欧几里得再世吧

xtx后半场都在搞A推了老半天的式子思来想去最后上个厕所发现倒着做复杂度就正确了……然而这时候比赛只剩2min了。凉凉。

看到F感觉好复杂不好dp就没怎么想结果发现读题也读错了这可以积分做而且被积函数都是多项式函数……如果这么想的话后半场可能就不会盯着D发呆了？还是做的题太少了，尤其这种考点不常见的题目。（暗指某CE题

J是个dp，G是个线段树，xtx签的。这些比赛都这么狠的么……拿dp拿线段树签到，涩会涩会。48min。2h19min+1。

之后发现M全世界都做了，就想了一想。ln模拟了一下样例后想按位处理然后推了一些结论然后就上去了，复杂度都没怎么估。因为没有考虑m=0的情形喜+2。（一般不都是+1的么！喜+2太惨了8 3h43min+2

然后就是日常卡题orz螺旋卡题=》花式爆炸.jpg

ln最后10min看了一下I口胡了一个塑料算法但是细节碰到了点问题就扔掉了。早看这题的话后期可能也不会无聊的说。

个人总结

ln：以后不能看到某些题目就蜜汁执着，比如A比如D。休息一下上上厕所吹吹风，回来先看看其他题，保持清醒。

ln：学类欧几里得算法。

xtx：每天要好好睡觉。CF 还是要多打，从 218 回来人就一直发呆。

补题

A：每段连续 j 个点不被选中且其两边点被选中，这些点构成的面积对答案的贡献是 S*C(n-j-2, k-2)/C(n, k)

B：瞎判。

C：

D：类欧几里得模板题。

E：

F：从叶子网上 dp 多项式求定积分。

G：求有无矩形相交。先离散化。考虑每个矩形横着的边对后面矩形的影响，按 x 坐标排序加矩形，建线段树记录每个 y 上的横边能到的最远距离求区间最大值，每次查询 (y1,y2) 是否大于等于 x1 ，没有将矩形加入。然后 x y 对换再做一遍。

H：

I：

J：f[i][j] 表示母串前 i 位匹配了子串前 j 个的时候子串最晚开始位置，最终答案为 sum{i*f[i][m]}

K：

L：

M：智商题。通过第一条和中间那条信息来考虑首位，然后看看合不合法，再递归进去。注意给出的信息中只出现了n以下个数字也要特判不合法。还有m=0要特判。