| Rank | Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 5/113 | 7/11 | O | O | O | O | O | Ø | O | O | Ø | . | . |
O: 当场通过
Ø: 赛后通过
.: 尚未通过
A Birthday
solved by chelly
chelly's solution
费用流即可
B Board
solved by chelly
chelly's solution
行列分别扫一遍即可
C Circle
solved by chelly
chelly's solution
答案就是n
D Growth
solved by ch&chelly
chelly's solution
考虑把坐标离散成网格图，那么就是在1000*1000的网格上进行dp，dp(i,j)由dp(i-1,j)和dp(i,j-1)转移而来
E Kingdom
solved by ch
ch's solution
F Matrix
upsolved by Feynman1999
Feynman1999's solution
G Mountain
solved by ch
ch's solution
H 清明梦超能力者黄YY
solved by chelly
chelly's solution
考虑将染色倒序，那么就是要输出每个点被恰好染k次时候的颜色
树链剖分，对于修改操作就是对一段区间里的所有元素进行颜色覆盖、次数都加1
颜色覆盖用一个标记就可以了，关键考虑“次数加1”
我们维护一个b和maxb表示该区间被整体加了b次，其中被加的最大值是maxb
对于一次修改，如果我们发现了某个区间的maxb=k-1，那么继续递归下去，直到叶子节点进行单点修改
单点修改的时候一方面可以得到答案了，另一方面为了防止该点以后又被加到k，所以可以把这个点的b赋值为-inf
因为对于一个元素单点修改最多进行1次，修改一次是O(logn)的，所以整个线段树复杂度就是O(logn)
再套上个树链剖分，总时间复杂度是(O(nlog^2n))
I 最短路
upsolved by chelly
chelly's solution
J 排序
unsolved
K 土龙弟弟
unsolved
Replay
本场由chelly、ch、Feynman1999线下打的。
开场chelly签了两个题，然后ch的签到题卡了有点久，不过最终还是过了。chelly发现A大概是个费用流，就写了一发，修修补补了一下题意，过了A。之后ch一直在乱搞E，最终把E卡过去了。chelly想了想H，发现H很简单，于是上机贴了个板子码码码就过了。后来Feynman1999提出了F的做法，并且上机进行coding，但因为细节没有想清楚，debug了很长时间。在Feynman1999coding的时候，ch和chelly交流了D题的解法，chelly觉得很好写，向Feynman1999要机时。在结束前90分钟的时候chelly开始敲D，Feynman1999继续回自己那里看代码考虑细节。然后chelly很快切了D。之后chelly和Feynman1999一起debug D题的代码，但无奈比赛中没有调过去。比赛结束后，Feynman1999发现自己少维护了一行，fix了一下就过了。