VP 2022 ICPC 沈阳
The 2022 ICPC Asia Shenyang Regional Contest (The 1st Universal Cup, Stage 1: Shenyang)
这个题解怎么和 Claris 一个 slides 板子,给我看 ptsd 了(
Problems | AC |
---|---|
A. Absolute Difference | 待补 |
B. Binary Substrings | |
C. Clamped Sequence | ○ |
D. DRX vs. T1 | ○ |
E. Graph Completing | ⊕ |
F. Half Mixed | ⊕ |
G. Meet in the Middle | 待补 |
H. P-P-Palindrome | 待补 |
I. Quartz Collection | ⊕ |
J. Referee Without Red | |
K. Security at Museums | |
L. Tavern Chess | ○ |
M. Vulpecula |
D 签到
1 | void solve() { |
C
赛时秒出思路但是吃了发罚时,队友提醒了下发现 a[i] 作为上下界都可以,但是忘了枚举其中一种情况。
1 | void solve() { |
L
炉管题,队友做了。
F 贪心,构造
太神必了这题。
子矩形数量是 $\frac{n(n + 1)}{2} \times \frac{m(m + 1)}{2}$,如果这个数量是奇数则显然无解。
否则 $\frac{n(n + 1)}{2}$ 和 $\frac{m(m + 1)}{2}$ 至少有一个是偶数。不妨设后者是偶数。
赛时打表发现可以将问题转化到一维上去,然后堆叠起来。也就是解决 $1 \times m$ 的问题然后堆叠 $n$ 行。
对于一个 $1 \times m$ 的矩形,子矩形数量是 $\frac{m(m + 1)}{2}$,设每一个同色区间的长度是 $a_i$。那么纯色子区间数量就是 $\sum_{i = 1}^k{\frac{a_i(a_i + 1)}{2}}$,则问题转化为解下列方程组:
- $\sum_{i = 1}^{k} a_i = m$
- $\sum_{i = 1}^k{\frac{a_i(a_i + 1)}{2}} = \frac{m(m + 1)}{4}$
不难证明一定存在一组解,构造时贪心让每个 $a_i$ 尽可能大即可。
1 | void solve() { |
I 贪心、线段树
总的和是固定的,可以将游戏看作每块石头价值 $b_i$,但是先选的话就有 $a_i - b_i$ 的收益,后选的话收益为 $0$。
因此实际上双方就是按照 $a_i - b_i$ 从小到大分别选。A 拿第 0 个,B 拿第 1, 2 个,A 拿第 3, 4 个,以此类推,A 会拿 rank % 4 = 0 或 3 的。
因此维护一个权值线段树,下标是 $a_i - b_i$,维护区间内排名 % 4 相同的数的和即可。
1 | struct SGT { |
A Calculus
\begin{aligned}
& \int_l^r \int_l^r |x-y| \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \int_0^{r-l} |(x + l)-(y + l)| \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \int_0^{r-l} |x-y| \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \left(\int_0^{x} (x - y) + \int_x^{r-l} (y - x) \right) \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \left(\int_0^{x}x - \int_0^{x}y + \int_x^{r-l}y - \int_x^{r-l}x \right) \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \left(\int_0^{x}x - \int_x^{r-l}x - \int_0^{x}y + \int_x^{r-l}y \right) \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \left(x^2 - x(r - l - x) + \frac{1}{2} (r-l)^2 - x^2 \right) \mathrm{d} x\\
&= \int_0^{r-l} \left( x^2 - x(r - l) + \frac{1}{2} (r-l)^2\right) \mathrm{d} x\\
&= \frac{(r-l)^3}{3}\\
\end{aligned}
E 边双、容斥、TreeDP
给定一个 $n$ 个点 $m$ 条边的简单无向图,可以加入任意多条(包括 $0$ 条)边,使得这张图边双联通,求加边的方案数。
边双联通的定义:任意不同的两点存在至少两条没有重复边的简单路径。
对原图进行边双缩点,由于原图是连通的,缩点之后会得到一棵树。此时每加一条边 $(u, v)$ 就会对树上 $u$ 到 $v$ 的树上路径进行覆盖,当所有树边都被覆盖时就得到了一个边双连通图。
现在问题转化为:加若干条边,使得这棵树的每条树边都被新加的非树边覆盖至少一次。求方案数。
这个方案数不好求,考虑容斥:设至少有 $k$ 条边没被覆盖的方案数为 $g_k$,则答案为 $\sum_{k}(-1)^{k}g_k$。
把这个容斥扔到树上做 TreeDP。如果一些边被钦定了没被覆盖,那么这些边会把原树划分成若干连通块,连通块内任意连边。
设 $dp_{u, i}$ 表示以 $u$ 为根的子树的连通块大小为 $i$ 时子树内的方案数。转移时考虑一个子树 $v$ 是否连上来(即边 $(u, v)$ 是否被覆盖)。如果连上来的话就是乘上一个 $2^{siz_u + siz_v - 1}$ 的系数(减去的 1 是那条已经有的树边,除此之外的边都可以覆盖这条边),没连上来的话就是容斥系数 $-1$。
注意每个子树根节点的初值应设为 $dp_{u, siz_u} = 2^{\frac{siz_u(siz_u - 1)}{2} - cnte_u}$,其中 $cnte_u$ 表示边双连通分量中的边数。
注意要写个光速幂,这样转移的时候可以少个快速幂的 log。
另,用的是哥哥的 EBCC 板子,发现那个板子算 cnte 好像是有问题的,debug 了半天。。。。而且看了眼哥哥的代码,写的有点过于神秘了,看不懂。。。。。。
1 |
|
VP 2022 ICPC 沈阳