本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-01 22:45:00

记录

赛时在上课，听说很多人被 B 卡了，以为特别困难，结果发现是基本题，大失所望。切到 E，但是 E 花了很长时间，后来做 G 的时候也调了很长时间，感觉 F 还是比较困难。（后来发现 F 是难调的板子）

题解

A - A Healthy Breakfast

基本判断题，略过不表。

B - Vertical Reading

暴力枚举所有的 $(w,c)$，然后把每个段中的第 $c$ 个字符拿出来比较即可，所以是基本循环 + 判断题，但是很多人没做出来，怎么回事呢（

C - Move It

发现每个盒子中原有的物品只能留下一个，这里选择留下每个盒子中重量最大的，其余的全部移到其他的空盒子里，显然这样一定最优。

D - Ghost Ants

发现如果方向不同，那么不可能相遇。所以预处理一下向右走的，再用向左走的来询问遇见了多少只。可以设 $l_i$ 表示有多少只的起点在 $i$ 及之前，$r_i$ 表示有多少只的终点在 $i$ 及之前，那么对于 $[x,x-t]$ 询问时答案为 $l_x-r_{x-t-1}$。

话说固定了每只的路程长度 $t$ 的话其实可以简化，这个做法可以做路程长度不同的。

E - Random Swaps of Balls

首先注意到初始状态只有两种：初始黑和初始白。另外求期望需要求出概率，但这个题目中只有这两种状态，所以就可以维护 $f_i,g_i$ 分别表示操作 $i$ 轮后黑球在 $1$ 号的概率以及在 $i\in[2,n]$ 分别的概率，其实这里一定有 $f_i+(n-1)g_i=1$，但是我赛时没注意到。

所以分别计算一下每种情况在 $n^2$ 种情况中出现的次数即可，有以下转移：

• $f_i=\frac{n^2-2n+2}{n^2}f_{i-1}+\frac{2n-2}{n^2}g_{i-1}$
• $g_i=\frac{1-f_i}{n-1}$

所以答案为 $f_n+g_n\sum_{k=2}^n$，用等差数列求和即为 $f_n+\frac{(n-1)(n+2)g_n}{2}$。

F - InterSections

发现与区间 $i$ 相交的条件是对 $l,r$ 的共同要求，也即 $l\in[0,l_i-1],r\in[l_i+1,r_i-1]$ 或 $l\in[l_i+1,r_i-1],r\in[r_i+1,10^9]$。考虑把这两个 $l,r$ 的要求放在 $l-r$ 的二维平面上，也就是两个不交的矩形中都可以与第 $i$ 个区间相交。所以扫描线枚举 $l$ 维，求 $r$ 维上的最大值即可。（但是截止到写这段话我还没有调出来）

G - Suitable Edit for LIS

首先原有的最长长度以及不含两端的最长长度 $+1$ 是显然能达到的。考虑让第 $i$ 个数修改后从前面和后面各连上一段，所以先用树状数组跑出以 $i$ 结尾和以 $i$ 开头的最长上升子序列长度 $f_i,g_i$。

所以要求的就是 $\max^{n-1}_{x=2} f_i+g_j+1$，其中 $i<x,j>x,a_j-a_i\ge 2$，那么变为枚举 $j$，把 $f_i$ 以 $a_i$ 为下标扔到树状数组上维护即可，为了保持不小于 $2$ 的性质需要把 $a_i+1$ 也进行离散化。