GYM103388 2021-2022 ACM-ICPC Brazil Subregional Programming Contest 部分题解

· · 个人记录

切了 K 后登顶了。
然后好像一直没下来过。
最后被剩下 11 题神仙踹到了 rank4。
写一下部分题解
由此可见我负责的题全都是萌萌题，进而认识到 xtw 菜的事实。

I（赛后补）

题意：
给定一张完全图，初始有若干边是黑的。
选择一个点集，把它涂黑，剩下的点留白。
对于一条边，如果它两端颜色不同，就将其颜色翻转。
求剩下黑边构成一个生成树的方案数 \bmod 10^9+7。
题解：
诈骗题，\bmod 10^9+7 的题直接 +1 就过了。
方案数不可能很多，感性理解一下，钦定前三个。
然后剩下点颜色就确定了，因为边数 \le n-1。
然后直接瞎暴力，大力 dfs，+1,+1 的就做完了。
代码：
Link

J（我负责代码）

题意：
有网格，每行选一个数，设第 i 行选的数是 p_i。
有若干个额外代价，表示答案减去 C|p_i-p_j|。
问最大贡献。
题解：
网络流题。
建模就考虑网格图，不考虑限制的话有一个最小割模型。
就是每行 m-1 个点，两两边权是 \inf-a_{i,j}。
这样可以保证每行只割一条边。
考虑限制，可以在限制的两行中行对应点两两连边，权为 C。
这样贡献就被拆成了很多个需要割开 C。
然后直接最小割就行了。
代码：
Link

K

题意： 傻逼题。
题解：
略
代码：
Link

L

题意：
有 01 串，有一些是 ?，表示既可以是 0 又可以是 1。
若干个限制，表示 [l,r] 必须是回文串。
问有多少方案。
题解：
参见这题然后做完了。
类似于建一个反串，然后相当于某个区间和某个区间相同。
然后并查集+st表维护就行了。
代码：
Link

M

题意： 略
题解： 签到题，直接离线然后求出 dfn 序。
用堆维护直接滞后删除就行了。
代码：
Link

N

题意：
略
题解：
直接离线，从大到小插入。
树状数组维护。
最难的地方在看懂题。
代码：
Link