2021-team7-003
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2021-team7 返回]
[http://10.71.10.90/pia/trac/wiki/2020-team10-002 fr一年前的训练记录]
2020-09-25做过，然而早就忘了。。。。。。
== Rank和提交情况 ==
[[Image(Standing.jpg, 1000px)]]
Solved: 7/11
rank（校内）：8/11
== 流水账 ==
by fr
开场我签I(1,28/1)，chy去做C，写一半假了，我上去签F(2,50/1)，F过后chy也会C了(3,52/1)。
scl去签E，写完WA了，因为没有新题所以继续调。我去看G，会了后E还是没调出来，我先上去写G，因为访问c[-1][-1]贡献两发WA on 1，改完就过了(4,83/3)。
chy提醒精度误差，我上机验证了一下确实会出锅，于是让scl转整数做，过了(5,98/3)。
然后我让队友把读过的题都说一遍，跟榜发现AHJ过的人比较多，于是让chy去想A，我去想J。
chy会了A，上去写，T了，优化后就A了(6,165/2)。然后我让他想可能是DS题的J。
同时scl想出了H的假做法，被样例杀，然后我根据假做法推了真做法，简单跟scl讨论一下证明是对的，上机写，WA了。自己造数据hack掉，发现是单调栈写错了，改完过了(7,231/4)。
最后1h多chy冲J，但由于细节太多（而且做法有点不对）（而且板子没备好）没过。
upd：D已经补完。也许过掉H后应该再好好想一下D？
== 个人总结 ==
fr：这场全队规划不错，但自己因失误罚时太多。。。
chy：还是太菜了……J题自信地认为只要能写出数据结构就没问题，赛后发现要同时对所有元素取min的线段树合并似乎并不可行（况且我从来没有写过线段树合并）(DDP啊居然没有看出来)……A题贡献了一发罚时完全是因为头铁……写的时候已经发现还要一个前缀和优化了，然后觉得均摊很小，最坏也就根号，所以先勇了一发……果然T了。感觉还需要加强和队友在想法上的讨论，还有感觉这场比赛有点莫名带了奇怪的节奏。
scl：暴露了比较大的基础漏洞，读代码的能力也要加强，以及需要对队友的做法进行快速的理解和反馈，复杂度的分析还是需要再学。小小的教训：记得看完所有样例，提交之前最好手造几组小数据。
== 题解 ==
A: 先计算每个分数每个时刻的排名（相同的排名压成一个状态），对每个分数的排名贡献做前缀和，之后再对每个人二分求和。（chy）
B:
C: 签到（chy）
D: 求经过 i 条边到达每个点的最短路，然后对 (i,dis[i][n]) 做一个凸包，则凸包上的 i 就是可能成为最短路的路径边数。（fr赛后）
E：签到（scl）
F：签到（fr）
G：组合数学（fr）
H: 伪·单调栈 + 二分（fr）
I：签到（fr）
J: （chy待补）
K: [/wiki/2021-team7 返回]
2020-09-25做过，然而早就忘了。。。。。。
Rank和提交情况
Solved: 7/11
rank（校内）：8/11
流水账
by fr
开场我签I(1,28/1)，chy去做C，写一半假了，我上去签F(2,50/1)，F过后chy也会C了(3,52/1)。
scl去签E，写完WA了，因为没有新题所以继续调。我去看G，会了后E还是没调出来，我先上去写G，因为访问c[-1][-1]贡献两发WA on 1，改完就过了(4,83/3)。
chy提醒精度误差，我上机验证了一下确实会出锅，于是让scl转整数做，过了(5,98/3)。
然后我让队友把读过的题都说一遍，跟榜发现AHJ过的人比较多，于是让chy去想A，我去想J。
chy会了A，上去写，T了，优化后就A了(6,165/2)。然后我让他想可能是DS题的J。
同时scl想出了H的假做法，被样例杀，然后我根据假做法推了真做法，简单跟scl讨论一下证明是对的，上机写，WA了。自己造数据hack掉，发现是单调栈写错了，改完过了(7,231/4)。
最后1h多chy冲J，但由于细节太多（而且做法有点不对）（而且板子没备好）没过。
upd：D已经补完。也许过掉H后应该再好好想一下D？
个人总结
fr：这场全队规划不错，但自己因失误罚时太多。。。
chy：还是太菜了……J题自信地认为只要能写出数据结构就没问题，赛后发现要同时对所有元素取min的线段树合并似乎并不可行（况且我从来没有写过线段树合并）(DDP啊居然没有看出来)……A题贡献了一发罚时完全是因为头铁……写的时候已经发现还要一个前缀和优化了，然后觉得均摊很小，最坏也就根号，所以先勇了一发……果然T了。感觉还需要加强和队友在想法上的讨论，还有感觉这场比赛有点莫名带了奇怪的节奏。
scl：暴露了比较大的基础漏洞，读代码的能力也要加强，以及需要对队友的做法进行快速的理解和反馈，复杂度的分析还是需要再学。小小的教训：记得看完所有样例，提交之前最好手造几组小数据。
题解
A: 先计算每个分数每个时刻的排名（相同的排名压成一个状态），对每个分数的排名贡献做前缀和，之后再对每个人二分求和。（chy）
B:
C: 签到（chy）
D: 求经过 i 条边到达每个点的最短路，然后对 (i,dis[i][n]) 做一个凸包，则凸包上的 i 就是可能成为最短路的路径边数。（fr赛后）
E：签到（scl）
F：签到（fr）
G：组合数学（fr）
H: 伪·单调栈 + 二分（fr）
I：签到（fr）
J: （chy待补）
K:
附加文件
- Standing.jpg by fr200110217102