CF EDU 169

A

• 题意：

  一条线上给定 n 个点，询问是否能新插入一个点，使得这个点是距离这 n 个点都是最近的

• 题解：

  $n>2$ 时，无解

  $n=2$ 时，直接插入到这两个点中间即可

B

• 题意：

  总共 $n$ 个房间，第 $i$ 个房间与第 $i+1$ 个房间中间有一扇门，假如 $A$ 可能在 $[l,r]$ 中任意一个房间， $B$ 在 $[L,R]$ 中任意一个房间，最少需要关闭几扇门才能保证两人不可能见面

• 题解：

  如果两人所在区间不相交的话，关闭 1 扇门即可

  如果两人可能所在区间相交的话，相交区间的所有门必须关闭，最后判断一下边界即可

C

• 题意：

  Alice 和 Bob 取数字，Alice 先手，Alice 取到的数字和为 A，Bob 取到的数字和为 B，Alice 想最大化 A-B，Bob 想最小化 A-B，在游戏开始前 Bob 可以增大任意数字，但是总增加量不能超过 k，求 A-B 的最小值

• 题解：

  每个人都尽量取剩下的最大的数字

  将数组排序，模拟取数字的过程，将最后结果减去 k 即可

  当有偶数个数字的时候，A-B 的最小值不会小于 0，奇数个数字的时候，A-B 的最小值不会小于原先所有数字的最小值

D

• 题意：
  总共有四种颜色的门，每个城市会有两扇不同颜色的门，其中城市 i 和 j 如果具有相同颜色的门，他们之间是互相可以到达的，所花费的价值是 $|i-j|$，每次询问城市 $x$ 去 $y$ 所花费的最小花费是多少

• 题解：

  若 $x$ 和 $y$ 具有相同颜色的门，最小花费就是 $|x-y|$

  否则枚举所有与 $x$ 和 $y$ 不一样的情况，找到 $x$ 右边第一个满足条件的门和 $y$ 左边第一个满足条件的门，直接处理即可

• code

E

• 题意：

  取石子游戏，若一堆石子有 x 个，只能从中取出 y 个，其中 gcd(x, y) 必须等于 1。给定多堆石子，第 i 堆有 $a_i$ 个石子，问先手和后手谁能赢

• 题解：

  SG函数

  考虑处理出来每个 $a_i$ 的 $\mathrm{SG}$ 值。

  考虑 $\mathrm{S}{\mathrm{G}}_{\mathrm{i}}$，若 $i$ 是质数，可以取任意 $[1,i-1]$ 个石子，所以 S G i = m a x { S G j } + 1 SG_i=max\{SG_j\}+1 SGi​=max{SGj​}+1

  若 $i$ 不是质数，对于 $i$ 的最小质因数 $p$，$p$ 的所有倍数都取不到，因此 $S{G}_i=S{G}_p+1$

  之后直接用 $\mathrm{SG}$ 定理即可

F

• 题意：

  给定一个数组 A，每次可以进行一下两种操作

  1. 用 $A_i+A_{i+1}$ 替换 $A_i$ 和 $A_{i+1}$
  2. 将 $A_i$ 拆成两个数字的和并替换掉 $A_i$

  $f(A)$ 表示让 $A$ 数组变成回文数组的最小次数，求 $\sum _{1\le l\le r\le n}(A[l:r])$

• 题解：

  对于一个长度为 $n$ 的数组，最坏情况是用 $n-1$ 次操作将其变成回文

  但是对于某一个数组 $A$，取其一个前缀和一个后缀，若这两个子段和相等，可以减少一次操作

  令 $f_{l,r}$ 表示 $A[l:r]$ 的最少操作次数，考虑 dp，最优情况一定是：

  f l , r = min ⁡ { f L , R + ( L − l ) + ( r − R ) } f_{l,r}=\min\{f_{L,R}+(L-l)+(r-R)\} fl,r​=min{fL,R​+(L−l)+(r−R)}

  也就是 f l , r + l − r = min ⁡ { f L , R + L − R } f_{l,r}+l-r=\min\{f_{L,R}+L-R\} fl,r​+l−r=min{fL,R​+L−R}

  其中 $\sum _{i=L}^l{A}_i=\sum _{i=R}^r{A}_i$

  对 $A$ 做前缀和 $sum$，转移条件变为：

  $su{m}_l-su{m}_{L-1}=su{m}_r-su{m}_{R-1}$，

  也就是 $su{m}_r-su{m}_l=su{m}_{R-1}-su{m}_{L-1}$

  开一个桶 $D$，有 $f_{l,r}+l-r=D[su{m}_r-su{m}_l]$，每次转移完 $f_{l,r}$ 后，更新 $D[su{m}_{r-1}-su{m}_{l-1}]$ 即可

• code

G

• 题意：

  给定一个又数字组成的字符串 $s$，可以将其划分乘偶数个非空子串 $s_i$，会以一下规则构成新字符串 $t$：

  • 依次对于每个 $j\le \frac{i}{2}$，将 $s_{2\times j}$ 个 $s_{2\times j-1}$ 拼接到 $t$ 后面（$s_i$ 下标从 $1$ 开始）

  给定 $n$ 和 $k$，对于 $s$ 中每个长度为 $k$ 的字串，求出其以上述方法生成的 $t$ 的最小长度

• 题解：

  单独考虑一个字串 $s$，发现划分后所有的 $s_{2\times j-1}$ 的长度一定为 $1$

  令 $f_{i,j}$ 表示考虑到第 $i$ 位，现在所填写的子串要重复 $j$ 次，这种情况的最小长度，有

  $f_{i,j}=f_{i-1,j}+j$

  f i , s i − 1 = min ⁡ { f i , s i − 1 , f i − 2 , k + s i − 1 } f_{i, s_{i-1}} = \min\{f_{i,s_{i-1}},f_{i-2,k}+s_{i-1}\} fi,si−1​​=min{fi,si−1​​,fi−2,k​+si−1​}

  考虑广义矩阵乘法，令 $f_{i,10}$ 表示考虑到第 $i$ 位，并且要更新 $j$ 的值（也就是上面转移的第二种情况）

  因为要求多个子数组的答案，直接双指针就行

• code