AtCoder 记录

总览

为什么你们都有脑子

(color{red}igodot) | AGC002

考虑从大到小排序后填成一个网格图，删去最大的就相当于删去最左边一列，每个数 (-1) 就相当于删去最下边一列。则相当于起点为 ((1,1))，每次可以向上或向右走，走出界者输。

直接 DP 显然不行。观察这个网格图可以发现，每条对角线内部的状态都是相同的。直接判断 ((1,1)) 所在对角线状态即可。

证明：

若 ((x+1,y+1)) 为必败，则无论先手在 ((x,y)) 怎么走，后手都可以走到 ((x+1,y+1))，即 ((x,y)) 必败。

若 ((x+1,y+1)) 为必胜，则 ((x+2,y+1),(x+1,y+2)) 至少有一个必败，由上得 ((x+1,y),(x,y+1)) 至少有一个必败，即 ((x,y)) 必胜。

(color{red}igodot) | AGC006

设 (f(i)) 表示点 (i) 的期望坐标，容易得到转移 (f(i)gets f(i-1)+f(i+1)-f(i))。

转移很复杂，考虑差分，设 (d(i)=f(i)-f(i-1))，则转移之后

[egin{aligned}d(i)&gets(f(i-1)+f(i+1)-f(i))-f(i-1)=f(i+1)-f(i) \ d(i+1)&gets f(i+1)-(f(i-1)+f(i+1)-f(i))=f(i)-f(i-1)end{aligned} ]

发现转移一次等价于交换 (d(i)) 和 (d(i+1))，则转移 (m) 次之后相当于一个置换。可以直接对置换做快速幂。但也可以把置换内部若干环提出来，则该环内的点做 (K) 次置换相当于做 (K mod mathrm{size}) 次，则可以做到线性。

考虑二分，设 (b_i = [a_i ge mathrm{mid}])，手玩一下可以发现，假如 (b) 中存在一段离第 (n) 位最近的 (00)，此时 (b) 序列相当于 (cdots color{red}00color{black}101cdots101color{red}00color{black}cdots)，每次这个 (00) 都会向中间拓展一位，则最后顶上的数只和离中间最近的一段 (00) 或 (11) 有关。

(color{red}igodot) | AGC009

考虑朴素的 DP，设 (f(i)) 表示第一个集合最后一个数是 (a_i) 的方案数。

考虑 (j) 要转移到 (i) 需要满足：

  1. (j < i)
  2. (a_i-a_j ge A)
  3. (forall x,y in [j+1,i-1],|a_x-a_y| ge B)

然而这样转移是错的，若 (a_{j+1}-a_{j-1} < B) 就会有问题。

但是如果钦定 (A ge B)，易证存在这种情况则该序列一定无解。所以特判掉即可。

(color{red}igodot) | AGC028

相当于在 (2n) 个 (a,b) 中选 (n) 个 (a,b)。设选择的集合为 (S)，则每个点被选的情况有四种：(00,01,10,11)。

如果全是 (01) 或 全是 (10)，就把它们全部接起来就行。

如果既有 (01) 又有 (10)，容易证明 (00) 和 (11) 的个数一定相等。如果有 (00,11)，在 (01) 和 (10) 中间塞即可，否则一定不合法。

上面是构造方案合法的必要条件。但实际上我们只用考虑这个条件，因为如果没有选 (min)，显然选了 (min) 的方案也会被这个条件判为合法，即没选 (min) 不会产生贡献。

考虑最优解为什么。先对 (2n) 个 (a,b) 排序得到 (p_1,p_2,cdots,p_{2n})，选 (p_1,p_2,cdots,p_n)，如果不合法就选 (p_1,p_2,cdots,p_{n-1},p_{n+1})，如果还不合法，则 (p_n,p_{n+1}) 一定是某个点 (u) 的一对 ((a_u,b_u))。强制同时不选 (p_n,p_{n+1})（即 (00)）或强制同时选 (p_n,p_{n+1})（即 (11)）都是合法的，取其中的最小值即可。

(color{red}igodot) | AGC043

若 (n=1) 则直接输出，否则差分一次之后原序列值域就变成了 ({0,1,2})。那我们先差分一次，并且令 (n gets n-1)。

若序列中有 (1)，则答案一定不为 (2)。此时 (x_{i,j}=|x_{i-1,j}-x_{i-1,j+1}| Longleftrightarrow x_{i,j}=(x_{i-1.j}+x_{i-1,j+1})mod 2)。则 (x_{n,1}=left(sum_{i=1}^n inom{n-1}{i-1}x_{1,i} ight) mod 2)。若序列中没有 (1)，则先把整个序列除以 (2)，就和前面一样，最后再乘 (2) 即可。

有一个结论：(dbinom n m mod 2 = [n land m = m])，具体证明可以考虑质因子 (2) 的次数，也可以考虑 Lucas 定理。

(color{red}igodot) | AGC044

考虑平移操作，每次相当于令最低位 (0 o 1,1 o 2,2 o 0)，并且最低位是 (2) 的数继续考虑次低位的变换。则把所有数倒着插入到 Trie 上，平移操作就相当于是在 Trie 上的一条链跑。至于 (1,2) 互换操作就是打一个翻转标记。

一个看不懂的 DP 做法

(color{orange}igodot) | ARC059

考虑用 (n) 部构造出的字符串 (s)，字符串的个数有 (2^{|s|}) 个。

设 (f(i,j)) 表示 (i) 步构造出长度为 (j) 的字符串的方案数，显然有

(f(i+1,j+1) gets f(i+1,j+1)+2f(i,j))

(f(i+1,max{0,j-1}) gets f(i+1,max{0,j-1}) + f(i,j))

则答案为 (dfrac{f(n,|s|)}{2^{|s|}})。

(color{orange}igodot) | ARC063

用 DP 求出每个点可选数的区间即可。

有 (ans ge 2 imes max{W,H}+2)，则容易证明最优矩形一定经过 (y=dfrac H 2) 或 (x=dfrac W 2)。上 DS 即可。

(color{orange}igodot) | ARC066

考虑 (a+b=(aoplus b)+2(a land b))，容易发现每个合法 ((u,v)) 都对应唯一的 ((a,b))。

显然 (u le v)，则只需要令 (vle n) 即可。

设 (f(i)) 表示满足 (v le i) 的 ((u,v)) 的方案数。

考虑这个时候对 (f(i)) 对应的所有数增加一个最低位。

由上得最低位只有三种情况：((0,0),(0,1),(1,1))。

若为 ((0,0))，则 (i'=2i)。

若为 ((0,1))，则 (i'=2i+1)。

若为 ((1,1))，则 (i'=2i+2)。

则 (f(i)=fleft(leftlfloor frac i 2 ight floor ight)+fleft(leftlfloor frac {i-1} 2 ight floor ight)+fleft(leftlfloor frac{i-2} 2 ight floor ight))。

可以发现每个 (i) 只会转移到两个状态 (k,k-1)。手玩一下可以发现再递归下去还是两个数，则总时间复杂度为 (O(log n))。

显然括号只会加到 (-) 号后面，一个括号内的形式是 ((++cdots++-cdots))，则 (+) 号的都会变成负数，而内部第一个 (-) 号开始的所有数都可以通过加括号变成正数。直接枚举最外层括号位置即可。

(color{orange}igodot) | ARC074

只用考虑每种颜色第一次出现的位置。设 (f(i,j,k)) 表示考虑到 (a_i,a_{i+1},cdots,a_n)，其中 (a_j) 是第一个 ( eq a_i) 的，(a_k) 是第一个 ( eq a_i) 且 ( eq a_j) 的，直接转移即可。

(color{orange}igodot) | ARC082

点集 (S) 构成的凸包内部有 (k) 个点（不包括凸包端点），则贡献为 (2^k)。

考虑组合意义，即为 (k) 个点选或不选的总方案数。每一种方案都能构成一个集合 (T)。容易证明，(Scup T) 只会出现一次，因为 (Scup T) 能构成的凸包是唯一的。

所以答案即为 (n) 个点中，选若干个点能构成凸包的方案数。

考虑补集转化，求不能构成凸包的方案数。总方案数显然为 (2^n-1)。不能构成凸包的充要条件是只有不超过两个点，或者有至少三个点，且其中有至少三个点贡献。

那么可以先减去只有一个点的情况，即减去 (n)。然后枚举两个点 (i,j)，求出有多少个点与 (i,j) 共线即可。

时间复杂度为 (O(n^3))。

设 (f_A(t)) 表示起点为 (A)，到了时间 (t) 时的沙子数，容易用 (O(t)) 的时间递推求出。

画出 (f_0) 和 (f_X) 的图像，容易发现任意 (Ain[0,X])，(f_A) 都夹在 (f_0) 和 (f_X) 的中间。

可以预处理出 (f_0,f_X)，设 (s_A(t)) 表示不考虑上下界时，起点为 (A)，到达时间 (t) 的沙子数。容易证明，如果有一个时刻 (t'in[0,t]) 满足 (s_A(t') < 0) 或 (s_A(t') > X)，则一定有 (s_A(t)<f_0(t)) 或 (s_A(t)>f_X(t))。否则全过程并没有越过上下界，答案即为 (s_A(t))。

实际实现只需要预处理出 (s_0)，容易得到 (s_A(t)=s_0(t)+A)。

故答案为 (min{f_X(t),max{f_0(t),s_A(t)}})。

(color{orange}igodot) | ARC083

位于点 ((x,y)) 的球可以被 A 类机器人 (a_x) 或 B 类机器人 (b_x) 选。让 (a_y) 向 (b_x) 连边，则原问题转化成每条边选一个点，要求每个点只被选一次。

因为总点数等于总边数，所以若某个连通块的点数与边数不相等，则显然无解。

若有解，此时建出来的图是一个基环树森林。对每条边定向，让每条边指向拿走它的点，则会形成若干个外向基环树，每个基环树有 (2) 种定向方案。

考虑分配好每个机器人选的球后，要如何让这些机器人的排列顺序合法。

若一个 B 类机器人 (b_x) 选了球 ((x,y))，则对于任意满足 (y' < y) 的球 ((x,y'))，都要有一个 A 类机器人 (a_{y'}) 比 (b_x) 先选走球 ((x,y'))。对于 A 类机器人也同理。

连接上述所有 (a_y' o b_x) 和 (b_{x'} o a_y)，容易发现每个 A 类机器人如果有出边，一定是连向一个 B 类机器人，对于 B 类机器人也同理。那么就可以建出一个内向树森林。

容易算出这个内向树森林的合法拓扑序个数，然后直接算。

(color{orange}igodot) | ARC084

考虑一个数 (u) 的各位和是 (mathrm{sum}(u))。(u) 可以转移到 (10u)，贡献是 (mathrm{sum}(u))；(u) 也可以转移到 (u+1)，贡献是 (mathrm{sum}(u)+1)。对 (u mod K) 跑 01-BFS 即可

(color{orange}igodot) | ARC089

题解

(color{orange}igodot) | ARC092

考虑 (u o v) 变成 (v o u) 会产生影响的条件是什么。

  1. (u,v) 在同一个强连通分量中：
    若存在 (u ightsquigarrow v) 不经过 (u o v)，则该强连通分量不会被破坏；否则会被破坏。

  2. (u,v) 不在同一个强连通分量中：
    若存在 (u ightsquigarrow v) 不经过 (u o v)，则不会产生影响；否则它们会连成一个新的强连通分量。

可以跑一次 Tarjan 判断是否在同一个强连通分量。

当然你会发现 (u,v) 在同一个强连通分量的充要条件是存在 (v ightsquigarrow u)，则跑 (n) 次 DFS 求出任意两点能不能到达也可以。

关键是如何判断是否存在 (u ightsquigarrow v) 不经过 (u o v)，这个问题等价于 (u o v) 是否是 (u ightsquigarrow v) 的必经边。

考虑删除 (u) 以及与其相关的边，对于 (u) 原先指向的点 (v_1,v_2,cdots,v_k)，按顺序从 (v_1) 到 (v_k)，跑 (k) 次 DFS 标记每个点最先可以被哪个 (v_i) 经过。然后再把 (u) 出边顺序反过来，从 (v_k) 到 (v_1)，跑 (k) 次 DFS 标记每个点最先被哪个 (v_i) 经过。

对于 (u o v)，若 (v) 两次被标记的结果一样（或者说 (v) 在两次 DFS 树上深度都是 (1)），则 (u o v) 是 (u ightsquigarrow v) 的必经边。

预处理出来后随便判断一下就好。时间复杂度为 (O(nm))。

当然也可以更快。

考虑复杂度带上 (m) 的原因是上面求必经点的 DFS 中，每个点即使被标记了，也可能再被若干条边枚举到。

设 (S_u) 表示删去 (u) 后，当前还没被标记的点的集合，设 (G_x) 表示 (x) 的出点集合。把上面的对 (v_i) 跑 DFS 改成跑 BFS，则每次只需要枚举 (S_u cap G_x) 即可。

把它们放到 bitset 上，可以用下面的代码快速求出每个 (1) 的位置。

for (int i = T._Find_first(); i != T.size(); i = T._Find_next(i))

时间复杂度为 (Oleft(dfrac{n^3}w+m ight))。

(color{orange}igodot) | ARC103

若 (u) 是 (v) 的父亲，(d(u) = d(v) + 2mathrm{size}_u- n)。显然按 (d_i) 排序后最小的是重心，最大的是叶子。从大到小排序后枚举每一位，第一位一定是叶子所以 (mathrm{size}=1)，则父亲的 (d) 也是确定的，直接二分即可。又因为按照这个顺序构造，枚举到每一位的时候，该位置的 (mathrm{size}) 都已经被确定，所以构造方案是唯一的。然而这样做只是保证 (Delta d) 合法，还要跑一次换根 DP 判断 (d) 是否合法。

(color{orange}igodot) | ARC107

设 (f(i,j)) 为 (i) 个数拼出 (j) 的方案数。

如果第 (i) 个数选 (1)，显然方案数为 (f(i-1,j-1))。

如果第 (i) 个数不选 (1)，则可以选 (dfrac 1 2,dfrac 1 4,cdots)。考虑全部 ( imes 2)，则变成可以选 (1,dfrac 1 2,cdots)。显然方案数为 (f(i,2j))。

则有转移 (f(i,j) = f(i-1,j-1)+f(i,2j))。

因为 (f(i,2j)) 存在仅当 (i ge 2j)，所以 (j) 最多只需要枚举到 (i)。

答案为 (f(n,m))，复杂度为 (O(n^2))。

(color{orange}igodot) | ARC111

边 (i) 连接点 (a_i) 和点 (b_i)，原问题变成每次选一条边的一个端点，最多能选多少个点。

如果是一棵树，则可以选 (n-1) 个点。如果是一张图，则选出一个生成树，肯定存在一个点被非树边覆盖，所以可以选 (n) 个点。

(color{orange}igodot) | ARC115

考虑图为一棵树，如果 (k) 为奇数，则答案为 (0)；如果 (k) 为偶数，则答案为 (dbinom n k)。

证明：如果 (n = 1)，则显然成立。如果 (n>1)，则考虑选一个叶结点，然后选择是否选叶结点连接的边。如果不选这条边，则原问题变成 (n-1) 个点里要求 (k) 个点为奇点。如果选这条边，则原问题变成 (n-1) 个点里要求 (k-2) 个点为奇点，一直推下去即可。

然而可能图不连通，所以要分别 DP 然后乘起来。

离散化之后能选的数分成 (m) 段。设 (f(i,j)) 表示选前 (i) 个数，第 (i) 个数放在第 (j) 段的方案数。

显然有 (f(i,j) = sumlimits_{k=1}^{m} f(i-1,k) - f(i - 1,j))，转移是 (O(n^2)) 的。

建一棵线段树，先整体 ( imes -1)，再整体加值，第 (j) 段 (+ len_j imes sumlimits_{k=1}^m f(i-1,k))，其中 (len_j) 表示第 (j) 段对应的数的数量。最后区间 ( imes 0) 即可。

(color{orange}igodot) | ARC116

分别考虑 (a_n=1,2,cdots,m) 的情况，设 (a_n = prodlimits_{i=1}^tp_i^{c_i})，则方案数为 (prodlimits_{i=1}^tdbinom{n+c_i-1}{c_i})。

显然这是一个积性函数，把 (dbinom{n+c_i-1}n) 拆成 (prodlimits_{j=1}^{c_i}dfrac{n+j-1}{j})，然后做线性筛即可。

考虑到 (igopluslimits_{i=1}^n a_i = 0)，则拆位之后，每一位只有偶数个 (a_i) 为 (1)。

设 (f(i)) 表示 (sumlimits_{j=1}^n a_j=i) 的方案数，则有

[f(i)=egin{cases}sumlimits_jdbinom n {2j} fleft(dfrac{i-2j}2 ight)& i mod 2 =0\0 & i mod 2=1end{cases} ]

答案为 (f(m))。

(color{orange}igodot) | ARC121

如果只能每次选两个，显然是排序后选 ((1,n),(2,n-1),cdots)。

只选一个可以看作把它和 (0) 配对，则可以在原序列塞若干个 (0) 使得序列长度为偶数，然后每次选两个。枚举加几个 (0) 即可。

(color{orange}igodot) | ARC123

(color{orange}igodot) | ARC124

考虑到 (x,y) 一定分别是 (a_1,b_1) 的因数。

那我们可以枚举 (x,y)，然后判断是否满足必要条件：(x|a_i,y|b_i) 或 (x|b_i,y|a_i)。

显然对于不满足充分条件的 (x,y)，(operatorname{lcm}(x,y)) 一定不为最优。

时间复杂度为 (O(nsqrt{a_1b_1}))。

(color{blue}igodot) | ABC214

可以发现同一个强连通分量内的点，只要遍历了一个就可以遍历全部，所以先缩点。容易发现缩点后就是一个费用流板子，在 DAG 上 DP 求出初始势能之后跑 Primal-Dual 即可。

(color{blue}igodot) | ABC218

先跑一次 BFS 求出一条最短路，如果被删的边不在这条最短路上，则对答案没有影响。如果在这条最短路上，就暴力跑一次 BFS 即可。时间复杂度为 (O(nm))。

显然可以颠倒颜色使得 (R gets min{R, n - R})，容易证明可以转化成选 (R) 个不相邻的点，如果选了位置 (i)，则贡献为 (a_{i-1}+a_i)。

容易发现这是一个凸函数，直接 WQS 二分即可。

貌似也可以分治。具体见官方题解。

(color{blue}igodot) | ABC219

设做一次 (s) 的移动顺序为 ((x_0=0,y_0=0) o (x_1,y_1) ocdots o(x_n,y_n))，又设 (A=x_n,B=y_n)，则第 (k) 次 (s) 的移动顺序相当于 ((x_0+A,y_0+B) o(x_1+A,y_1+B) ocdots o(x_n+A,y_n+B))。

考虑 ((x_0,y_0),(x_1,y_1),cdots,(x_{n-1},y_{n-1})) 分别的贡献。设 (t_i) 为最小的 (k)，使得 (exists j eq i,(x_i+kA,y_i+kB)=(x_j,y_j))。可以发现对于 ((x_i,y_i))，做前 (k) 次 (s) 时都有贡献，从第 (t_i+1) 次 (s) 开始就一定没有贡献。则答案为 (sum_{i=0}^n min{t_i,K+[i = 0]})。

对于 (t_i)，把每一个 ((x_i,y_i)) 按照 ((x_i mod A,y_i mod A)) 分类，丢到对应的 set 里，每次在 set 里找即可。

(color{blue}igodot) | ABC225

考虑 (k=n) 的时候，就是对所有的 (s_i)，按照 (forall i<j,s_i+s_j<s_j+s_i) 排序。

传递性：

考虑把 (s_i,s_j) 看作 (26) 进制数 (a,b)，则 (s_i<s_j Longleftrightarrow a imes 26^{|s_j|}+b < b imes 26^{|s_i|} + a Longleftrightarrow dfrac a {26^{|s_i|}-1} < dfrac b {26^{|s_j|}-1})

可以发现这个不等式只和自己有关，容易证明其传递性。

然后倒过来 DP，设 (f(i,j)) 表示 (s_i,s_{i+1},cdots,s_n) 中选 (k) 个的最小字符串，容易证明这样做一定可以得到 按照顺序 选择得到的最小字符串。（可以证明正过来 DP 是错的）

考虑是否能不按照这个顺序得到更小字符串，可以证明这是与前面的排序矛盾的，所以无需考虑。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/kcn999/p/15512680.html