自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 21:35:50，当前版本为作者最后更新于2025-07-08 01:27:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于除 $r_1$ 外的寄存器 $r_i$，分类讨论：

• $r_i$ 在不删除指令的前提下仍然可能为最小值：为了防止我们加上去的指令被删掉，那么我们需要添加 $2$ 个 $\text{CE}(1,i)$ 来把这个最小值交换到 $r_1$。
• $r_i$ 在不删除指令的前提下不可能为最小值，但在删除某条指令后可能为最小值：有意已经有一条被删除的指令垫背，我们只需要添加 $1$ 个 $\text{CE}(1,i)$ 来把这个最小值交换到 $r_1$。
• $r_i$ 在不删除指令的前提下不可能为最小值，在删除某条指令后也不可能为最小值：显然不用管它。

枚举被删除的指令并根据模拟结果给寄存器分类即可。

在 DeepSeek 强大卡常能力（套上 bitset）的加持下，以上 $O(N+M^2)$ 做法成功地冲过了此题。

（免责声明：以下代码经过 DeepSeek 的卡常处理。）

AC Code：

#include <cstdio>
#include <bitset>
#include <vector>
using namespace std;

const int MAX_N = 10012, MAX_M = 20012;
bitset<MAX_N> a, b, t;
int ox[MAX_M], oy[MAX_M];

inline int fast_read_int() {
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}

int main() {
    int n = fast_read_int();
    int m = fast_read_int();
    
    for (int i = 1; i <= m; ++i) {
        ox[i] = fast_read_int();
        oy[i] = fast_read_int();
    }

    a.set(); // Set all bits to 1 (equivalent to 0xFF in previous version)
    for (int i = 1; i <= m; ++i) {
        if (a[ox[i]] || a[oy[i]]) {
            b = a;
            for (int j = i + 1; j <= m; ++j)
                if (b[ox[j]] || b[oy[j]]) {
                    b.set(ox[j]);
                    b.reset(oy[j]);
                }
            t |= b;
            a.set(ox[i]);
            a.reset(oy[i]);
        }
    }
    
    int ans = 0;
    for (int i = 2; i <= n; ++i) {
        ans += a[i] ? 2 : (t[i] ? 1 : 0);
    }
    printf("%d\n", ans);
    
    return 0;
}