AtCoder 做题寄录

天命之路 · 2022-08-05 21:32:18 · 个人记录

AtCoder 是人类智慧题的集中区，天天上 AtCoder 逛的也不是什么正经人（

AGC018D

题意：给一棵带权树，建立一个完全图使得 G_{i,j} = dis(i,j) ，求最长哈密顿路径。

看到题后，有一个直觉就是，设边 i 两边的连通块中，较小的那个的大小为 S_i ，则答案为 ans = \sum 2S_iw_i

我们如果求的是哈密顿回路，这个答案真的是对的，虽然它看上去很不靠谱。

但哈密顿路径没有那个“回”的过程，所以答案会稍微小一些。

这题要针对重心进行分类讨论，我们知道一棵树有一个或两个重心，且如果有两个重心，则这两个重心相邻。

1. 如果有两个重心

这等价于存在一条边 e 使得 S_e = n / 2，e 的两个端点分别为两个重心，显然，虽然 2S_e = n ,但这条边最多被经过 n - 1 次，所以答案减去 w_e

2.如果有一个重心

重心有个性质在于：删去重心后，剩余每个联通块的子树大小都不大于 n / 2

设该重心为 G,连出去的边为 e_1,e_2,\dots,e_k，对应的联通块为 T_1,T_2,\dots,T_k。

我们是没法让这 k 条边都走到最理想的次数的，否则我们开始时要在每个 T_i 外面，结束时也要在每个 T_i 外面，但不再 T_{1 \dots k} 中的点只有 G 一个。

我们考虑牺牲权值最小的那条边，这样答案就是 \sum 2S_iw_i - \min\{w_{e_1},\dots,w_{e_k}\}

因为每个|T_i| 都不超过 n/2 ，所以我们可以构造方案，使得每个p_j 和 p_{j+1} 都不在同一个 T_i 中，这容易理解。

总的来说，这个题容易有一个直觉，即考虑边的贡献，但想出正确的分类讨论并不容易，需要对重心的性质有非常敏感的直觉。

在众多 AGC 题目中，这题的题解算比较详细的了。

AGC011C

题意：给出两张无向图 A = (V_A,E_A),B = (V_B,E_B)，构造一张新的图 C ，满足 V_C = V_A \times V_B ，新图中的点 (a,b) 和 (a',b') 有边当且仅当 a 与 a' 有边且 b 与 b' 有边，求C 的连通分量个数。

（原题中是 A = B 的情况）

我们先考虑 A 和 B 均连通的情况。

容易发现，点 (a,b) 和 (a',b') 连通，当且仅当存在一个数 l ，使得 a 到 a' 有长度为 l 的路径，b 到 b' 也有长度为 l 的路径。

我们很容易把路径的长度加上 2，所以我们只需考虑路径长度的奇偶性。 （这是无向图上非常重要的思想，如果在理论层面出现了“路径长度”，容易将其转化为奇偶性，然后使用二分图相关理论解决问题）

如果 A 和 B 都是二分图，设两部分别为 S,T，那么S_A \times T_A \cup S_A \times T_B 是不连通的，因为 S_A 内部没有连边，所以只需考虑两个分量 S_A \times T_A \cup S_B \times T_B和 S_A \times T_B \cup S_B \times T_A.

这两个分量之间没有连边，另一方面，在二分图中，一个点到另一个点的路径的奇偶性是确定的，而这两个连通分量分别对应两种可能的奇偶性。

相反地，如果A 和 B 有至少一个不是二分图，我们肯定能通过走一个奇环来反转奇偶性，故每一对点都有办法连通，就只有一个连通分量。

考虑 A 和 B 不一定连通的情况，设点的数量分别为 N_A,N_B ，孤立点数量分别为 i_A,i_B ，不是二分图的连通分量数为 p_A,p_B，是二分图的连通分量数为 q_A,q_B， 则答案为

这题涉及到一个重要思想，对于这种图长得比较奇怪的题，我们不要去尝试想象图的形状，而是尝试分解问题，并针对”连通性”等字眼转化为路径问题，再注意到无向图上路径长度的奇偶性，解决问题。

同样用到了这个重要思想的还有 [HNOI2019]校园旅行

AGC009C

题意：将 n 个数 s_1,\dots,s_n (s_i \lt s_{i+1}) 分成两个集合 S,T ，满足 S 中任意两数的差的绝对值大于等于 A，T 中任意两数的差的绝对值大于等于 B ，求方案数。

设 F_{i,j,0/1} 表示 dp 到第 i 个数，上一个与元素 i 不在同一个集合的元素是 j，0/1 表示 i 在 S 或者 T 集合。

则显然有转移：

对于 j = 0 的情况稍稍注意一下。

对于这种 dp 的优化，我们可以尝试把第 i 位滚动掉，并尝试用数据结构维护转移。

注意到对于第一、三种转移，如果不满足条件，我们把数组全部置为 0 即可，否则啥都不用干。

对于第二、四种转移，只有一个特殊点会被转移，同时 j 的取值也是一个区间。

所以，我们维护一颗支持全局赋 0，单点修改，区间求和的线段树即可。

如果要划分两个集合的话，这种 dp 状态的设计是比较套路的。

ARC117D

题意：给一棵无权树，要求构造一组正整数 E_1,E_2,\dots,E_n 满足对于任意 1 \le i,j \le n，都有 |E_i - E_j| \ge dis(i,j)，同时让 \max(E) 最小，然后输出 E

如果我们构造好了一组 E，那么一定存在一个排列 p_1,p_2,\dots,p_n 满足 E_{p_i} \le E_{p_{i+1}}

那么 E_{p_n} - E_{p_1} \ge \sum_{i=1}^{n-1} dis(p_i,p_{i+1})

为了让上界最小，我们取等号。

问题转化为找到排列 p_1,p_2,\dots,p_n 使得 \sum_{i=1}^{n-1} dis(p_i,p_{i+1}) 最小（有趣的是，上面那道题要让他最大)

我们还是考虑回路的情况，这种时候每条边最少也要被经过两次，答案为 2(n - 1)

如果去掉dis(p_n,p_1) ，答案即为 2(n - 1) - dis(p_1,p_n) 。

取 p_1,p_n 为直径的两个端点即可。

这道题巧妙地把上界表示了出来，以至于我都不知道如何总结了。

ARC115E

给出一个数列 a_1,a_2,\dots,a_n ，求满足以下要求数列的个数：

• 1 \le X_i \le a_i
• X_i \ne X_{i+1} (1 \le i \lt n)

当然这题有 sb 线段树做法，但我做这题的CF原题的时候写了一遍线段树了，不想写了。

考虑容斥，设有 k 个位置满足 x_{i-1} = x_i，其余随意的方案为 f(k)，答案就是 \sum_{k=0}^n (-1)^k f(k)

考虑 dp，

对于建立在容斥上的 dp 有一个套路，就是把容斥系数放进转移里面。

鉴于此设计 dp，设 F_i 表示前 i 位的方案。

转移的意义是考虑 a_j = a_{j+1} = \dots = a_i

因为有 \min 所以用单调栈优化转移，因为有 (-1)^{i-j} ，所以分奇偶记录前缀和即可。

ARC116E

题意：给出一棵树，要求选出 K 个点 p_1,p_2,\dots,p_k，最小化 \max_{i=1}^n\min_{j=1}^k dis(i,p_j)

看到这玩意考虑二分，设一个时间 T，问题转化为每个点都要在时间 T 内被某一个点到达。

我们称一个被选中的节点覆盖了所有与他距离小于等于 T 的节点。

考虑设计树形 dp，算出为了到达目的最少需要几个点。

我们要记录如下状态（这也是我不太能想到的地方）：

• 如果根节点被某个选中节点到达了,求出最近的那个选中节点和它的距离。
• 如果根节点没有被某个选中节点到达，求出距根节点最远的没有被选中节点覆盖的节点
• 这个子树内选了几个节点

如果有些选中节点能够覆盖别的子树的未覆盖节点，我们就不需要选中根了，这可以用前两个记录的信息来判断。

AGC020C

给出一个长度为 n 的数列 A_1,A_2,\dots,A_n，将其所有非空子序列的和排成一个序列 S_1,S_2,\dots,S_{2^n - 1}

求出该序列的中位数，即 S_{2^{n-1}}

题解：

这题肯定不能使用常规的二分中位数来做。

令 S_0 = 0 表示空序列的和。

既然要求中位数，考虑把这 2^n 个序列对半分，也就是分出 2^{n-1} 个数对 (P,Q)，我们不妨设 \sum P \le \sum Q

分数对也要讲究分法，我们让 P 并上 Q 等于原序列，那么 (P,Q) 也就是一个原序列的划分，这样看上去更加贴近“中位数“的有关性质。

设 Sum = \sum A

则 \sum P \le \frac{1}{2}Sum,\sum Q \ge \frac{1}{2}Sum

所以我们的这种分法，正好把这 2^n 个子序列平均分到 \frac{1}{2} Sum 的两端。

那么我们所求的就是大于等于 \frac{1}{2}Sum 的最小的能凑到的和。

使用 bitset 背包即可。

做的时候，直接证明较为困难，可行的思路是猜出结论与 \frac{1}{2} Sum 有关。

ARC064D

这题一眼望过去，用不了什么现成的科技，最朴素的思路就是，考虑每个串会被算几次。

事实上，一个串会被算多次，也意味着有两个回文串互相循环同构。

循环同构也会出现所谓“重复”的情况，这与一个串的最小整周期有关。

如果一个回文串的最小整周期为 x，那么只有 x 个串是“可能有用的”

故我们先考虑一个周期内的问题。

回文串有两种：AA^r 和 AcA^r (A^r 表示 A 的翻转，c 表示一个字符)

对于 AA^r ，与其循环同构的回文串只有 A^rA

对于 AcA^r，没有与其循环同构的回文串。（这就是我没有发现的地方）

所以如果 x 是偶数，一个回文串会带来 \frac{x}{2} 的贡献，否则带来 x 的贡献。

接下来考虑如何算周期为 x 的回文串个数。

先可以算周期是 x 约数的回文串个数，为 K^{\lceil \frac{x}{2} \rceil}，再用其约数的答案来减即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 6000,P = 1e9 + 7;
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
int factor[N],f[N],tot,n,k;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i = 1;i * i <= n;i++)
    {
        if(n % i) continue;
        factor[++tot] = i;
        if(i * i != n) factor[++tot] = n / i;
    }
    sort(factor + 1,factor + tot + 1);
    int ans = 0;
    for(int i = 1;i <= tot;i++)
    {
        f[i] = qpow(k,(factor[i] + 1) >> 1);
        for(int j = 1;j < i;j++)
            if(factor[i] % factor[j] == 0) (f[i] += P - f[j]) %= P;
        ans = (ans + 1ll * ((factor[i] & 1) ? factor[i] : factor[i] / 2) * f[i] % P) % P;
    }
    cout << ans << endl;
    return 0;
}

ARC067F

容易发现最终选择的烧烤店一定是一段区间。（推到这里花了15分钟）

对于 l,r,其答案为 \sum_{i=1}^m \max_{j=l}^rB_{j,i} - (s_r - s_l)

重点在与 \sum_{i=1}^m \max_{j=l}^r B_{j,i}

如果你想着开 m 个数据结构，扫描线增量维护，必然会陷入难以统计答案的困局，因为 \sum 与 \max 是极不好复合的。（挂在这里）

正确的做法是，考虑每个 B_{j,i} 的贡献。

每一维是独立的，而在每一维中 ，我们设 l_j 表示 j 左边第一个大于 B_{j,i} 的数，r_j 表示 j 右边第一个大于等于 B_{j,i} 的数。那么，当且仅当 L \in [l_j+1,i],R \in [i,r_j - 1] ，B_{j,i} 会对区间 [L,R] 的答案造成贡献。

使用二维差分把这个子矩形整体加即可。

而原来的 dp[i][l][r] 则是现在的 dp2[i][l + r] * \binom{l + r}{l}，我们用组合数规定这 l + r 次有效操作的顺序。

然后对于满足条件的 l,r 统计即可。

本题的关键在于观察到“有效操作”的特殊性，以及根据有效操作的特点设计倒流式的 dp，这种“有效操作”其实跟普通的赋值具有很相近的特点，故思想也是相似的。最后一步的优化也非常好，是对转移方程的观察与思考。