AGC039 题解

· · 个人记录

AtCoder Grand Contest 039

A - Connection and Disconnection

每个串中间的代价和每两个串交界处的一些相同字母的代价分开算即可。

code

B - Graph Partition

如果有解，必须保证图是一个二分图，因为显然一个奇环上一定构造不出合法解。

然后容易发现答案就是所有点对间最短路的最大值。

可以枚举起点然后 bfs 或者 直接 floyed。

code

C - Division by Two with Something

令一个 01 串 s 每位取反后得到的串为 s'。

通过思考/打表可以发现：

对于一个长度为 n 的 01 串 T，找到最短的一个 01 串 s 满足：T=s+s'+s+s'+\cdots +s+s'+s。

那么 T 回到自己的操作次数就是 2\times |s|。不妨令 s 为 T 的最短循环节（注意，这里和通常我们的定义是不一样的。）

考虑枚举 s 的长度然后容斥。

设枚举长度为 d，最短循环节长度为 d 的 T 的个数为 f(d)。这样答案就是 \sum f(d)\cdot d。显然，如果 f(d)>0 那么 d 必须是 n 的因数并且 \frac{n}{d} 是奇数。

对于每个 d，设 X 前 d 位构成的二进制数是 tot，那么 f(d) 要么等于 tot，要么等于 tot-1。暴力 \mathcal{O}(n) 判断一下 s=X_{1,\cdots ,d} 时的 T 是否 \leq X 即可。

容斥的时候就把合法的 d 的倍数减掉 f(d) 。

时间复杂度：\mathcal{O}(n\cdot cnt_d)。其中，cnt_d 的上界为 72。

code

D - Incenters

我不会 MO，再见。

知道了欧拉线就会做这题了。

结论：对于一个 \triangle ABC，设它分割成的 3 段圆弧的中点分别是 A',B',C'，那么 \triangle ABC 的内心的坐标就是 \triangle A'B'C' 的重心的三倍。（这里的“三倍”指的是横纵坐标都是三倍。）

重心很好算，就是 \left(\frac{X_{A'}+X_{B'}+X_{C'}}{3},\frac{Y_{A'}+Y_{B'}+Y_{C'}}{3}\right)

然后就能把每段弧分开算贡献。 \mathcal{O}(n^2) 暴力枚举即可。

code

E - Pairing Points

假设 1 和 x 相连，那么这个圆就成了 [2,x) 和 (x,2n] 两部分。

显然这两部分之间至少要有一条边相连。假设 [2,x) 中编号为a_1,a_2,\cdots a_m 的点与 (x,2n] 中编号为 b_1,b_2,\cdots,b_m 的点分别相连，（显然，a 是单调递增的，b 是单调递减的。），我们可以枚举 a_1 和 b_1 来防止 dp 时把方案算重。

设 dp_{l,x,r} 表示 [l,r] 这段区间中的点互相连，并且区间外有个点和区间内的编号为 x 的点相连时的方案数。

显然边界就是 l=r=x 时，dp_{l,x,r}=1。

枚举当前区间中的 a_1 和 b_1，分别设为 j 和 k（需要保证 j,k 之间有边）。

还需要枚举 p\in [j,i) 和 q\in (i,k]，表示分割成 [l,p],(p+1,q-1),[q,r] 三段区间。

那么，

dp_{l,x,r}=\sum\limits_{l\leq j\leq p<x<q\leq k\leq r} dp_{l,j,p}\times dp_{p+1,x,q-1}\times dp_{q,k,r}\times [a_{j,k}=1]

大概就是长这样：

答案就是 \sum dp_{2,x,n}。

暴力转移是 \mathcal{O}(n^7) 的，但是因为常数极为优秀所以可以轻松通过。

考虑如何优化。

观察 dp_{l,j,p} 和 dp_{q,k,r} 发现它们都和 x 无关，所以可以提前算出它们的贡献然后枚举 x 并把贡献添加到 dp_{l,x,r}。这样时间复杂度就是 \mathcal{O}(n^5) 的了。

我过懒了所以只写了个 \mathcal{O}(n^7) 的代码。

code

F - Min Product Sum

设第 i 行的最小值为 a_i，第 j 列的最小值为 b_j，那么 (i,j) 的贡献是 \min \{a_i,b_j\}，方案数是 K-\min\{a_i,b_j\}+1。

如果 a_i 和 b_j 都被钦定了，那么在不保证所有第 i 行最小值等于 a_i 和所有第 j 列最小值等于 b_j 时的贡献为：

\prod\limits_{i,j}\min\{a_i,b_j\}\times (K-\min\{a_i,b_j\}+1)

考虑把不合法方案容斥掉，即：再钦定若干行/列的实际最小值大于钦定的最小值。

那么可以令 dp_{k,i,j} 表示用 [1,k] 范围内的数填好 i 行 j 列的所有方案的系数之和。

有个朴素的转移就是枚举被容斥的行数和列数还有没有被容斥的行数和列数，但是这样复杂度过高。

仔细观察发现 4 种转移的转移系数是互不影响的，所以可以分开枚举然后转移。

（转移方程可参考小粉兔的题解）

时间复杂度：\mathcal{O}(Knm(n+m))。

有点卡常。

code