CF710(EDU16) 题解 / 二进制分组优化 AC 自动机学习笔记

zrl123456 · 2025-09-07 17:53:48 · 题解

:::::info[闲话] 不要问为啥直接从 13 到 16 了。
:::::

A. King Moves：

:::::info[题目基本信息] 考察：字符串（800）。
题目简介：
在一个 8\times 8 的棋盘上放置了一个国际象棋中的王，它能向上、下、左、右、左上、左下、右上、右下的相邻格移动（不能移出棋盘），问王能到达几格。
数据范围：
这种题有什么数据范围…… ::::: 容易发现，王如果在角上能到达 3 格，在边缘能到达 5 格，否则能到达 8 格。
时空复杂度均为 \Theta(1)。

B.Optimal Point on a Line：

:::::info[题目基本信息] 考察：数学（1400）。
题目简介：
给定 \{a_n\}，求所有的整数 x 中顺序最小的 x。顺序的关键字是：

1. 第一关键字是 \displaystyle\sum_{i=1}^n|a_i-x|，升序。
2. 第二关键字是 x，升序。

数据范围：

• 1\le n\le 3\times 10^5
• \forall i\in[1,n],-10^9\le a_i\le 10^9

  ::::: 先对 \{a_n\} 排序。
  那么结论就是：\displaystyle x=a_{\lfloor\frac{n}{2}\rfloor}。 :::::success[几何证明结论] 画个数轴出来手玩一下即可。
  吊打下面的代数。
  ::::: :::::success[代数证明结论] 设 \displaystyle p=\sum_{i=1}^n[a_i\le x]。
  那么：

  \begin{aligned}\sum_{i=1}^n|x-a_i|&=(\sum_{i=1}^px-a_i)+(\sum_{i=p+1}^na_i-x)\\&=px-(\sum_{i=1}^pa_i)+(\sum_{i=p+1}^na_i)-(n-p)x\\&=(2p-n)x+(\sum_{i=p+1}^na_i)-(\sum_{i=1}^pa_i)\end{aligned}

  接下来，分类讨论：

• 这是一个一次函数，由于 $\displaystyle p>\frac{n}{2}$，那么 $2p-n>0$，同时由于 $p$ 是整数也容易证出 $2p-n\ge 1$。 $$\begin{aligned}\sum_{i=1}^n|x-a_i|&=(2p-n)x+(\sum_{i=p+1}^na_i)-(\sum_{i=1}^pa_i)\\&=(2p-n-1)x+(\sum_{i=p+1}^na_i)-(\sum_{i=1}^{p-1}a_i)\end{aligned}$$ 容易发现 $2p-n-1\ge 0$，那么第一关键字随 $x$ 的增加而增加，所以 $x=a_p$。 那么现在 $x$ 随 $p$ 的增加而不递减，$(2p-n-1)x$ 也单调不递减，所以 $p$ 取最小，那么 $\displaystyle x=a_{\lfloor\frac{n}{2}\rfloor+1}$。
• 首先 $2\mid n$。 容易发现 $2p-n=0$，那么 $\displaystyle x\in[a_{\frac{n}{2}},a_{\frac{n}{2}+1})$ 都可取最小，所以 $\displaystyle x=a_{\frac{n}{2}}$（同时 $\displaystyle a_{\frac{n}{2}}\ne a_{\frac{n}{2}+1}$）。
• 同 $p>\frac{n}{2}$，不过 $2p-n\le -1$ 了，最后 $p$ 取最大，最终 $\displaystyle x=a_{\lceil\frac{n}{2}\rceil-1}$。

分类讨论结束，接下来整理答案：

• 有三个答案 $\displaystyle x=a_{\frac{n}{2}-1}$ 和 $\displaystyle x=a_{\frac{n}{2}+1}$ 还有 $\displaystyle x=a_{\frac{n}{2}}$，继续分讨： - $\displaystyle a_{\frac{n}{2}+1}\ne a_{\frac{n}{2}}$： 带入发现取 $\displaystyle x=a_{\frac{n}{2}}$ 时第一关键字最小。 - $\displaystyle a_{\frac{n}{2}+1}=a_{\frac{n}{2}}$： 带入发现 $\displaystyle x=a_{\frac{n}{2}+1}$ 时在哪种情况均不劣，由于前提条件所以结果同上。
• 两个答案 $\displaystyle x=a_{\lfloor\frac{n}{2}\rfloor}$ 和 $\displaystyle x=a_{\lceil\frac{n}{2}\rceil}$，显然前者不劣。

容易发现，最后答案就是 \displaystyle x=a_{\lfloor\frac{n}{2}\rfloor}。
证毕。
::::: 时间复杂度为 \Theta(n\log n)，空间复杂度为 \Theta(n)。

C. Magic Odd Square：

:::::info[题目基本信息] 考察：构造（1500）。
题目简介：
请你构造一个 n\times n 的矩阵 a_{i,j}，满足：

• \displaystyle\forall i\in[1,n],2\nmid \sum_{j=1}^na_{i,j}
• \displaystyle\forall j\in[1,n],2\nmid \sum_{i=1}^na_{i,j}
• \displaystyle2\nmid \sum_{i=1}^na_{i,i}
• \displaystyle2\nmid \sum_{i=1}^na_{i,n-i+1}
• \forall i1,j1,i2,j2\in[1,n],i1\ne i2\lor j1\ne j2,a_{i1,j1}\ne a_{i2,j2}
• \forall i,j\in[1,n],1\le a_{i,j}\le n^2

数据范围：

• 1\le n\le 49
• 2\nmid n

  ::::: 构造题最有效的方法是观察样例。
  容易发现，每行每列每个对角线的奇偶性只与每个数的奇偶性有关，那么我们看一下样例二中答案矩阵的奇偶性：

  \begin{bmatrix}0&1&0\\1&1&1\\0&1&0\end{bmatrix}

  容易发现这个矩阵的性质，我们扩大到 5\times 5 看看：

  \begin{bmatrix}0&0&1&0&0\\0&1&1&1&0\\1&1&1&1&1\\0&1&1&1&0\\0&0&1&0&0\end{bmatrix}

  容易发现，这个矩阵也符合奇数个数要求和行列对角线和为奇的要求，所以我们模拟即可。
  :::::success[证明] 行列对角线和为奇显然。
  那么对于奇数个数要求，我们需要证明：

  \sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}2i+1+\sum_{i=2}^{\lfloor\frac{n}{2}\rfloor}2i-1=\frac{n^2+1}{2}

  对前式变形：

  }{2}\\&=\frac{n^2+n-n+1}{2}\\&=\frac{n^2+1}{2}\end{aligned}

  证毕。
  ::::: 时空复杂度均为 \Theta(n^2)。

  D. Two Arithmetic Progressions：

  :::::info[题目基本信息] 考察：exgcd（2500）。
  题目简介：
  求满足下列条件的整数 x 的个数：

• L\le x\le R
• \exist k\in\mathbb N,x=a_1k+b_1
• \exist l\in\mathbb N,x=a_2l+b_2

数据范围：

• 0<a_1,a_2\le 2\times 10^9
• -2\times 10^9\le b_1,b_2,L,R\le 2\times 10^9

  ::::: 联立两个式子 x=a_1k+b_1 和 x=a_2l+b_2 得：

  a_1k+b_1=a_2l+b_2\\\Leftrightarrow a_1k-a_2l=b_2-b_1

  这是一个二元一次不定方程，有解的充要条件是 \gcd(a_1,a_2)\mid b_2-b_1，利用 exgcd 求解即可。
  设解出来的解 k,l 为 x,y。
  那么我们现在要求 k,l 的范围，以 k 举例：

  L\le x\le R\\\Leftrightarrow L\le a_1k'+b_1\le R\\\Leftrightarrow L-b_1\le a_1k\le R-b_1\\\Leftrightarrow\lceil\frac{L-b_1}{a_1}\rceil\le k\le\lfloor\frac{R-b_1}{a_1}\rfloor\\\Leftrightarrow k\in[\lceil\frac{L-b_1}{a_1}\rceil,\lfloor\frac{R-b_1}{a_1}\rfloor]

  与 \mathbb N 取交集得：

  k\in[\lceil\frac{L-b_1}{a_1}\rceil,\lfloor\frac{R-b_1}{a_1}\rfloor]\cap\mathbb N

  那么，可能的 k 的个数为：

  \lfloor\frac{\lfloor\frac{r-b_1}{a_1}\rfloor-x}{b}\rfloor-\lceil\frac{\max(\lceil\frac{l-b_1}{a_1}\rceil,0)-x}{b}\rceil+1 时间复杂度为 $\Theta(\log V)$，空间复杂度为 $\Theta(1)$。 #### [E. Generate a String](https://www.luogu.com.cn/problem/CF710E)： :::::info[题目基本信息] 考察：dp（$2000$）。 题目简介： 你需要生成一个长度为 $n$ 的全 `a` 字符串，有两种操作： 1. 添加或删除一个字符，代价为 $x$。 2. 将原有字符串复制并粘贴一次，代价为 $y$。

求最小代价。
数据范围：

• 1\le n\le 10^7
• 1\le x,y\le 10^9

  ::::: 显然要设 f_i 为字符串长度为 i 时的最小代价，接下来分类讨论：

• 写出朴素的转移方程： $$f_i=\min(f_{i-1}+x,f_{i+1}+x,f_{\frac{i}{2}}+y)$$ 但是这样会有后效性，我们考虑消去 $f_{i+1}+x$： - 进行 $1$ 次删操作： 下一步操作只能是加，显然抵消了。 - 进行 $2$ 次及以上删操作： 显然下一步如果是加就又抵消了，下一步只能是翻倍，显然比先删再翻倍劣了。 所以我们成功消去了 $f_{i+1}+x$，转移方程变为了： $$f_i=\min(f_{i-1}+x,f_{\frac{i}{2}}+y)$$
• 同样写出朴素方程： $$f_i=\min(f_{i-1}+x,f_{i+1}+x)$$ 同样考虑消去 $f_{i+1}+x$。 注意到由于下一步操作只能是翻倍，也就是说会进行奇数次删操作，同时由于进行 $2$ 次及以上删操作显然比先删再翻倍劣了，所以只能进行 $1$ 次删操作。 方程为： $$f_i=\min(f_{i-1}+x,f_{\frac{i+1}{2}}+x+y)$$ 注意到 $i=1$ 时仍然有后效性，所以要特判。

综上，转移方程为：

时空复杂度均为 \Theta(n)。

F. String Set Queries：

:::::info[题目基本信息] 考察：AC 自动机（2400）。
题目简介：
维护一个字符串集合，有 3 种 n 个操作：

1. 加字符串 s。
2. 删字符串 s。
3. 查询集合中的所有字符串在给出的字符串 s 中出现的总次数。

强制在线。
数据范围：

• 1\le m\le 3\times 10^5
• \sum|s|\le 3\times 10^5

  ::::: 容易发现，普通的 AC 自动机是离线的，所以我们要二进制优化 AC 自动机。 :::::success[功能详解] 二进制优化 AC 自动机在插入一个字符串时就给它单独开一个 AC 自动机，但是这样就会退化成暴力复杂度。
  所以对于相同大小都为 siz 的 AC 自动机我们要对其进行合并，合并时间复杂度为 \Theta(siz) 的，这样保证了 AC 自动机数量不超 \Theta(\log n) 个，同时合并总时间复杂度为 \Theta(n\log n) 的，可以接受。
  ::::: 然后注意到这道题有加也有删，不妨开两个 AC 自动机分别维护加和删。
  时间复杂度为 \Theta(n\log n|\sum|+\sum|s||\sum|)，空间复杂度为 \Theta(\sum|s||\sum|)。