2020-2021 ICPC Southwestern European Regional Contest (SWERC 2020)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 83/? | 9 | 9 | 13 |
A¶
solved by JLK
题意¶
签到，略
题解¶
B¶
**upsolved by **
题意¶
题解¶
C¶
solved by JLK
题意¶
签到，略
题解¶
D¶
upsolved by YZW
题意¶
题解¶
E¶
solved by TYB
题意¶
签到，略。
题解¶
略。
F¶
solved by JLK
题意¶
\(N\)个点的二叉树，要求父亲点的编号一定大于儿子点的编号，且\(R\)点一定是叶子结点，求方案数。
\(1 \le R\le N \le 2021\)
题解¶
注意到编号的一个后缀的点集一定构成一个连通块，考虑这样不断加点。
\(dp_{i,j}\)表示\([i,N]\)的点构成的树，有\(j\)个点已经放满了两个儿子。
很容易通过点和边的关系算出0个儿子和1个儿子的点数。插入\(i-1\)点，要么在0个儿子的点下面，要么在1个儿子的点下面。
只要转移的时候钦点\(R\)这个点始终为0个儿子即可。也就是不会往\(R\)下面插入点。
\(O(N^2)\)
G¶
solved by TYB
题意¶
直接简化：给出一个\(n\)个点的内向基环森林，找出一条长度恰为\(k\)的路径，使其点权和最小。
\(n\le10^6\)
题解¶
显然可以无脑倍增，但是被卡空间了。现在的两个大数组，\(fa_{i,j}\)表示\(i\)的第\(2^j\)级祖先，\(v_{i,j}\)表示路径上的和。第一个不太好去掉，第二个long long数组是可以去掉的，按照路径完全在树上、完全在环上、既在树上也在环上三种情况处理，预处理环上一些信息即可。
H¶
solved by JLK
题意¶
主席树裸题，略
题解¶
I¶
solved by YZW
题意¶
题解¶
J¶
**upsolved by **
题意¶
题解¶
K¶
solved by YZW
题意¶
题解¶
L¶
**upsolved by **
题意¶
题解¶
M¶
**upsolved by **
题意¶
题解¶
记录¶
TYB过E(0:02)，JLK过A(0:15)，YZW过K(0:27)，JLK过C(0:38)。
JLK写F，TYB和YZW讨论G。
JLK过F(0:57)，TYB开始写。
YZW和JLK讨论D，TYB卡住了，YZW先写。
YZW过D(1:31)，TYB G MLE一次。
YZW过I(1:47)，TYB G WA一次后AC(2:39)。
JLK写H，WA两次后AC(3:58)。
最后看L，YZW提出一个做法，JLK开始冲，但是一直WA。赛后发现假了。
总结¶
Dirt¶
G(-2)
H(-2)