3月18日

24湖北省赛H

去年比赛没时间看，虽然看了也肯定不会写。偶然翻题单在状压DP里翻到，，但是我连啥叫状压DP都不太记得了，之前只看过几题。

其实是昨天先看了下题解，大概知道要用状压 DP ，然后每两位表示一个有鱼的单元格的状态。

因为每个池塘的鱼的数量最多只有3，所以我们用2位二进制位就可以表示出来。总共需要 \(2k\) 位。由于 \(k\) 很小，所以就可以这样。

并且还有一个很关键的信息就是，每个炸弹最多只能炸五个单元格，并且形状是固定的。所以每个池塘最多只会被5个单元格给炸到。

所以总共最多只有 \(5k\) 个池塘有可能被放置炸弹。我们枚举每一个状态，看使用每一个炸弹会转移到什么状态。

最后我们需要输出鱼全都被炸似的最小的答案，也就是 \(dp_0\) 。

int mp[1001][1001];

void ChatGptDeepSeek()
{
    memset(mp, -1, sizeof mp);
    // cerr<<mp[0][0]<<'\n';
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> x(k), y(k), a(k);
    int now = 0;
    // map<pair<int, int>, int> mp;
    for (int i = 0; i < k; i++) {
        cin >> x[i] >> y[i] >> a[i];
        mp[x[i]][y[i]] = i;
        // mp[{ x[i], y[i] }] = i;
        now |= (a[i] << (2 * i));
    }
    // 10 01 10
    // cerr << now << '\n';
    vector<int> dp(now + 1, 666);
    dp[now] = 0;
    vector<pair<int, int>> dir { { 0, 0 }, { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
    auto calc = [&](int now_val, int i, int j) {
        for (auto it : dir) {
            int nx = i + it.first, ny = j + it.second;
            if (nx > n || nx < 1 || ny > m || ny < 1)
                continue;
            if (mp[nx][ny] != -1) {
                int xx = (now_val >> (2 * mp[nx][ny])) & 3;
                assert(xx <= 3 && xx >= 0);
                now_val ^= (xx << (2 * mp[nx][ny]));
                xx = max(0, xx - 1);
                now_val |= (xx << (2 * mp[nx][ny]));
            }
        }
        return now_val;
    };
    //k * 2**20
    //k*1e6*5
    for (int i = 0; i < k; i++) {
        for (auto it : dir) {
            int nx = x[i] + it.first, ny = y[i] + it.second;
            if (nx > n || nx < 1 || ny > m || ny < 1)
                continue;
            // for (int _ = 1; _ <= 3; _++)
            for (int j = now; j >= 0; j--) {
                int nxt = calc(j, nx, ny);
                assert(nxt <= j);
                dp[nxt] = min(dp[nxt], dp[j] + 1);
            }
        }
    }
    cout << dp[0] << '\n';
}

然后其实就是一些简单的操作了。。但是我把 map 改成数组就不超时了。。

但是时间最多 500ms 了，算比较慢的了。看了别人的更快代码发现，有的是 DFS ，有的是把状态放外层，如果不是合法状态就跳过，可以减少很多的时间。

改了之后变成 240ms。。虽然写了十分钟多，且写错了看了一会才看出来。。我把 ny>m || ny<1 写成了 ny>m || ny>m 。

    for (int i = now; i >= 0; i--) {
        {
            int tmp = i;
            bool skip = false;
            for (int j = 0; j < k; j++) {
                if ((tmp & 3) > a[j]) {
                    skip = true;
                    break;
                }
                tmp >>= 2;
            }
            if (skip)
                continue;
        }
        // cerr<<i<<" "<<dp[i]<<" \n";
        for (int j = 0; j < k; j++) {
            for (auto it : dir) {
                int nx = x[j] + it.first, ny = y[j] + it.second;
                if (nx > n || nx < 1 || ny > m || ny < 1)
                    continue;
                int nxt = calc(i, nx, ny);
                // cerr<<nxt<<'\n';
                dp[nxt] = min(dp[nxt], dp[i] + 1);
            }
        }
    }

24湖北省赛G

乐，写了三个小时。。。虽然前面一直在写错误的做法。。

最后精力不太行了，实在看不出来。。问了下deepseek，帮我找到了一些问题。因为写错了重新写一下，然后忘记初始化并查集了。。

然后占了新格子的话，周围所有的点的气都不能有这个格子。这一点我也知道啊，但是脑子非常混乱了。。然后瞎改了下过了。

还是很麻烦的一个题的，然后我是没有想到每个连通块的气都放集合里不会TLE MLE。。。但是每个连通块每次 DFS BFS算气也是没问题。。

确实就是模拟。不然我也写不了这么久，可能就一点东西都敲不了。

感觉 BFS DFS 同样不好写。真要哈气了。

虽然效率很低，但也是多写一题吧。也该休息一下了。

int board[20][20];
int p[20][20];

constexpr int N = 5e5;
int cnt[N + 1], f[N + 1];
// bool vis[N + 1];
// vector<int> f(9);
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
void ChatGptDeepSeek()
{
    // 看自己上下左右的同色的
    // 如果有 那么加入它们所在的联通块
    // 用并查集维护联通的信息
    //
    // 看它周围的颜色不同的 若气为0了 则该全部移除了
    // 怎么用并查集呢？好像还行 试试 ，其实没用过几次并查集（
    for (int i = 0; i <= 19; i++)
        for (int j = 0; j <= 19; j++)
            board[i][j] = -1;
    int m;
    cin >> m;

    vector<pair<int, int>> dir { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    vector<set<pair<int, int>>> Qi(m + 1, set<pair<int, int>>());

    int res = 0;
    auto Eat = [&](auto&& self, int x, int y, int v) -> void {
        // cerr << x << " " << y << '\n';
        res++;
        assert(x <= 19 && x >= 1 && y <= 19 && y >= 1);
        board[x][y] = -1;
        for (auto it : dir) {
            int nx = x + it.first, ny = y + it.second;
            if (nx > 19 || nx < 1 || ny > 19 || ny < 1 || board[nx][ny] == -1)
                continue;
            if (board[nx][ny] != v) {
                int idx = find(p[nx][ny]);
                assert(idx <= m && idx > 0);

                Qi[idx].insert({ x, y });
            } else
                self(self, nx, ny, v);
        }
    };
    for (int i = 1; i <= m; i++) {
        res = 0;
        int x, y;
        cin >> x >> y;
        board[x][y] = (i % 2);
        p[x][y] = i;
        f[i] = i;

        // 先算周围的反色的气
        for (auto it : dir) {
            int nx = x + it.first, ny = y + it.second;
            if (nx > 19 || nx < 1 || ny > 19 || ny < 1 || board[nx][ny] == -1)
                continue;
            int idx = find(p[nx][ny]);
            // if(!idx) continue;
            assert(idx <= m && idx > 0);

            if (!Qi[idx].empty())
                Qi[idx].erase({ x, y });
            if (p[nx][ny] % 2 != i % 2) {
                // dbg(i, nx, ny);

                if (Qi[idx].empty()) {
                    // dbg(nx, ny, idx);
                    Eat(Eat, nx, ny, p[nx][ny] % 2);
                    // f[idx] = 0;
                }
            }
        }
        for (auto it : dir) {
            int nx = x + it.first, ny = y + it.second;
            if (nx > 19 || nx < 1 || ny > 19 || ny < 1)
                continue;
            if (board[nx][ny] == -1)
                Qi[i].insert({ nx, ny });
        }
        for (auto it : dir) {
            int nx = x + it.first, ny = y + it.second;
            if (nx > 19 || nx < 1 || ny > 19 || ny < 1 || (board[nx][ny] != i % 2))
                continue;
            int idx = find(p[nx][ny]);
            if (idx == i)
                continue;
            assert(idx <= m && idx > 0 && board[nx][ny] == board[x][y]);
            for (auto it : Qi[idx]) {
                // if (board[it.first][it.second] == -1)
                Qi[i].insert(it);
            }
            f[idx] = i;
        }
        // dbg(Qi[i]);
        // cerr << Qi[i].size() << '\n';
        int val = res;
        res = 0;
        if (Qi[i].empty())
            Eat(Eat, x, y, i & 1);
        if (i & 1) {
            cout << res << " " << val << '\n';
        } else {
            cout << val << " " << res << '\n';
        }
        // dbg(Qi[find(1)]);
        // dbg(Qi[2]);
    }
    // 我要哈气了
}