前言

警示后人

由于 BCOI 功能的漏洞 在写 blog 退出时不能保存。导致我本来写了一小时的东西全都没了。

所以写 blog 一定要及时保存。

去了本部集训才知道 dxd 一小时讲 5 道选择题是多珍贵。

这里没有对集训内容的总结

这里集训真是越来越水了。一点新的内容都没有讲。

硬要说的话，一堆模拟赛和杂题可以提供经验。

Day 0

7:00 整理宿舍内务。8:30 在机房集合，收电子设备。

---

以下内容提醒：

1. 不是我想写这么短的，是 FSJ 讲的本来就这么短。
2. 原题和链接并不一定完全一样，差不多。
3. 不要看这些题目标题，是我乱写的。

Day 1

上午模拟赛，下午讲题。

1. 天使之城。这是一道栈的语法题。T1 都没做出来是连语法都没学完吗？
2. $x$ 通过 $+1$、$-1$、$\times2$ 变成 $y$ 的最小次数。这是一道记忆化搜索。但当时我写了一个双向 BFS 超时了。
3. 打赌。这是一道模拟，还要通过 % 运算来优化。
4. 路标设置。这是二分。注意若指数为 $50$，在 $[0,100]$ 区间应该是 $1$ 个而不是 $2$ 个。
5. 关灯。线段树模板。
6. 交换地砖。这是动态规划。定义 $dp_{i,j}$ 表示用 $i$ 块地砖拼成面积 $j$ 的最小代价。通过将 $a+i$ 换成 $k$ 转移。

Day 2

做和讲了一些杂题。FSJ 讲题真好，每道题都控制在 $3\min$ 以内。

1. awa 的海报。语法题。
2. 幻想大战猪（？）。这题竟然只有入门！？？枚举每一个子串的中心，向两边拓展。直到两边不一样。虽然我是用记忆化搜索过的。
3. 给你一个 $N$ 行 $M$ 列的字符矩形，其中不是 $\texttt{.}$ 就是 $\texttt{\#}$。现在你可以任选行与列，将其去掉，使得剩下的行列中，包括的 $\texttt{\#}$ 有且只有 $K$ 个，求有多少种不同的选择方式。这题是个状压，但不是 dp。枚举 $0$ ~ $2^H$，第 $i$ 为表示 $H_i$ 是否删除。$W$ 同理。由于数据很小，这样可以过。
4. 图形。就是模拟，但细节很多。
5. 零食塔。按第一个数排序，然后对第二个数 LIS 就好了。
6. 最大价值。我是按照 FSJ 的做法写的。但是没有 AC。可以自己去洛谷上看。
7. 压缩 maojun。没办法，将就着看吧。可以逆向思考，$y\to x$。设为 $a,b,c$，每次将 $c$ 设为 $a+b-1$ 就好了。
8. 线段复杂度。可以计算每条线段对总和的贡献。第 $i$ 的贡献为：$2^{cnt}+2^{n-i}$。$cnt$ 是所有 $j<i$，且 $r_j<l_i$ 的数量。
9. 剩下的我没有 AC 就只放个题目了：「飞犇」快递、平衡的字符串、创世。

Day 3

这场比赛是个学长讲的。比 FSJ 好一点，但不多。

复制于：https://www.cnblogs.com/Fall-wendywan/p/21762382 。经 DeePseek 加工。

T1 VJEKO 模拟，星号唯一：判断前缀+后缀匹配文件名，且首尾匹配。Code.

T2 Number of Pairs 排序后对每个数二分合法左右端点，$O(N log N)$ 统计。

T3 Riko 每根棍子只能分成两段。若全断为两截，则 $N$ 必须为偶数，排序首尾配对检查；否则有未断的，扫一遍记录即可。

T4 相聚 排序后 DP：设 $f[i]$ 为前 $i$ 只的最小代价，转移 $f[i] = min(f[i-2] + a[i]-a[i-1], f[i-3] + a[i]-a[i-2])$。

T5 Vlad and Avoiding X 暴搜优化：黑白染色分治，互相影响的格子同色；答案上界为操作中间 $8$ 个格子，搜索时剪枝。

T6 Bullet 将条件转化为 $A_i/B_i = - B_j/A_j$，价值相同的鱼不能共存。总方案 $2^n$，用 map 统计最简分数（注意负号和零值），排除冲突组合，最后减去全空情况。

黑白染色

就是这样子的：

记住它，后面会用到。

Day 4

做和讲了二些杂题。好在这一天我们拿到了「电脑开智代码」，于是就能愉快地使用 AI 进行学习（Chao'Xi）了。

1. awk 的序列。这题可用双端队列维护。反转奇数次就把开头当成结尾，结尾当成开头。

2. awk 分水果。暴力会超时。可以利用 BFS 思路遍历网格。网格 $(i,j)$ 表示 $A_i+B_j$。将 $A$ 和 $B$ 排序后，$(1,1)$ 将是最小的，向 $(n,n)$ 递增。按照 BFS 遍历即可。

3. 复制 + 1。这竟然是 普及-？容易发现，一定是先做加一，然后到达一定数字后一直复制。于是就可以枚举 $x=1, 2, \ldots, \sqrt{n}$，计算 $1\to x\to n$ 的步数，即 $x-1+\left \lceil \dfrac{n}{x} \right \rceil$。

4. 交换一个奇数的其中两位，求出能构造出的最大偶数。若不行，则输出 $-1$。容易发现，一定要交换前面的一位偶数和最后一位。遍历原串，是偶数就构造出来。在所有构造出来的字符串中取最小的就好了。

5. 一个 $n\times m$ 的网格，每次选相邻的两格 $+1$ 或 $-1$，问是否能将所有数变成 $0$。这题我也不知道自己是怎么想出来的，大概是前几天的模拟赛的题目：黑白染色，黑格总和与白格总和相等，则可以，否则不行。

6. 乱打机。可以发现数字之间会有环。例如样例 1：$3\to 2\to 4$。对于没有被减掉的列，求出所有数字的 LCM，这就是这一段的整体环。要求 $A,A+1,\ldots,B$ 的环数，就可以用 $1,2,\ldots,B$ 的环数减去 $1,2,\ldots,A-1$ 的环数。$1,2,\ldots,x$ 的环数为：$\left \lceil \dfrac{x}{L} \right \rceil$，$L$ 为整体环长度。

7. 给定 $n$ 和质数 $mod$。对每个 $m \le n$，定义 $v_m$ 为：所有 $m$ 阶排列中，满足 排列字典序 < 其逆排列字典序 的数量对 $mod$ 取模。输出 $v_1 \oplus v_2 \oplus \cdots \oplus v_n$。

   可以计算 $p=Q(p)$ 的数量，再用总数 $n!$ 减去即可。$p=Q(p)$ 的数量可用递推求出。定义 $dp_i$ 表示长度为 $i$ 的 $p$，$p=Q(p)$ 的数量。$dp_i=dp_{i-1}+dp_{i-2}\times (i-1)$。

8. 石头剪刀布。这是个概率 DP（？）。定义 $dp_{r,s,p}$ 表示石头剪刀布分别有 $r,s,p$ 只的概率。通过相互战争减少数量和发生概率转移：

   $$dp_{i,j-1,k}=dp_{i,j-1,k}+dp_{i,j,k}\times \dfrac{ij}{ij+ik+jk} \texttt{(石头和剪刀相遇)} \\ dp_{i-1,j,k}=dp_{i-1,j,k}+dp_{i,j,k}\times\dfrac{ik}{ij+ik+jk} \texttt{(石头和布相遇)} \\ dp_{i,j,k-1}=dp_{i,j,k-1}+dp_{i,j,k}\times\dfrac{jk}{ij+ik+jk} \texttt{(剪刀和布相遇)}$$

   初始化：$dp_{r,s,p}=1$。

   答案：$R=\sum_{i=1}^{r}dp_{i,0,0},S=\sum_{j=1}^{s}dp_{0,j,0},P=\sum_{k=1}^{p}dp_{0,0,k}$。

9. 数列。但是我没有 AC。

Day 5

模拟赛。怎么隔一天一场模拟赛啊。

1. 加密。语法题。
2. 海港。可以使用一个滑动窗口，加入的时候增加相应的国家，弹出（队首时间距离当前点超过 $24$ 小时）时减少相应的国家。如果某个国家 $0\to1$，那么国家种类增加 $1$。反之则减少 $1$。按时输出即可。
3. P16227、P2440。这两道很像。就是二分最大值最小。
4. 这和 +1-1×2 那题是一样的。
5. 从 $N$ 个数中选 $2M$ 个配成 $M$ 对，使每对差的平方和最小，$M = K+3$。 这可以用动态规划。定义 $dp_{i,j}$ 表示前 $i$ 只筷子组成 $j$ 双的最小方差。再枚举一个 $k$ 表示将 $a_i$ 与 $a_k$ 配对，从而转移。答案即为 $dp_{n,k+3}$。
6. 倒立的奶牛。这题我搬到 GF24 里了。但原题数据在 $10$ 以内。 可以考虑从右下角开始统计。且右下角如果为 $1$ 那么是一定需要全局反转而不能通过其他矩形来反转的。反转之后递归 $(x-1,y)$ 和 $(x,y-1)$。按照递归的思维，现在这两个点是右下角了，如果为 $1$ 就必须进行反转。直到 $(1,1)$，反转次数就是答案。

Day 6

做了三些杂题。但是都是思维题。思维题最好了，讲完就懂。而且今天是 677 讲，他会给代码。

1. 给定一个只含 $\texttt{A}$ 和 $\texttt{B}$ 的字符串 $s$，长度为 $n$。称一个子串是 good，当且仅当子串中的 每一个字符 都至少属于这个子串内的某个长度至少为 $2$ 的回文子串。你需要统计 $s$ 的所有子串中，good 子串的总数。 这可以枚举所有 bad 串，然后用总数 $\dfrac{n(n-1)}{2}$ 减去。bad 串的形式：$\texttt{AB...B}$、$\texttt{A...AB}$、$\texttt{BA...A}$、$\texttt{B...BA}$。统计这四种情况的数量，用总数减去。

2. 石头游戏。有 $n$ 堆石子，每堆有 $a_i$ 个。两人轮流取石子，T 先手。每次只能从某一堆取 $1$ 个，但不能取上一轮被取过的那一堆。谁无法行动（所有堆都为空，或只剩上一轮被取过的那一堆非空），谁就输。问：每组判断 T 赢还是 HL 赢。

   1. 如果有一堆的数量 严格 超过总数的一半。那么先手一直拿这一堆，另一个人就会输。
   2. 如果总数是奇数，先手赢；偶数反之。

3. 字符游戏。注意到，$\texttt{y}$ 与 $\texttt{x}$ 和 $\texttt{z}$ 都可以交换。所以所有 $\texttt{y}$ 都可以自由移动。所以只需要在 $\texttt{z}$ 之前输出所有 $\texttt{y}$ 即可。

4. 有三个背包，每个背包里有若干整数。 每次操作选两个不同的背包，从第一个背包取一个数 $a$，从第二个背包取一个数 $b$，然后把 $a-b$ 放回第三个背包。重复操作，直到只剩一个数为止。问这个最终的数最大可能是多少。 有两种情况：

   1. 分别在两个背包中取出最小值最负贡献，其余做正贡献。
   2. 总和最小的背包整体做负贡献，其余背包做正贡献。

5. 鱼货替换。注意到与或操作并不会改变数字内每一位上 $1$ 的总数。于是考虑将 $1$ 都往前推，组成 $1111,0111,0011,0001$ 这样的。统计每一位 $1$ 的数量，构造出这些数字，统计平方和即可。

6. 疑惑枪。注意到如果有 $3$ 个及以上的相同的数字，那么一定可以异或起来组成更小。例如：$01,01,01,10$。可以将第 $2$ 和第 $3$ 个 $01$ 异或起来得到 $0$，这样 $00<01$，就不是完美的了。同时注意到 $10^9$ 不会超过 $30$ 位，因此如果数量超过 $60$，就会出现三个重复的，就能直接 $1$ 次解决。

   也就是说这样就将 $n$ 缩小到 $60$，那就可以暴力乱搞了。枚举每一个区间，判断将这个区间异或起来能不能解决。取最小值。如果都不能，就输出 $-1$。

7. 中位数。容易发现以下性质：

   1. 没有 $k$ 一定不行。
   2. 有两个连续的 $k$ 一定可以。
   3. 如果有连续的两个数大于等于 $k$，那一定可以。
   4. 如果有间隔一个数的两个数大于等于 $k$，那一定可以。 按照这些模拟即可。

8. power_bound。如下表格：

   格子	1	2	3	4	...	m
   1.	1
   2.	$2^1$	$2^2$	$2^3$	$2^4$	...	$2^m$
   ...
   n	$n^1$	$n^2$	$n^3$	$n^4$	...	$n^m$

   好像不是很直观。提取出所有 $2$ 的倍数：

   格子	1	2	3	4	...	m
   2.	$2^1$	$2^2$	$2^3$	$2^4$	...	$2^m$
   4.	$2^2$	$2^4$	$2^6$	$2^8$		$2^{2m}$
   8.	$2^3$	$2^6$	$2^9$	$2^{12}$		$2^{3m}$

   你就会发现：只需要考虑指数相同就好了。这可以递推。定义 $cnt_i$ 表示前 $i$ 列有多少个指数相同的。因为 $10^9$，可只计算前 $20$ 列。后面统计以 $i$ 为底有多少个数。计算总和即可。

Day 7

模拟赛。太好了，过完今天就结束了。

1. 控制人偶。模拟，再通过 % 运算优化。
2. 刺杀大师。二分 + BFS。二分最大能承受的伤害，再进行 BFS。
3. 深度。这好像在 BCOI 上做到过。如果是 $\texttt{(}$，如果深度太深了就修改成 $\texttt{)}$ 进行操作，否则入栈；如果是 $\texttt{)}$，如果栈空了，改成 $\texttt{(}$ 再入栈，否则弹出前一个 $\texttt{)}$。
4. 剩下的我没有 AC 就不写解释了。
5. 选择若干工作，并为它们分配互不相同的完成日期（$1$ 到 $m$），使得每个工作 $i$ 的完成日期 $t$ 满足 $t + A_i \le m$，求所有被选中工作的 $B_i$ 之和的最大值。
6. 莫晗。
7. 旅行。这好像是 DP。