前言

其实是讲后补题笔记,所以会有些出入。

Day 1

AGC 039E Pairing Points

考虑和 $1$ 相连的点 $i$,则其他点跨过 $1\to i$ 这条线的必然互不相交。设 $f(l,r,i)$ 表示只考虑 $[l,r]$ 中的点,其中 $i$ 向区间外连边,其余点两两连边的方案数,则转移可以考虑枚举第一条跨过 $1\to i$ 的边 $j\to k$ 和与其相交的区间 $[l,x],[y,r]$,那么有:

$$ f(l, r, i) = \sum_{l\le j\le x < i < y\le k\le r, A_{j,k}=1} f(l, x, j) f(x+1,y-1,i) f(y,r,k) $$

稍微调换一下循环顺序,则可以得到:

$$ \sum_{l\le x < i < y\le r} f(x+1,y-1,i) \sum_{j\le x < y\le k, A_{j,k}=1} f(l, x, j) f(y, r, k) $$

后面那项只和 $l,r,x,y$ 有关,设:

$$ \begin{aligned} g(l,x,y,r) &= \sum_{j\le x < y\le k, A_{j,k}=1} f(l, x, j) f(y, r, k) \\ &= \sum_{j\le x} f(l,x,j)\sum_{y\le k,A_{j,k}=1} f(y,r,k) \end{aligned} $$

设 $h(y,r,j) = \sum_{y\le k,A_{j,k} = 1} f(y,r,k)$.

于是通通暴力算,然后复杂度就变成 $\mathcal O(n^5)$ 啦。

AGC 049D Convex Sequence

注意到相当于差分单调不降,考虑枚举第一个最小值的位置 $p$.

于是存在三个操作:选择一个 $i<p$,令 $A_i,A_{i-1},\cdots,A_1$ 分别加上 $1,2,\cdots,i$(差分前缀减),以及选择一个 $i>p$,令 $A_i, A_{i+1},\cdots,A_n$ 加上 $1,2,\cdots,i$(差分后缀加),以及全局 $+1$.

注意到操作 $1$ 必然对 $p-1$ 位置做一次(否则就不是第一个最小值),故 $p$ 只有 $\mathcal O(\sqrt m)$ 种可能取值,然后之后的操作只有 $\mathcal O(\sqrt m)$ 种,所以可以直接做完全背包。

换最小值的位置时只有 $\mathcal O(1)$ 个物品改变,总的时间复杂度可以做到 $\mathcal O(m\sqrt m)$.

ARC 101F Robots and Exits

显然一个机器人只可能到其左右两边最近的出口(对于两边的只有一个可能出口的机器人可以忽略)。

记它到左边的距离为 $a_i$,到右边的距离为 $b_i$,把机器人抽象成点 $(a_i - 0.5,b_i - 0.5)$,则我们相当于画一条折线代表向左移动距离和向右移动距离的历史最大值的变化,那么若某次折线穿过 $x=x_i$ 或 $y=y_i$ 则代表一个机器人到了一个出口。

那么折线上方的就是到了左边的出口,而折线下方就是到了右边的出口。

考虑若某个点被选取了,则其右下角的所有点显然不会再被选取了,于是按 $a_i$ 排序后实际上就是一个上升子序列计数,容易做到 $\mathcal O(n\log n)$.

AGC 046D Secret Passage

显然,若我们有一个合法的最终串 $T$,使得 $S$ 有一个最长的后缀 $S'$ 是 $T$ 的子序列,则存在一个方案使得我们不需要对 $S'$ 作任何修改。

设 $f(i,j,k)$ 表示 $\operatorname{suf}(S,i)$ 插入 $j$ 个 $0$、$k$ 个 $1$ 能得到的不同的字符串的个数。

为了避免重复计算,我们要求 $S'$ 必须是 $T$ 的第一个子序列,那么 $S_x',S_{x+1}'$ 之间就插入的数就必须与 $S_{x+1}'$ 不同。

同时,我们也不能插入某个数,使得 $T$ 存在一个更长的 $S$ 的后缀作为子序列。

然后我们可以容易写出 $f(i,j,k)$ 的转移方程,再设 $g(i,j,k)$ 表示 $\operatorname{pre}(S,i)$ 是否可以拿出 $j$ 个 $0$、$k$ 个 $1$,暴力转移即可做到 $\mathcal O(n^3)$.

AGC 041D Problem Scores

(参考了洛谷上的题解)

显然条件满足的充要条件是是取尽可能大、且不重合的大小分别为 $k+1$,$k$ 的前后缀满足条件(即 $k = \lfloor (n-1)/2\rfloor$)。

前两个条件相当于:给定一个初始全为 $n$ 的序列 $A_i$,每次选择一个前缀减一。显然若设每个前缀被减一的次数 $k_i$,$\{k_i\}$ 和合法序列一一对应。

再记 $x$ 表示前 $k + 1$ 个数与后 $k$ 个数之差,则每个操作造成的 $\Delta x = -1,-2,\cdots,-k,-k-1,-k,\cdots,-2,-1$。

做个背包就好了,$\mathcal O(n^2)$.

AGC 024F Simple Subsequence Problem

我们将对每个可能的 $t$ 求出其为 $S$ 中多少个串的子序列。

直接暴力是 $\mathcal O(4^nn)$ 的,我们考虑匹配过程中实际上我们只关心剩下还未匹配的串长什么样,而不关心已经匹配的串长什么样,于是设:$f(t_p,s_s)$ 表示已经确定了 $t$ 的前若干位 $t_p$,$s$ 还剩下后缀 $s_s$ 未匹配的 $s$ 的个数。转移时枚举 $t_p$ 的下一个位置是 $0/1$,或者直接停止匹配(把 $s_s$ 变为空串 $\varepsilon$)。

注意到 $|t_p| + |s_s| \le n$,所以总共有 $2^nn$ 个状态(还需压一个分界线)。每次转移是 $\mathcal O(1)$ 的,所以总的时间复杂度是 $\mathcal O(2^nn)$ 的.

AGC 040E Prefix Suffix Addition

容易通过在序列前后加 $0$ 的方式变为区间加单增 / 单减的序列,假如我们能确定最后每个位置加的是 $A_i=b_i+c_i$($b_i$ 为操作 $1$ 加上的,$c_i$ 为操作 $2$ 加上的),那么显然所需要的最少操作次数为(不妨令 $x_0=x_{n+1} = 0$):

$$ \sum_{i=1}^n ([b_i>b_{i+1}]+[c_i<c_{i+1}]) $$

设 $f(i,j)$ 表示考虑了前 $i$ 个数,$b_i=j$ 时,$\sum_{k=1}^{i-1} ([b_k>b_{k+1}]+[c_k<c_{k+1}])$ 的最小值。

我们可以发现两个性质:

  • $i$ 固定时,$f(i,j)$ 随 $j$ 增大单调不升:显然 $b_i$ 增大则 $c_i$ 减小,那么 $[b_{i-1} > b_i]$ 和 $[c_{i-1} < c_i]$ 就更不可能为真(显然 $i-1$ 前面部分的贡献是每个 $j$ 都一样的)。
  • $i$ 固定时,$f(i,j)$ 的极差不超过 $2$。由代价定义显然。

于是可以把 dp 值分三段去维护,具体而言,转移的时候拿每段 $j$ 最小点去转移(这样显然是最优的),先求出 $f(i+1,0)$,然后再找分界线就好了。

然后就做完了,$\mathcal O(n)$.

ARC 108E Random IS

设 $f(i,j)$ 表示区间 $[i,j]$ 已经被标记了,只考虑该区间内部的期望是多少,显然有:

$$ f(i,j) = 1+\dfrac 1{{\rm cnt}_{i,j}} \sum_{k\in(i,j),a_k\in(a_i,a_j)} [f(i,k-1)+f(k+1,j)] $$

其中 ${\rm cnt}_{i,j}$ 表示 $(i,j)$ 中合法的 $k$ 的数量,容易在 $\mathcal O(n^2\log n)$ 时间内求得。

注意到 $\sum f(i,k-1)$ 和 $\sum f(k+1,j)$ 互不影响,所以我们可以分开统计。对于前者,我们考虑建立 $n$ 棵线段树,第 $i$ 棵的下标 $j$ 维护以 $i$ 为左端点,而右端点 $r$ 满足 $a_{r+1} = j$ 的 dp 值之和。转移较为容易,而后者同理。所以总的时间复杂度也是 $\mathcal O(n^2\log n)$.

AGC 033D Complexity

待补。

CF 585F Digits of Number Pi

待补。

AGC 022E Median Replace

待补。

Day 2

FJOI 2018 城市路径问题

题意简述:$n$ 个城市,第 $i$ 个城市有 $2k$ 个点权 $(a_{i,1},\cdots,a_{i,k},b_{i,1},\cdots,b_{i,k})$,$u$ 到 $v$ 的方案数为 $\sum_{i=1}^k a_{u,i}b_{v,i}$($u$ 可以等于 $v$),$m$ 次询问 $u$ 在 $d$ 步以内到达城市 $v$ 的方案数。($n\le 10^3$,$d<2^{31}$)($k\le 20,m\le 50$ 或 $k=1,m=100$)

设邻接矩阵 $C$,则我们就要求 $I_n+C+C^2+\cdots+C^d$($I_n$ 即 $n$ 阶单位矩阵)第 $u$ 行第 $v$ 列的值,直接倍增则单次询问的复杂度是 $\mathcal O(n^3\log d)$

注意到 $C = AB^{\mathsf T}$,则原式等于:

$$ I_n + A[I_n+B^{\mathsf T}A+\cdots + (B^{\mathsf T}A)^{d-1}] B^{\mathsf T} $$

而 $B^{\mathsf T}A$ 是 $k$ 阶方阵,所以单次询问的复杂度就可以做到 $\mathcal O(nk+k^3\log d)$ 了。

CF 1336E1 Chiori and Doll Picking (easy version)

把 $a_i$ 看成 $\mathbf F_2$ 上的 $m$ 维向量,求出 $V = \mathrm {span}(a_1,\cdots,a_n)$ 的一组基(记 $\dim V = k$),则 $V$ 中的每个向量都有 $2^{n-k}$ 种表示方法,在基上做原问题,然后对答案乘 $2^{n-k}$ 即可。

在 $k$ 较小时直接暴搜就好了,时间复杂度 $\mathcal O(2^k)$.

在 $k$ 较大时,考虑消成行最简形式(即所有自由的位上有且仅有一个基为 $1$),不妨设只有一个 $1$ 的列为主元。

设 $f(i,j,S)$ 表示考虑了前 $i$ 个数,主元选取了 $j$ 个,非主元的状态为 $S$ 的方案数,则为 $1$ 的位数自然是 $j+\operatorname{popcount}(S)$.

大力 dp 就好了,时间复杂度 $\mathcal O(m^22^{m-k})$.

总的时间复杂度大概是 $\mathcal O\left(m2^{\frac m2}\right)$.

LOJ 6247 九个太阳

首先我们有单位根反演:

$$ [k\mid n] = \dfrac 1k\sum_{i=0}^{k-1}\omega_k^{in} $$

所以原式为:

$$ \sum_{i=0}^n [k\mid i]{n\choose i} = \dfrac 1k\sum_{i=0}^n\sum_{j=0}^{k-1}\omega_k^{ji}{n\choose i} = \dfrac 1k\sum_{j=0}^{k-1}(1+\omega_k^j)^n $$

注意到 $k=2^t(t\le 20)$ 且模数为 $998244353$,所以模意义下 $\omega_k$ 总存在,暴力算就好了。时间复杂度 $\mathcal O(k\log n)$.

CF 933D A Creative Cutout

由题意,相当于求:

$$ \begin{aligned} & \sum_{n=1}^m\sum_{x^2+y^2\le n}\sum_{i=x^2+y^2}^ni \\ = & \sum_{x^2+y^2\le m}\sum_{i=x^2+y^2}^mi\sum_{n=i}^m 1 \\ = & \sum_{x^2+y^2\le m}\sum_{i=x^2+y^2}^mi(m-i+1) \end{aligned} $$

由于 $m$ 是常数,所以 $\sum_{i=x^2+y^2}^mi(m-i+1)$ 是关于 $x^2+y^2$ 的三次多项式 $P(x^2+y^2)$,可以通过插值或手算求得系数。

则原式可以看成:

$$ \sum_{x^2+y^2\le m} P(x^2+y^2) = \sum_{|x|\le \lfloor\sqrt m\rfloor} \sum_{|y|\le \lfloor \sqrt {m-x^2}\rfloor} P(x^2+y^2) $$

把 $x$ 看成常数,则 $\sum_{y\le \lfloor \sqrt {m-x^2}\rfloor} P(x^2+y^2)$ 为关于 $\lfloor \sqrt {m-x^2}\rfloor$ 的七次多项式 $Q_x(\lfloor \sqrt {m-x^2}\rfloor)$,于是考虑枚举 $x$,然后插值求出 $Q_x$,再带入求值即可。

时间复杂度 $\mathcal O(\sqrt m)$.

NOI 2019 斗主地

待补。

AGC 020F Arcs on a Circle

待补。

NOI 2020 机器人

待补。

LOJ 508 失控的未来交通工具

待补。

Day 3

待补。

Day 4

IOI 2019 景点划分

不妨设 $a\le b\le c$,则 $a\le \lfloor n/3\rfloor$,$b\le \lfloor n / 2\rfloor$,显然我们应该构造 $A,B$ 连通。

考虑树的情况,我们需要找到一个子树,根为 $u$,满足 $a\le s_u\le n-b$ 或 $b\le s_u\le n-a$($s$ 表示子树大小),然后就可以通过删叶子来得到大小恰为 $a,b$ 的连通块了。如果没有这样的子树,那么无解。

对于图的情况,我们考虑其的一个 DFS 树,对其进行上述的操作,若找不到这样一棵子树,则考虑其重心 $u$,由重心的性质,与其相连的所有子树大小不超过 $n/2$,但又无法通过上述的判断,所以又不满足 $\ge a$,即与其相连的所有子树 $s_v\le a$.

考虑将重心父亲(注意 DFS 树是有根的)的那个子树拿出来,放入集合 $B$,而重心所在子树放入集合 $A$。注意到:

  • 由于重心的所有子树大小都严格小于 $a$,所以重心必然在 $A$ 集合当中。
  • DFS 树是只有返祖边的,所以重心所在的子树中不会互相连边。

于是我们需要利用返祖边不断给 $B$ 加子树,显然,若所有返祖边都加完了,还不满足条件,那么一定无解,否则我们可以证明一定有解:

  • 我们断言,不存在某一时刻 $|A| \ge a,|B| < b$ 在连接一个返祖边后 $|A'|=|A| - s_x< a,|B'| = |B| + s_x \ge b$.
  • 考虑反证法,若存在这样的一个时刻,注意到 $|B|<b$,$|A|-s_x<a$,两式相加得到 $|A|+|B|<a+b+s_x=n$,与 $|A|+|B|=n$ 矛盾,故原命题得证。

于是我们就得到了一个 $\mathcal O(n+m)$ 的做法了。

Day 5~7

咕咕咕

最后修改:2021 年 07 月 21 日 11 : 11 AM