【VP 记录】ABC360

· · 个人记录

记录

赛时在上课，听说很多人被 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_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 也进行离散化。