题解归档 - cf2234G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2234G
• 本地来源：problems/cf2234G/idea.md
• 题目链接：https://codeforces.com/contest/2234/problem/G
• 原始标题：cf2234G - Stripe, Token and Two Players

思路

cf2234G - Stripe, Token and Two Players

pattern:
game DP compressed by nearest losing state per power

state:
At cell i with current power p, the player first chooses final power
P in [p, p+a[i]], then moves to any future cell within distance P.
Landing on n+1 wins immediately.

claim:
Process cells from right to left. For every power P, keep near[P], the
nearest future cell j>i such that state (j,P) is losing. A final power P
is winning from cell i iff either it reaches n+1, or near[P] <= i+P.

why:
With final power P, all cells i+1..i+P are reachable and the power remains
P. Moving to any losing state wins. No losing state at the same i may be
used during the current row, so updates are batched after the row is complete.

compression:
Store d[P]=near[P]-P. For fixed i, final power P can reach a losing state
iff d[P] <= i. Thus state (i,p) is losing iff:

• p+a[i] < n+1-i, so no immediate win is available.
• Every P in [p,p+a[i]] has d[P] > i.

implementation:
A segment tree stores both minimum and maximum d[P]. For fixed i, powers
with d[P] > i are inactive. A start p is losing exactly when the whole
window [p,p+a[i]] lies inside one consecutive inactive run. Enumerate inactive
runs with first d>i / first d<=i; a run [L,R] contributes losing starts
[L, R-a[i]] clipped by the no-immediate-win limit. After finishing cell i,
update all losing powers with d[p]=i-p.

check:
brute.cpp does exact memoized game DP for small n. gen.cpp mixes random
small cases with zero-heavy and large a[i] cases.

代码

来源：problems/cf2234G/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100005;
const ll inf=(ll)4e18;
ll a[maxn];
ll mn[4*maxn],mx[4*maxn];
int n;
void build(int v,int l,int r){
    mn[v]=inf;
    mx[v]=inf;
    if(l==r) return;
    int m=(l+r)>>1;
    build(v<<1,l,m);
    build(v<<1|1,m+1,r);
}
void upd(int v,int l,int r,int p,ll val){
    if(l==r){
        mn[v]=val;
        mx[v]=val;
        return;
    }
    int m=(l+r)>>1;
    if(p<=m) upd(v<<1,l,m,p,val);
    else upd(v<<1|1,m+1,r,p,val);
    mn[v]=min(mn[v<<1],mn[v<<1|1]);
    mx[v]=max(mx[v<<1],mx[v<<1|1]);
}
int firstLe(int v,int l,int r,int ql,int qr,ll val){
    if(qr<l or r<ql or mn[v]>val) return -1;
    if(l==r) return l;
    int m=(l+r)>>1;
    int res=firstLe(v<<1,l,m,ql,qr,val);
    if(res!=-1) return res;
    return firstLe(v<<1|1,m+1,r,ql,qr,val);
}
int firstLe(int l,int r,ll val){
    l=max(l,1);
    r=min(r,n);
    if(l>r) return -1;
    return firstLe(1,1,n,l,r,val);
}
int firstGt(int v,int l,int r,int ql,int qr,ll val){
    if(qr<l or r<ql or mx[v]<=val) return -1;
    if(l==r) return l;
    int m=(l+r)>>1;
    int res=firstGt(v<<1,l,m,ql,qr,val);
    if(res!=-1) return res;
    return firstGt(v<<1|1,m+1,r,ql,qr,val);
}
int firstGt(int l,int r,ll val){
    l=max(l,1);
    r=min(r,n);
    if(l>r) return -1;
    return firstGt(1,1,n,l,r,val);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,1,n);
        bool startLose=false;
        for(int i=n;i>=1;i--){
            ll A=a[i];
            ll limit=(ll)n-i-A;
            vector<pair<int,int>> lose;
            for(ll cur=1;cur<=limit;){
                int L=firstGt((int)cur,(int)min(limit,(ll)n),i);
                if(L==-1) break;
                int nxt=firstLe(L,n,i);
                ll R=(nxt==-1?n:nxt-1);
                ll end=min(limit,R-A);
                if(end>=L) lose.push_back({L,(int)end});
                cur=R+1;
            }
            if(i==1){
                for(auto [l,r]:lose){
                    if(l<=1 and 1<=r) startLose=true;
                }
            }
            for(auto [l,r]:lose){
                for(int p=l;p<=r;p++) upd(1,1,n,p,(ll)i-p);
            }
        }
        cout<<(startLose?2:1)<<"\n";
    }
    return 0;
}