题解：P13755 【MX-X17-T4】Yet another Game problem

LiaoYF · 2025-11-23 23:35:03 · 题解

做法

不需要那个结论。

先二分答案，设答案为 x，则令 b_i=[a_i\geq x]。

设 f_{i,j} 表示当前区间是 [i,j] 时 Alice 是否会赢。考虑把这个 DP 画到平面上，横坐标是左端点，纵坐标是右端点，然后我们一次考虑一整个回合，即 Alice 走一步之后 Bob 再走一步。发现操作相当于是 Alice 先向右走，Bob 再向下走。考虑从下往上计算 f。

Alice 一定会走到一个全为 1 的列，否则 Bob 就能走到一个 0 让 Alice 输掉。故这个格子是 1 的充要条件就是右边有一个全为 1 的列。然后我们维护全为 1 的列即可。如果当前最右边的格子为 1 那么这一整行都为 1，否则当前最右边的全 1 列左边的格子一定都为 1，右边的格子（包括它自己）一定都为 0。用栈存全 1 列，每次要么入栈最右边的格子，要么弹出栈顶。

至于第一步可以走哪些，就是所有全 1 列。时间复杂度 O(n\log n)。

代码

#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=1000005;
const int MOD1=1e9+7,MOD2=998244353;
const int MOD=MOD1;
int n,op;
int a[N],b[N];
bool check(int x){
    for(int i=1;i<=n;i++){
        b[i]=(a[i]>=x);
    }
    //从下到上扫
    stack<int> stk;
    for(int i=1;i<=n;i++){
        if(b[i]==1){
            stk.push(i);
            if(i==n){
                return 1;
            }
        }else{
            if(i==n){
                if(!stk.empty()&&stk.top()!=1){
                    return 1;
                }else{
                    return 0;
                }
            }
            if(!stk.empty())stk.pop();
        }
    }
}
void solve_(){
    cin>>n>>op;
    int mx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mx=max(mx,a[i]);
    }
    int l=1,r=mx,res=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            res=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }

    cout<<res<<"\n";
    if(op==1){
        for(int i=1;i<=n;i++){
            b[i]=(a[i]>=res);
        }
        stack<int> stk;
        for(int i=1;i<=n;i++){
            if(b[i]==1){
                stk.push(i);
            }else{
                if(i!=n&&!stk.empty())stk.pop();
            }
        }
        vector<int> vec;
        while(!stk.empty()){
            if(stk.top()!=1)vec.push_back(stk.top());
            stk.pop();
        }
        sort(ALL(vec));
        cout<<vec.size()<<"\n";
        for(auto x:vec){
            cout<<x<<" ";
        }
    }
}
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;
}