ARC119F AtCoder Express 3
题意有一条长度为 $n+1$ 的村庄，编号依次为 $0\ldots n$。最初，在 $i$ 和 $i+1$ 之间有双向通行的铁路。现在有两个铁路公司（A 和 B）要争夺这些村庄。$0$ 和 $n$ 这两个村庄同时被两个铁路公司占有，$[1,n-1]$ 内的村庄会被其中一个铁路公司占有。假设某个铁路公司占有的村庄按顺序排序为 $a_1,a_2,\ldots,a_m$，那么在 $(a_1,a_2...
题意有一条长度为 $n+1$ 的村庄，编号依次为 $0\ldots n$。最初，在 $i$ 和 $i+1$ 之间有双向通行的铁路。现在有两个铁路公司（A 和 B）要争夺这些村庄。$0$ 和 $n$ 这两个村庄同时被两个铁路公司占有，$[1,n-1]$ 内的村庄会被其中一个铁路公司占有。假设某个铁路公司占有的村庄按顺序排序为 $a_1,a_2,\ldots,a_m$，那么在 $(a_1,a_2...
题意有 $n$ 行 $m$ 列的棋盘，每个位置颜色一开始是红色或蓝色。每次操作你可以选择一个红色格子，选择将这个格子所在行/列都涂成白色格子。求构造一组最大化白色格子的方案。$n,m \leq 2500$。题解比赛的时候没有尝试往二分图上去想，因为感觉这种带先后覆盖顺序的问题好像不是很能做，但是事实证明错了。。这种每次覆盖一行，或者一列的做法都考虑将行列抽象成点，操作位置抽象成边。对于这个题...
题意有一个长度为 $n$ 的排列 $p_i$，你可以执行以下操作任意次：将数字 $x$ 移动到任意一个位置，花费 $A_x$将数字 $x$ 移动到开头，花费 $B_x$将数字 $x$ 移动到结尾，花费 $C_x$求排序最小代价。$n \leq 2 \times 10^5$。题解首先 $B_x,C_x$ 都要和 $A_x$ 取 $\min$。手动模拟一下，我们先固定一些不动的数 $a_1,a_...
由于是恢复训练，所以会把所有题目解法都写写。A显然是少的每一堆就放一个，大的尽量均摊，设 $r < b$，那么就是判断 $\lceil \frac{b}{r} \rceil -1\leq d$。B模拟一下发现这东西无论什么路径权值都是 $nm-1$。证明可以考虑对 $n+m$ 归纳：首先 $n=m=1$ 是对的，考虑到达 $(n,m)$ 最后一步是怎么走的，如果是从 $(n-1,m)$...
题意你从一个二维平面上开始做自由落体运动。重力加速度 $g=10m/s^2$，但是你可以随时调整你在水平方向上的分速度 $v_x \in [-1,1]$。你一开始在点 $(sx,sy)$，但是平面上有 $n$ 个云朵，第 $i$ 个位于 $(x_i,y_i)$，有密度 $c_i$。表示如果你到了 $(x_i,y_i)$，会立刻停止运动 $c_i$ 秒，并在 $c_i$ 秒后将竖直方向分速度重...