题解 CF1866I 【Imagination Castle】

Leasier · 2023-09-29 18:04:10 · 题解

不难，但感觉很优雅 /jw

首先可以考虑一个暴力的 bool SG：

• 设 f(x, y) 表示棋子现在位于 (x, y)，先手必胜还是必败。
• 直接求出每个 f(x, y) 可以做到 O(nm)。

不妨先来考虑 n \leq m, k = 0 的情况，注意到此时：

• ……

于是当 n \neq m 时先手必胜，否则先手必败。

接下来我们尝试加入特殊点。对于一个特殊点而言，其带来的影响为：

• 左边和上边的非特殊点处的 f 值全部变为 \operatorname{true}。

至此可以注意到我们事实上更加关心的是一行最右侧的非特殊点且 f 值为 \operatorname{false} 的位置。

遂考虑从下往上一行一行扫，记录一下扫到目前位置哪些列有 \operatorname{false}，双指针即可扫出这行中我们关心的位置。

时间复杂度为 O(n + m + k)。

代码：

#include <iostream>
#include <vector>

using namespace std;

bool vis[200007];
vector<int> v[200007];

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++){
        int x, y;
        cin >> x >> y;
        if (x == 1){
            cout << "Chaneka";
            return 0;
        }
        v[x].push_back(y);
    }
    int lst = m;
    for (int i = n; i >= 1; i--){
        while (vis[lst]) lst--;
        if (lst == 0){
            cout << "Chaneka";
            return 0;
        }
        int size = v[i].size();
        bool flag = true;
        for (int j = 0; j < size; j++){
            vis[v[i][j]] = true;
            if (v[i][j] >= lst) flag = false;
        }
        if (flag) vis[lst] = true;
    }
    if (lst != 1){
        cout << "Chaneka";
    } else {
        cout << "Bhinneka";
    }
    return 0;
}