专栏文章

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

LLiaoYF1
P13755题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1w5at
此快照首次捕获于
2025/12/01 19:13
3 个月前
此快照最后确认于
2025/12/01 19:13
3 个月前
查看原文

做法

不需要那个结论。
先二分答案，设答案为 xx，则令 bi=[ai≥x]b_i=[a_i\geq x]。
设 fi,jf_{i,j} 表示当前区间是 [i,j][i,j] 时 Alice 是否会赢。考虑把这个 DP 画到平面上，横坐标是左端点，纵坐标是右端点，然后我们一次考虑一整个回合，即 Alice 走一步之后 Bob 再走一步。发现操作相当于是 Alice 先向右走，Bob 再向下走。考虑从下往上计算 ff。
Alice 一定会走到一个全为 11 的列，否则 Bob 就能走到一个 00 让 Alice 输掉。故这个格子是 11 的充要条件就是右边有一个全为 11 的列。然后我们维护全为 11 的列即可。如果当前最右边的格子为 11 那么这一整行都为 11，否则当前最右边的全 11 列左边的格子一定都为 11，右边的格子（包括它自己）一定都为 00。用栈存全 11 列，每次要么入栈最右边的格子，要么弹出栈顶。
至于第一步可以走哪些，就是所有全 11 列。时间复杂度 O(nlog⁡n)O(n\log n)。

代码

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...