P2273

035966_L3 · 2025-07-08 01:27:53 · 题解

对于除 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;
}