2021/12/31 校内比赛

Problem D

其实是道很简单的二分题但考场上我一直想的是贪心。

每一次操作，任选一个不变其余减 \(1\)。

那么二分答案，对于二分到的答案 \(mid\)，我们计算 \(\sum\limits_{a_i<mid}(mid-a_i)\)，如果小于等于 \(mid\) 就是合法答案。

时间复杂度 \(O(n\log n)\)。

Problem H

很容易想到的一个逆向思维是，所有的人不动，而是电线杆动。

那么怎么解决电线杆与分身的碰撞呢？我们以横向运动为例。

假设电线杆现在在 \((x_0,y_0)\) 点，要向右移动距离 \(l\)，那么根据题意，满足 \(x\in[x_0,x_0+l]\) 且 \(y=y_0\) 的分身都会被合并到点 \((x_0+l+1,y_0)\) 上。

合并直接用并查集即可，关键在于如何找到这些该合并的点。

我们考虑以 \(x\) 升序最为第一关键字，\(y\) 升序作为第二关键字排序，不难发现的是，我们需要的点在一个区间上。

由于需要动态维护，我们用 set 维护，操作的时候 lower_bound 找到所需区间第一个点即可。

同理，处理上下移动时，我们需要以 \(y\) 升序最为第一关键字，\(x\) 升序作为第二关键字排序，需要再来一个 set。

对于时间复杂度，类似于启发式合并，是 \(O(n\log n)\)。

Problem I

分情况讨论：

• 不在最短路上，且边变大：一定不会是新的最短路。
• 不在最短路上，且边变小：将经过这条边的最短路与原来的最短路比较即可。
• 在最短路上，且边变小：原来的最短路减去对应差值即可。
• 在最短路上，且边变大：新的最短路可能是原来的最短路加上这段差值，也可能是删掉这条边做最短路。

因此，这道题中最复杂的部分其实就是如何做删边最短路。

我们先随便取出一条最短路，形成一条链。类似于断环法的思路，我们考虑删掉这条链上的一条边之后，以一条路径绕过这条边。

比如一条路径从 \(x\) 点从这条链出去，从 \(y\) 回来，那么这条路径就能作为 \(x\) 到 \(y\) 链上所有断边的"替代"。

按照这个思路，我们枚举每一条边 \((u,v,w)\)，尝试用 \(d_1(u)+d_2(v)+w\) 来更新对应的区间。由于到 \(u\) 是用的最短路（即 \(d_1(u)\)），因此我们在找 \(x\) 点的时候也要满足最短路的要求（即 \(1-x-u\) 的最短路就是 \(1-u\) 的最短路）。找 \(y\) 的时候同理。

由于只需要区间取最小值，我们用线段树维护即可。

时间复杂度 \(O(n\log n)\)。

Problem M

这好像是我做过的原题，但是时间太久远了我给忘了。

考虑到 \(n\) 很小，我们可以枚举行的所有状态，再枚举列贪心选择（\(1\) 比 \(0\) 多就翻），时间复杂度是 \(O(2^nm)\)，需要优化。

设 \(a_i\) 表示状态为 \(i\) 的列的个数，\(b_i\) 表示在列在状态 \(i\) 时贪心选最少的 \(1\) 的个数。

举个例子，对于状态 \(10111100\)，\(b_i=3\)；对于状态 \(00010100\)，\(b_i=2\)。

那么我们枚举行的状态 \(T\)，有：

由于 \(T\bigoplus i=j\) 与 \(i\bigoplus j=T\) 等价，转化成：

后半部分是 FWT 的模板，直接做即可。

要注意的是，虽然答案在 \(nm\) 以内，但是做的时候可能会超 int 范围，要开 long long。

时间复杂度 \(O(n\log n)\)。