一轮省集

Day1, 2

模拟赛

fibonacci串

picture 0

$n=\vert t\vert\le 1. 5\times 10^5$

首先考虑不存在连续三个字符相同, 答案长度是 $O(n)$ 的. 再考虑超过 $\vert s\vert$ 超过答案长度后后面的都是重复, 所以合理的 $\vert s\vert$ 也是 $O(n)$ 的.

对斐波那契串这个递归结构应该想到建树, 对 $s_n$ 中间切一刀连向两个子节点, 树高是 $\log n$ 的, 于是像线段树一样任意一个区间可以拆成 $\log n$ 个完整的 $s_k$ 相拼

考虑枚举起点的话, 我们需要能 $\log n$ 找到对应终点, 也就是 $O(1)$ 跳一个完整的 $s_k$, 则预处理 $f_{i, j}$ 表示从 $t_j$ 开始完整匹配过一个 $s_i$ 能匹配多少即可.

复杂度 $n\log n$

水龙头

picture 1

$n\le 5\times 10^5$

考虑期望的线性性, 则期望值是每个水龙头被打开的概率和. 另外容易想到建图, 每个点向两个下方的点连边.

则一个点被打开当且仅当自己在所有前驱之前, 概率显然, 只要建图.

从下往上扫描线随便做吧!

多边形

picture 2

$n\le 5\times 10^5, a_i\le 50$

也就是对每个数求大于剩下所有数的概率. 注意不到 $x_i$ 和 $2^a_i-x_i$ 分布相同所以相当于所有数和超过 $x_i$ 的概率.

并且实数实在太难了, 考虑拆成 $x_i=y_i+z_i$, $y_i\in[0, 1], z_i\in [0, 2^{a_i}-1]\cap Z$, 对于实数的部分要求它大于 $k$ 的概率, 只能积分, 考虑:

$$
\begin{gathered}
\int^1_0\int^1_0\ldots \int^1_0[\sum_t z_t\le k]dz_1dz_2\ldots dz_n\
=\int\int\ldots \int[\sum_t z_t\le k]\prod_t ([z_t\ge 0]-[z_t\ge 1])dz_1dz_2\ldots dz_n\
=\sum_i (-1)^i \binom{n}{i} \dfrac{(k-i)^n}{n! }
\end{gathered}
$$

对于整数部分就很熟悉了, 如果直接求的话要卷 $(1-x^a_i)$ 复杂度是 $na\log^2 n$, 考虑因为所有数都是 $2^k-1$ 要求值的点都是 $2^k$, 可以拆位卷, 则复杂度变成 $na\log n$, 做完了.

[trick] 实数拆成小数部分和整数部分

[trick] 容斥积分/求和边界.

反转了

picture 5

$n\le 2\times 10^5, \vert a_i\vert \le 10^9$

显然对于某个前缀最优方案是反转负数前 $k$ 小, 容易发现最优前缀随 $k$ 递增, 于是分治决策单调性加数据结构支持单 $log$ 前 $k$ 大就做完了.

游戏

picture 8

$\vert S\vert \le 10^5, T\le 20$

考虑相当于一个括号串. 那么如果最后能成功 $k$ 轮, 取走 $4k$ 个括号, 发现Bob总是取最前最后的, 而Alice要取最好括号串是匹配的, 所以相当于只看最前的 $2k$ 个左括号和最后 $2k$ 个右括号组成的串, 看是否能全取完.

注意到这件事后剩下的容易了, 二分答案, 只要取成不匹配的括号串, 就要尽量减前缀和, Bob总是取最前最后的, 而Alice就要做到保证Bob取的时候总是只有一个根, 则统计每个点子树外的点个数和深度判断即可. 复杂度 $n\log n$

划分

picture 9

$n\le 10^6, k\le 60, x\le 2^k$

考虑大多数情况下自己一段是很优的.

如果 $X=0$, 显然段数就是非 $0$ 数个数, 简单题.

否则数分成 $0/X/\text{Other}$ 三类, 称非 $0, X$ 的数为好的.

则关注极长的不好的段, 此时只有两种分配方式: 第一个 $X$ 向左匹配一个好的数, 或者第一个 $X$ 向右匹配下一个 $X$, 若做前缀异或和, 分别对应了在所有前缀和为 $X$ 的位置断和在所有前缀和为 $0$ 的位置断.

类似 鸡 那个题, 拆贡献, 好的段的贡献直接算, 当它在前/后缀的时候直接算, 在中间时, 长 $l$ 的段的期望应该是先乘上这一段每个数都不好的概率, 然后直接考虑前缀和(也是每一位 $0/X$ 等概率), 考虑其中 $0/1$ 多的情况下的期望, 简单组合算即可.

复杂度线性.

课

ICPC Jinan 2023 B

picture 3

直接dp, $f_{u, i}$ 表示 $u$ 的子树分完, 包含 $u$ 的一块大小为 $i$ 的方案数, 转移就是直接卷加点单点改.

当 $k\le \sqrt n$ 复杂度显然 $nk$, 当 $k\ge \sqrt n$ 则一个子树只能分 $t\le n/k$ 个大小为 $k$ 的块, 此时 $i=(siz-t)\bmod (k+1)$, 所以本质不同只有 $\sqrt n$ 个, 复杂度也是 $n\sqrt n$.

ECFinal 2023 C

picture 4

todo

[ARC168E] Subsegments with Large Sums

显然直接wqs是没凸性的, 想到判定.

考虑把划分转成选出不交的 $x$ 段, 要求没选的位置个数不小于 $k-x$, 即选一段支付 $r-l$ 代价, 要求总代价小于 $n-k$, 此时容易直接wqs二分+dp了.

[trick] 把划分段, 每个段贡献 $0/1$ 变成选出有贡献的段.

[ABC311Ex] Many Illumination Plans

暴力dp肯定是 $f_{u, i, 0/1}$ 表示 $u$ 子树内, 重量是 $i$, 外面选的颜色是 $0/1$ 的最大权值, 复杂度是 $nX^2$ 的. 显然爆炸了. 不能出现背包合并.

考虑从上往下加点, 先只考虑求全局答案, 代码写出来是

picture 6

即我们带着dp数组往下走, 当遍历到 $u$ 时里面存储着dfs序在它之前的点和子树中的点的信息, 最后加入自己, 此时复杂度是 $X2^n$ 级别的, 因为重复访问了两次儿子.

考虑轻重剖分先遍历重儿子, 则它只被遍历了一次, 复杂度降为 $n^{\log_2 3}X$.

对于所有子树, 只要对每个重链分别跑, 复杂度不变.

CF1874F Jellyfish and OEIS

考虑对可能不合法的 $\sum_i m_i-i+1$ 个区间容斥, 发现如果钦点了两个相交区间 $l_1<l_2\le r_1< r_2$, 其和择 $[l_1, l_2-1], [l_2, r_1], [r_1+1, r_2]$ 的效果是一样的, 则可以构造双射, 若存在相交区间, 则切换 $[l_1, l_2-1]$ 是否存在即可系数相消.

现在只要考虑钦点完之后区间不交的情况, 则可以表示成树状(添加一个 $[1, n]$), 显然方案数是树上每个点不被子节点覆盖的位置数的阶乘再乘起来, 于是考虑dp: $f_{l, r}$ 表示以 $[l, r]$ 区间为根下带容斥系数的方案数, $g_{l, r, i}$ 表示根完全被 $[l, r]$ 的森林, 且森林外有 $i$ 个散点的方案数来辅助 $f$ 的转移, 则 $g_{l, r, i}\to g_{l, r+1, i+1}, g_{l, r, i}f_{r+1, r+k}\to g_{l, r+k, i}, g_{l, r, i}i! \to f_{l, r}$, 复杂度 $n^4$.

[trick] 构造双射容斥系数相消.

[AGC066D] A Independent Set

考虑最终的串, 一定是若干个 $AB$ 交替段加上若干个 $B$ 段, 在最后添加一个没有影响的 $B$ 可以使得交替串都是 $AB$ 重复得到. 同时容易发现 $B$ 串一定不参与交换.

则考虑dp, 设最小代价为 $f_i$, 则若 $[j, i]$ 中 $A, B$ 数量相等可以把它变成一个 $AB$ 交替串, 如果只有 $B$ 可以作为一个全 $B$ 串.

发现若 $[j, i]$ 可以拆成 $[j, k], [k, i]$ 分布满足 $AB$ 数量相等, 则这么转移没什么坏处, 于是转移其实是有 $O(n)$ 个的.

于是要计算 $w_{l, r}$ 表示把区间 $[l, r]$ 变成 $AB$ 交替的代价, 因为不存在某个位置使得其能拆分成两个, 所以对于任意不是本身的前缀都有 $A$ 的数量减 $B$ 的数量恒大于/小于 $0$, 可以说明所有的 $A$ 一定都往左/都往右跑, 于是前缀和简单计算.

复杂度线性.

[trick] 考虑最优串状态

[trick] 对转移拆分

CF1930G Prefix Max Set Counting

考虑重复走过一个点没有影响, 不妨让它可以重复随便走.

于是状态为 $f_u$ 表示走到 $u$ 且 $u$ 是走过的点中最大值的方案数, 每次若子树内有比自己大的点必须往下走, 否则向上走到第一个点满足其子树内有比 $u$ 大的再向下走. 直接dp, 则向下走的转移是子树加单点查.

但这样会算重, 因为对于从上到下的祖孙链 $u\to v\to w$, 从 $u$ 转移到 $w$ 和从 $v$ 转移到 $w$ 是重复的, 即我们要求向下走过一次的不允许接着往下转移. 也就是按照上面的走法, 第一次从根到某个点, 后面都是先上后下的转移.

Qoj5312 Icpc Hangzhou 2022 L. Levenshtein Distance

先考虑怎么求这个距离, $f_{i, j}$ 表示让 $s$ 前 $i$ 个和 $t$ 前 $j$ 个相同的最小代价, 可以转移, 复杂度 $30n$. 看一下各维度大小想到交换值域和状态, 于是 $f_{i, j}$ 表示用 $i$ 代价使得最大的 $p$ 满足 $s_{1\ldots p}=t_{1\ldots p+j}$, 此时状态是 $k^2$ 的, 而每次转移就是当前位置进行一个修改然后求两个后缀的lcp, 用SA可以 $O(1)$, 最后对每个后缀跑上面这个东西复杂度 $O(nk^2)$

PKUWC 2024 Day1 T2

picture 7

注意 $d$ 是不包含自身的.

一个比较显然的策略: 先找到最小值, 可以直接算出它的值, 然后给所有边同时减去最小值, 此时没有跨过最小值的贡献, 有了递归结构. 但不知道最小值所以考虑dp:

$f_{l, r, v}$ 表示区间 $[l, r]$ 整体减去 $v$ 是否可行, 转移要枚举最小值位置和值. 此时状态 $n^2V$ 复杂度 $n^3V^2$.

注意到若 $f_{l, r, v}$ 可行, 那么 $f_{l, r, v-k(r-l)}$ 一定可行(相当于每个元素加 $1$), 于是 $f_{l, r, v}$ 表示模 $r-l$ 意义下减去 $v$ 的话最大的 $v$, 同余最短路转移, 复杂度变成 $n^5$, 可以通过.

Qoj. 7905 Icpc Jinan 2023 L. Ticket to Ride

首先想到简单的dp: $f_{i, j}$ 表示只考虑前 $i$ 个线段, 涂红 $j$ 个的答案, 转移是要么 $f_{i, j}=f_{i-1, j}$, 要么 $f_{i, j}=f_{i-k-1, j-k}+w(i-k+1, i)$, $w(l, r)$ 表示被 $[l, r]$ 包含的区间的权值和, 现在的状态不太好, 转移时第二维会被影响, 不如第二维改成 $i-j$, 容易用线段树优化, 要求做到: 前缀加, 在最后单点改, 全局max.

那么真的用线段树吗? 要注意到操作的特殊性, 前面的若比后面的大后面的就没用了, 于是并查集维护所有前缀max, 每次前缀加的时候把后面的合并到前面即可. 复杂度 $nq\alpha(n)$.

P8294 [省选联考 2022] 最大权独立集问题

todo

UOJ840. 龙门考古

考虑如果已知不确定的位置怎么求 $b$, 则 $c_i=0$ 相当于没有限制, $c_i=1$ 相当于 $b_i\ge \max_{j\in [1, nxt_i-1]}$, 其中 $nxt_i$ 表示下一个 $c_k=1$ 的位置 $k$.

考虑对于 $c_i=0$ 的位置, 不可辨认的位置一定是递增的, 如果所有 $c_i=1$ 都是可辨认的则这是充要的.

对于 $c_i=1$ 的位置, 考虑其什么时候可以不可辨认, 此时一定有不存在不可辨认的位置 $j$, $j>i, b_j<b_i$ 且交换 $i, j$ 后符合限制, 设 $s_i$ 为 $[1, nxt_i-1]$ 的次大值, 即 $s_i\lt b_j\lt b_i, j\gt nxt_i$ 的 $j$ 必须可以辨认. 发现这个条件是充分的.

此时问题变成了每个 $c_i=0$ 的位置可以选择是否可辨认, 若所有满足 $b_j\in [s_i, b_i]$ 的 $j$ 都可以辨认则 $i$ 可以不可辨认(贡献 $\times 2$)(若 $b_j>s_i, i\ne j$, 则 $j>nxt_i$).

于是对 $c_i=0$ 的部分dp, 设 $f_i$ 表示以 $i$ 结尾的前缀, $i$ 可辨认的方案数, 则 $f_i2^{w(b_i, b_j)}\to f_j$ 当且仅当 $b_i<b_j$. 其中 $w(l, r)$ 表示有多少个区间 $[s_i, b_i]$ 被 $[l, r]$ 包含.

注意到 $[s_i, b_i]$ 互不包含, 用BIT优化到 $n\log n$

UOJ823. [UR #26]铁轨回收

用 $A_i’$ 表示原始 $A_i$, $A_i$ 表示当前 $A_i$.

考虑对 $B_n\le 4$ 的部分分可以直接从前往后dp, 记录数组 $c$ 表示后面被加了 $j$ 的数有 $c_j$ 个, 转移时考虑自己会是几, 再加到后面去(也就是把考虑自己是几的方案数这件事延迟到后面计算了).

考虑容斥, 把 $A_i=B_i$ 的位置容斥成总方案数减去 $A_i<B_i$ 的方案数计算.

于是设 $f_{i, S, j}$ 表示考虑后 $i$ 个点中, 需要被加的 $A$ 的集合为 $S$, 且有 $j$ 个点被钦定计算总方案数, 考虑第 $i$ 个点转移:

  • $i$ 被加到 $j$ 个点中, 则 $j\to j+1$.
  • $A_i=B_i$, 加上总方案数贡献, 则 $k\to k+1$, 并把 $S$ 中一个元素减去 $B_i$
  • $A_i=B_i$, 减去其他贡献, 则 $S$ 中一个元素减去 $B_i$, 加入一个 $t<B_i$ 的 $t-A_i’$
  • $A_i<B_i$ 加入一个 $A_i-A_i’$

重点是过程中 $S$ 的和单调不升, 一开始和为 $B$, 所以 $S$ 状态数是分拆数级别的, $i, j$ 是 $O(n)$ 的.

Day3

模拟赛

A

考虑对出边邻接矩阵 $M$, 定义矩阵 $A_{ij}=M_{ij}x^i$, 则 $\mathrm{tr} \dfrac{A^l}{l}$ 统计了所有长 $l$ 的环. 于是所有的环就是

$$
\mathrm{tr} \sum_i \dfrac{A^i}{i}
$$

我们进行容斥, 钦定一些环存在, 剩下的点随便连, 则要求没有偶环, 有 $k$ 个奇环的方案贡献 $2^k$, 则偶环容斥系数为 $-1$, 奇环系数为 $1$(这 $k$ 个奇环每个选/不选都贡献 $1$, 共 $2^k$ 种). 此时环的贡献应
该是

$$
\mathrm{tr}\sum_i \dfrac{A^i}{i}(-1)^{i+1}=\mathrm{tr}\ln (I+A)
$$

已知 $\exp \mathrm{tr}\ln M=\det M$ 下面类比矩阵树定理推导, 所求即为:

$$
\begin{gathered}
[x_1x_2\ldots x_n]\prod_i(1+deg_ix_i) \exp \mathrm{tr}\ln(I+A)\
=[x_1x_2\ldots x_n]\prod_i(1+deg_ix_i) \det(I+A)\
=[x_1x_2\ldots x_n]\det{((1+deg_ix_i)([i=j]+M_{i, j}x_i)){i, j}}\
=\det{([i=j]deg_i+M{i, j})_{i, j}}\
\end{gathered}
$$

B

注意到 $A=\begin{bmatrix}1&u\0&1\end{bmatrix}$ 和 $\begin{bmatrix}1&-u\0&1\end{bmatrix}$ 互为逆元, $v$ 的同理设为 $B$ 和 $B^{-1}$.

则猜测在去掉平凡的 $AA^{-1}BB^{-1}$ 这种情况之后, 也就是对操作序列 $M_1\ldots M_k$ 来说 $M_iM_{i+1}\ne I$ 的情况下, 不同的 $M$ 得到的结果不同.

如果这个是对的就很简单了, 可以看成是一个四元环形状的自动机上走, 数据范围一眼常系数线性递推, 推GF然后求就行了.

但是这个结论怎么证啊! 发现上面不同的 $M$ 得到的结果不同 等价于 有所有 $M$ 序列生成的矩阵组成的群 $G$ 是自由群, 或者说 $G$ 是 $A$ 和 $B$ 的自由积. 并有一个判定自由积的乒乓引理:设群 $G$ 作用在集合 $X$ 上, $H_1, H_2$ 是 $G$ 的非平凡子群, $H$ 是 $H_1, H_2$ 生成的群, 若 $X$ 有两个不交的非空子集 $X_1, X_2$ 使得 $\forall 1\ne a\in H_1, a(X_2)\subset X_1$ 且 $\forall 1\ne b\in H_2, b(X_1)\subset X_2$, 则有 $H$ 是 $H_1, H_2$ 的自由积. (看起来就像 $H_1, H_2$ 把元素从 $X_1, X_2$ 打到对面去, 所以乒乓)

然后解释一下(自己体会的), 自由群的概念是存在子群 $S$ 对所有元素有唯一的极简生成路径(就是去掉 $AA^{-1}$ 这种到不能去了). 自由积看起来就是以这两个元素为生成元生成循环群然后它是自由群.

则对于上面的问题, 把 $A, B$ 作用到 $1\times 2$ 向量 $[a, b]$ 得到 $[a, b+au]$ 和 $[a+bv, b]$, 发现只要让 $X_1, X_2$ 分别对应 ${[a, b]\vert a>b}$ 和 ${[a, b]\vert a<b}$ 即可证明.

C

恶心玩意

对于 $k=1$ 显然.

对 $k=2$, 若为左右结构就用 $k=1$ 的方法求前缀/后缀答案再枚举位置合并, 若为上下结构, 考虑建出笛卡尔树, 则一定是选择有祖先关系的两个点 $u, v$($u$ 是 $v$ 祖先), 设两个点的宽度高度(从底部开始)分别为 $w_u, h_u, w_v, h_v$, 则贡献是 $w_uh_u+w_vh_v-w_vh_u$, 一眼斜率优化形式, 于是用李超树合并维护决策从下往上即可.

对 $k=3$ 进行分类, 若为左中右结构又直接线性dp秒了.

若为凸口形(两个成上下, 合起来再成左右), 则也秒了.

若为上中下形, 考虑实际上 上 和 下 比较独立, 也就是做两遍即可.

最后剩下凹形, 考虑 $u$ 子树内两个不为祖孙的点 $x, y$, 最后的式子是 $h_uw_u+w_x(h_x-h_u)+w_y(h_y-h_u)$, 于是对于一组 $x, y$, 我们需要的信息是 $k=w_x+w_y$ 和 $b=w_xh_x+w_yh_y$, 然后求最大的 $kw_x+b+w_uh_u$, 也就是枚举 $u$ 之后单点求值, 发现求值直线只要保留 $(k, b)$ 为点的情况下凸包上的点(这个是半平面交于凸包对应关系), 而 $(k, b)$ 显然是 $(w_x, w_xh_x)$ 做闵和得到, 所以分别保留凸包再闵和, 可以把没有祖孙限制的做到线性.

加上限制之后考虑用dfs序表示为子树区间不交, 用线段树结构, 每个点维护 $L, R$ 两个集合, 则对区间 $[l, r]$ 找到线段树上 $r$ 点叶子到根的路径, 若某个点为右儿子则上面插入到集合 $R$ 中, 左边同理, 则自底向上合并 $L, R$ 即可. 每个点被插入 $n\log n$ 次, 总复杂度单log.

Day4

A

picture 10

$n\le 3\times 10^7$

考虑要尽量让累加的东西和 $n$ 无关, 再换下形式 $i=k-m$, 于是

$$
\sum_k^n \sum_i^k \binom{k}{i}\binom{i}{i/2}2^{n-i}
$$

然后我的思路是

$$
\begin{gathered}
=\sum_i \binom{i}{i/2}2^{n-i}\sum_k\binom{k}{i}\
=\sum_i \binom{i}{i/2}2^{n-i}\binom{n+1}{i+1}
\end{gathered}
$$

可以单独看 $i$ 是偶数/奇数再加起来, 这里对偶数, 并且对 $n$ 差分得到 $\binom{n+1}{i+1}-\binom{n}{i+1}=\binom{n}{i}$, 只要求 $\binom{i}{i/2}2^{n-i}\binom{n}{i}$ 累加

$$
\begin{gathered}
\binom{2i}{i}2^{n-2i}\binom{n}{2i}\
=x^n^n\dfrac{1}{\sqrt{1-4x}}
\end{gathered}
$$

奇数同理, $\binom{2i+1}{i}$ 的生成函数应该是 $\dfrac{\dfrac{1}{\sqrt{1-4x}}-1}{2x}$

于是显然微分有限, 求两次前缀和都是乘 $\dfrac{1}{1-x}$ 也微分有限. 然后直接跑高消可以出一个答案的二阶二次递推式.

但是感觉我们是闲的没事干才推这些, 实际上

$$
\binom{2i}{i}2^{n-2i}\binom{n+1}{2i+1}\
$$

是超几何级数吧!

复杂度线性.

但是题解更智慧, 注意到一开始我们不把 $k$ 换出来, 就要 $O(n)$ 的对所有 $k$ 求 $\sum_i^k \binom{k}{i}\binom{i}{i/2}2^{k-i}$, 然后这个居然组合意义一下等于 $\binom{2n+1}{n}$ /xia/xia/xia

B

picture 11

$n\le 3\times 10^5, M\le 200$

列一下生成函数发现二元要拆拉普拉斯变换做不了, 考虑dp.

于是设 $f_{i, j}$ 表示已经摸出来 $i$ 种球, 其中有 $j$ 种只出过一次, 有

$$
\begin{gathered}
f_{i, j}=\dfrac{i-j}{n}f_{i, j}+\dfrac{j+1}{n}f_{i, j+1}+\dfrac{n-(i-1)}{n}f_{i-1, j-1}\
f_{i, j}=\dfrac{n-i+1}{n-i+j}f_{i-1, j-1}+\dfrac{j+1}{n-i+j}f_{i, j+1}
\end{gathered}
$$
复杂度 $n^2+nm$

然后优化肯定是改成算期望而非概率, 但看到若干次考虑斯特林数拆成二项式, 现在设 $g_{i, m}$ 表示 $\sum_j f_{i, j}\binom{j}{m}$, 求递推式是 $nm$ 的. 做完了

C

picture 12

$n, Q\le 1. 5\times 10^5$, 3s

todo

Day7

模拟赛

A

picture 13

简单题, 容易确定出哪些点是 $C/D$, 直接染了, 剩下的二分图染色即可.

B

picture 14

$m\le n\le 100$ 你要保证操作次数少于 $n^3$

群论题.

相当于用一些循环位移置换构造 $p^{-1}q$, 则考虑位移偶数是一定偶置换, 奇数不一定, 又经过打表发现偶数能成一半奇数都行, 去猜结论.

开始构造, 对奇数构造相邻交换:

C

容易发现联通块数等于加边时两点都有边的边的数量, 于是容斥成钦定 $i$ 条比相邻的早, 剩下的无所谓的方案数. 这里容斥系数应该是 $(-1)^{i-k}f(n-2k, i-k)$, $f(a, b)$ 表示在 $a$ 个点的完全图中选 $b$ 个不相交的边的方案数. 这个 $f$ 看起来很显然.

然后计数的话, 这个直接想的话感觉限制是一个DAG做不了(要求与这 $i$ 条边有一个公共点的比它晚, 有两个公共点的比它俩都晚), 但容易发现这 $i$ 条边是对称的, 可以钦定它们之间的顺序, 于是有两个公共点的只要连到两条边中晚的一个, 变成一棵树, 可以做了.

总复杂度线性.