题解：CF1866I Imagination Castle

做法

首先考虑暴力 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 维护即可。

代码

CPP

#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;
}

题解：CF1866I Imagination Castle

文章操作

做法

代码

相关推荐

评论

题解：CF1866I Imagination Castle