AtCoder Grand Contest 039 题解

AutumnKite · 2020-09-18 10:32:37 · 个人记录

比赛地址

A - Connection and Disconnection

题意

给定字符串 S 和一个整数 k，令 T 为将 S 复制 k 份依次拼接得到的字符串。

求最少需要改变 T 中的几个字符使得 T 中任意两个相邻的字符不同。

题解

考虑 k=1 时如何求答案。设字符相同的连续段长度依次为 l_1,l_2,\ldots,l_m，那么答案为 \sum\limits_{i=1}^{m} \lfloor\frac{l_i}{2}\rfloor。

题解

有解的充要条件是没有奇环。

我们钦定一个点 u 在第一层，那么剩下点的分层方式一定是按 BFS 树分。具体证明可以根据 BFS 树的性质进行证明。

时间复杂度 O(N^3)。

代码

C - Division by Two with Something

题意

给定一个整数 n 以及一个 n 位二进制数 X，求对于 0\le k\le X，执行若干次（不为 0 次）以下操作第一次变回原来的 k 的操作之和：

• 若 k 是奇数，则减 1 后除以 2；若 k 是偶数，则除以 2 后加 2^{n-1}。

对 998244353 取模。

题解

先不考虑 X 的限制。

执行题目中的一次操作相当于把最后一位取反后放到最前面。而执行不超过 n 次操作相当于把一段后缀取反后放到最前面。

即若把操作的数的二进制表示从高位到低位看成一个字符串 S，我们要求最小的 p 使得 \operatorname{not}(S[n-p+1,n])+S[1,n-p]=S。注意到若操作次数大于 n，条件与上述条件相同，所以若不存在这样的 p 那么答案一定是 2n。

发现满足上述条件的字符串一定是由一个长度为 d\ (d\mid n,d < n) 的字符串每次取反加入到 S 中，执行 \frac{n}{d} 次后得到的结果。如 n=9,d=3 时，可以构造出形如 000111000,001110001 的字符串。而这样构造得到的字符串一定有最小的 p=2d。

于是考虑枚举 d，那么方案数为 2^d，操作次数为 2d，对答案的贡献为 2^d\times 2d。

可是这样做会有问题，例如 n=9,d=3 时会构造出 010101010 这样的字符串，但这样的字符串的 p 应为 2，应该在 d=1 时被计算。所以容斥即可。

有 X 的限制时同理，前 d 位小于 X 的前 d 位时方案数就是 X 的前 d 位，等于时只有一种，直接构造出字符串判断是否小于等于 X 即可。

时间复杂度 O(d(n)n)，其中 d(n) 表示 n 的因子数量。

代码

D - Incenters

题意

给定单位圆上的 N 个点，求随机选择三个不同的点形成的三角形的内心的坐标的期望。

题解

假设三角形的三个顶点为 A,B,C，我们可以得到 \angle A,\angle B,\angle C 的角平分线与圆的交点，分别记做 A',B',C'。根据圆心角、圆周角的相关性质可以得到 A',B',C' 分别是弧 BC,CA,AB 的中点。可以根据这一性质继而证明 \triangle ABC 的内心与 \triangle A'B'C' 的垂心重合。

另外，根据欧拉线的相关性质，有三角形的重心 G 在外心 O 和垂心 H 的连线段上，且 OH=3OG，即 \overrightarrow{OH}=3\overrightarrow{OG}。

于是我们把垂心的计算转化成了重心的计算。

三个点 A'(x_1,y_1),B'(x_2,y_2),C'(x_3,y_3) 形成的三角形的重心为 (\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3})。此题由于 A',B',C' 都在单位圆上，外心为原点，所以垂心即为 (x_1+x_2+x_3,y_1+y_2+y_3)。

于是我们可以枚举 N 个点之间两两形成的弧，求出该弧的中点对答案的贡献即可。

时间复杂度 O(N^2)。

代码

E - Pairing Points

题意

有 2N 个点共圆，按逆时针编号 1 到 2N。保证任意六个不同的点形成的三条线段不经过同一个点。

这些点之间有一些线段相连，你需要选出 N 条线段，使得：

• 每个点恰好属于一条选出线段。
• 若把选出的线段之间的交点看做顶点，把线段看做边，则形成一棵树。

求方案数。

题解

首先可以枚举与 1 相连的点，然后将环分成两部分。

令 f_{l_1,r_1,l_2,r_2} 表示 [l_1,r_1] 与 [l_2,r_2] 配对（中间已经有一条线段）的方案数。跨越中间的匹配一定是在 [l_1,r_1] 中选一些点 x_1,x_2,\ldots,x_m\ (x_i < x_{i+1})，在 [l_2,r_2] 中选一些点 y_1,y_2,\ldots,y_m\ (y_i > y_{i+1})，然后 x_i 与 y_i 匹配，如下图所示：

为了防止算重和方便转移，我们再引入 g_{l_1,r_1,l_2,r_2}，定义与 f 类似，但是强制跨越中间的线段只能选一条。

那么 f 的转移只需要枚举 x_m,y_m 所在的区间即可：