题解：CF1866I Imagination Castle

LiaoYF · 2025-09-17 21:50:19 · 题解

做法

首先考虑暴力 DP，设 dp_{i,j} 代表先手走完之后到了 (i,j) 时是先手必胜还是必败（1 表示必胜， 0 表示必败）。显然有对于所有关键点，dp_{X_i,Y_i}=1，且 dp_{n,m}=1。倒着 DP 即可。

考虑优化。发现 dp_{i,j}=1 当且仅当 (i,j) 无法走到任何 dp_{x,y}=1 的位置（否则下一轮轮到后手就可以直接走到一个必胜点）。于是可以发现一个重要性质：不考虑关键点，每行和每列最多有一个 1。于是考虑设 f_i 表示第 i 行除了关键点的 1 在哪个位置，g_i 表示第 i 列除了关键点的 1 在哪个位置（-1 表示没有）。发现只要知道了所有大于 i 的 j 的 f_j，就能算出 f_i。于是 f 与 g 是独立的，分别倒着计算即可。

具体地，f_i 需要不能走到它下面的 1，设 t 为所有大于 i 的行的 1 所在的列的 MEX。如果 t 大于这一行所有关键点所在列的最大值，那么 f_i=t，否则 f_i=-1。用 set 维护即可。

代码

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define i128 __int128
#define ALL(x) x.begin(),x.end()
#define popcount(x) __builtin_popcountll(x)
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int INF=1e18;
const int N=200005;
const int MOD1=1e9+7,MOD2=998244353;
const int MOD=MOD1;
int n,m,k;
int f[N],g[N];//这一行/列除了关键点的1 
vector<int> vec1[N],vec2[N];
set<int> s;
void calc(int x){
    //计算行
    int t=(!s.empty()?*s.rbegin():-1);
    int mx=0;
    for(auto i:vec1[x]){
        mx=max(mx,i);
    }
    //debug(x,mx,t);
    if(t>mx)f[x]=t;
    for(auto i:vec1[x]){
        s.erase(i);
    }
    if(f[x]!=-1){
        s.erase(f[x]);
    }
    if(x!=1)calc(x-1);
}
void calc2(int x){
    int t=(!s.empty()?*s.rbegin():-1);
    int mx=0;
    for(auto i:vec2[x]){
        mx=max(mx,i);
    }
    if(t>mx)g[x]=t;
    for(auto i:vec2[x]){
        s.erase(i);
    }
    if(g[x]!=-1){
        s.erase(g[x]);
    }
    if(x!=1)calc2(x-1);
}
void solve_(){
    cin>>n>>m>>k;
    bool flg=0;
    bool flg2=0;
    for(int i=1;i<=k;i++){
        int x,y;
        cin>>x>>y;
        if(x==1||y==1){
            flg=1;
        }
        if(x==n&&y==m){
            flg2=1;
        }
        vec1[x].push_back(y);
        vec2[y].push_back(x);
    }
    if(!flg2){
        vec1[n].push_back(m);
        vec2[m].push_back(n);
    }
    if(n==1&&m==1){
        cout<<"Bhinneka\n";
        return;
    }
    if(n==1||m==1){
        cout<<"Chaneka\n";
        return;
    }
    if(flg==1){
        cout<<"Chaneka\n";
        return;
    }
    for(int i=1;i<=n;i++){
        f[i]=-1;
    }
    for(int i=1;i<=m;i++){
        g[i]=-1;
    }
    for(int i=1;i<=m;i++){
        s.insert(i);
    }
    calc(n);
    s.clear();
    for(int i=1;i<=n;i++){
        s.insert(i);
    }
    calc2(m);
    for(int i=2;i<=n;i++){
        if(f[i]==1){
            cout<<"Chaneka\n";
            return;
        }
    }
    for(int i=2;i<=m;i++){
        if(g[i]==1){
            cout<<"Chaneka\n";
            return;
        }
    }
    cout<<"Bhinneka\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase,multitest=0;
    if(multitest)cin>>testcase;
    else testcase=1;
    while(testcase--){
        solve_();
    }
    return 0;
}