咕 咕 咕 咕 咕

QAQ 两小时建站, 因为我 Nginx 的配置文件忘记打后缀了一直没配进去.

数值为 $i (0 \le i < n)$ 的数有 $c_i$ 个. 从中选取一些数 $S, |S| > 0$, 变为 $\rm{mex}\{S\}$ 放回. 最后剩一个数, 问这个数最大是多少.

$1 \le n \le 10^5, 0 \le c_i \le 10^9, \sum c_i \ge 1$

不会思考的人有难了!

一开始想的是把某点之后所有的数单独拎出来变成 $0$, 然后 $0$ 往上推. 这样就几个问题. 首先是这个点会不会在同一个数里, 然后是即使往上推, 如果有多的, 我还可以拿出来变成 $0$. 比如 $0, 1, 1, 1, 2$, 可以 $2$ 不动, 但是拿出两个 $1$ 变成 $0$. 还有一个, 不是说要"物尽其用", 有时候可以通过"放弃"来达到更好的结果. 假设有 $4, 5$ 两个数, 虽然我可以变成两个 $0$, 但是如果恰好多出来一个 $0$, 比如说最后变成了 $0, 3$, 然后再做的话答案就是 $2$; 但其实可以"丢弃"一个数, 即取出 $4, 5$, 取 $\rm{mex}$ 为 $0$. 这样就只有一个 $3$ 了.

二位平面上 $n$ 个点, 两两不重叠, 要求用两种颜色的边分别把他们连成一个连通块. 连边操作用一个 长度为 $k \ge 2$ 的序列 $s_i$ 表示, 方法如下:

1. 第一种颜色: 对所有 $1 \le i \le \left\lfloor \frac{k}{2} \right\rfloor$, $s_{2i−1}$ 和 $s_{2i}$ 连边
2. 第二种颜色: 对所有 $1 \le j \le \left\lfloor \frac{k-1}{2} \right\rfloor$, $s_{2j}$ 和 $s_{2j+1}$ 连边

求一个最短的序列 $s_i$, 满足上述条件, 且要求序列中相邻两个点不同, 对于同一种颜色, 连得边仅在端点处有相交.

$2 \le n \le 10^4$

题解

考虑最短序列, 应该为 $2n - 1$. 尝试这样是否可行. 从点数很少时手玩, 从简单的方向入手, 尝试构造两条链, 发现确实可行. 不考虑相交的话, 可以这样构造: $1, 2, \dots, n-1, n, n-1, \dots 2, 1$. 而且这两条链是一模一样的. 那么只需要考虑一条链不相交即可.

无穷大的二位网格平面上, $(0, 0)$ 处有一个障碍物. 现在有一个由 R, L, U, D 组成的长度为 $n$ 的操作序列和一个机器人. 操作序列表示控制机器人如何走(上下左右), 如果机器人的下一步是障碍物(即原点), 那么他不行动. 现在有 $Q$ 次询问, 每次询问给出机器人的起点, 问终点. 保证机器人不在 $(0, 0)$.

$1 \le n, q \le 3 \cdot 10^5$

jyz nb!

不要被"一个“给误导了, 把所有询问都放在图上, 然后同时开始执行操作, 想象一下, 是不是有种"背景在动"的感觉? 没错, 这就是 “相对运动”. 与其操作 $Q$ 个机器人, 不如反向操作一个障碍物. 假设在障碍物移动的过程中, 没有碰到任何机器人, 那么障碍物移动的轨迹反一下, 就是所有机器人移动的轨迹了. 障碍物移动的轨迹可以通过二位向量前缀和求得. 统计答案每个机器人起点对它做差即可. 于是, 对于障碍物移动过程中碰到的机器人, 我们想办法改变机器人的起点, 使得其终点不变, 但不再碰见障碍物. 这是好办的, 因为障碍物碰见机器人了的话, 就证明机器人在这个时候会去撞障碍物(相对运动), 那么让机器人"后退"一步, 再执行这个操作, 后续操作是一模一样的. 所以做法就是, 相对运动移动障碍物, 碰到机器人就"推"一下. 需要注意的是, 障碍物移动一下最多推 $n$ 个机器人, 但是这些机器人在后续操作中就等价了, 所以只用搞一个代表出来就行, 用并查集合并一下即可.

(zzs讲课没听, vp遭殃)

打牛客发现完全不会概率期望, 高中课本上的东西就是个屑, 大概率徐积限自己也不清楚就乱教. 冥思苦想, 用自己的方式理解了一波, 记录一下.