A - ><

左右分别是 >，< 的一定可以设为 \(0\)，倒推即可，最后对两类限制取 max。

C - Linear Approximation

取 \(a_i-i\) 的中位数即可。

本文基本不做证明，只简单说明大致内容，由于博主只是一只猫没有数理基础，有错误还望指出（其实大部分在搬 wiki）。

A,B 喂猫。

A - Table Tennis Training

给定位置 \(1\sim n\)，一开始有两个人在 \(a,b\)，每一次每个人可以任意向左或向右走一步，如果在边上不能越界但是可以不动，问最少多少步结束后两个人在同一个位置。\(n\leqslant 10^{18}\)。

直接枚举向中间贴（只有 \(a,b\) 奇偶性相等时才可以）还是都先向左/向右，如果奇偶性不同有个人需要等一步，三种情况取最小值即可。

A - Erasing Vertices

给定大小为 \(n\) 的有向图，每次随机选择一个未删除的节点，将其与其可以到的的点全部删除，求总操作次数期望，\(n\leqslant 100\)。

考虑贡献，设能到达 \(i\) 的节点数为 \(d_i\)（包括自己），则其被操作的概率是 \(\dfrac{1}{d_i}\)，所以期望是每个点的和，求 \(d_i\) 建图跑或者直接 floyd 传递闭包。

C - Candles

枚举最后点燃的区间是什么（长度一定为 \(k\) ），这个区间的答案根据左端点右端点是否在原点两侧判一下就好。

提交记录

膜 zzz 赛考了 F，先占个坑，剩下的等我做到这再补。

A - Range Flip Find Route

直接 dp，转移根据贪心显然 \[ f(i,j)=\min(f(i,j-1)+[(i,j)是墙][(i,j-1)不是墙],f(i-1,j)+[(i,j)是墙][(i-1,j)不是墙]) \] 不知道为什么只开到 \(100\) 还给了 \(2s\)，还以为我 A 都想假了。

提交记录

A - Pay to Win

把过程倒过来，暴力记忆化搜索，每次可以转移至 \(\lfloor\dfrac{n}{5}\rfloor\) 和 \(\lceil\dfrac{n}{5}\rceil\)（\(2,3\) 同理），再和 \(nD\) 取 \(\min\)，注意到每一次的 \(n\) 都是 \(\dfrac{N}{2^x3^y5^z}\) 上下取整的形式，所以复杂度是对的。

提交记录