SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 13/? | 11 | 12 | 15 |
A¶
solved by YZW
题意¶
签到。
题解¶
略。
B¶
**upsolved by **
题意¶
题解¶
C¶
upsolved by TYB
题意¶
\(n\)个点，\(m\)条边的无向图，求有多少条包含\(k\)条边的路径，满足起点和终点相同，且不连续经过同一条边两次。
\(n\le100,m\le\frac{n(n-1)}{2},k\le10^4\)
题解¶
CF1662C European Trip - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
D¶
solved by JLK
题意¶
有两个串\(s,t\)，每次可以在任意位置插入/删除一个子串\(AA,BB,CC,ABAB,BCBC\)，问是否能把\(s\)转换成\(t\)。
\(1 \le |s|,|t| \le 200\)
题解¶
可以分析得到一些性质。
\(BA \Leftrightarrow (AA)BA(BB)=A(ABAB)B \Leftrightarrow AB\)
\(CB \Leftrightarrow BC\)同理。而\(AC\)不能互换。
也就是说，\(B\)可以随意移动，而且每两个可以删除，那么只需要两个串\(B\)个数奇偶性相同即可。
那么只剩\(AC\)，相邻的同样的字符仍然消掉，最后如果还相同就可以转化，否则不行。
可以用一个栈来维护一下。
\(O(|s|+|t|)\)
E¶
**upsolved by **
题意¶
题解¶
F¶
solved by TYB
题意¶
\(n\)个点，\(i,j\)间有一条权值为\(1\)的双向边当且仅当\(|i-j|\le\min(p_i,p_j)\)，求\(a\)到\(b\)的最短路。
\(n\le2\times10^5\)
题解¶
线段树优化BFS即可。
G¶
solved by TYB
题意¶
给一棵\(n\)个点的无向树，要求给边定向，使得不同的路径数最多。
\(n\le10^6\)
题解¶
结论：找重心，对于一部分子树，所有边连向重心，另一部分子树，重心向他们连边。
这样之后，子树内部的贡献是独立的。把子树分为两个集合\(S,T\)，子树间的贡献为\(((\sum_{x\in S}\rm{size}_x)+1)((\sum_{y\in T}\rm{size}_y)+1)\)。
求这个式子的最大值只能背包，直接做复杂度竟然是对的，似乎为\(\mathcal{O}(\frac{n\sqrt{n}}{w})\)。
以后可能会补一下复杂度的证明，但结论的证明不太想看。
H¶
solved by TYB
题意¶
签到。
题解¶
略。
I¶
solved by YZW
题意¶
签到。
题解¶
RE 了两次，呜呜呜。略。
J¶
**upsolved by **
题意¶
题解¶
K¶
solved by YZW
题意¶
几何题。
题解¶
三分套三分 + 费马点。
L¶
solved by JLK
题意¶
在数轴上，一开始在原点，每秒最多移动\(v\)单位。有\(n\)个条件，如果在\(t_i\)时刻到达了\(a_i\)，那么可以加一分，问最多有多少分。
\(1 \le n \le 2\times 10^5,1 \le v \le 10^6,1 \le t_i \lt 10^9,-10^9 \le a_i \le 10^9\)
题解¶
考虑最简单的dp，\(dp_i\)表示满足第\(i\)个条件的最多分数。转移的时候枚举\(t_j\)更大的\(j\)。
满足条件为\((t_j-t_i)\times v \ge |a_j-a_i|\)。
然后分类讨论，如果\(a_j \le a_i\)，就是\(a_i-t_i \times v\ge a_j - t_j \times v\)。
那么实际上就是一个二维偏序问题，每次往一个矩形转移。反过来同理。
用一个CDQ分治+BIT维护即可。
\(O(n\log ^2n)\)
M¶
solved by YZW
题意¶
签到。
题解¶
略。
N¶
solved by TYB
题意¶
给一个\(n\times n\)的矩阵，格子中的数为\(1\sim n^2\)的排列，求有多少个矩形，长宽都\(\ge2\)个格子，且四个角上的最小的两个数不在对角的位置（即在矩形的一条边上）。
\(n\le1500\)
题解¶
枚举一条边就要\(\mathcal{O}(n^3)\)，所以考虑间接计数。
比如可以统计下列四元组的数量：\((x,y,x_1,y_1)\)，满足\((x,y)\)中的数比\((x,y_1)\)和\((x_1,y)\)中的数大。可以发现，合法的矩形贡献一个这样的四元组，不合法的矩形贡献两个，然后就做完了。
O¶
solved by YZW
题意¶
签到。
题解¶
略。
记录¶
YZW过A(0:02)和M(0:11)，TYB过H(0:16)。
JLK写D，WA了一次，发现假了。
YZW写I，RE两次后AC(1:00)。
JLK和YZW讨论后过了D(1:11)。
TYB过F(1:23)。
YZW写O，WA一次后AC(1:37)。
JLK开始写L，写一半换TYB先写N，然后过了N(2:01)。
L WA两次后AC(2:26)。
YZW过K(3:03)。
最后看G，猜了个结论，TYB大力背包过了(3:58)。
然后就不会了。
总结¶
Dirt¶
D(-1)
I(-2)
L(-2)
O(-1)