题目大意

给定从 $1$ 到 $n$ 编号的牌，初始按 $1$ 在顶部、$n$ 在底部的顺序排列。进行了 $k$ 次操作，操作类型包括：

• 移除顶部的牌；
• 移除底部的牌；
• 移除顶部或底部的任意一张牌。

需判断每张牌的状态：被移除（输出 -）、保留（输出 +）或状态不确定（输出 ?）。

思路

通过三个变量统计新的顶部位置 $ctop$，新的底部位置 $cback$ 以及未知移除的个数 $uk$。

之后遍历 $1\sim n$，分如下几种情况：

• 情况一：如果操作次数 $k$ 大于等于总数 $n$​，则说明已经没有牌存在了，直接输出 -。\
• 情况二：如果当前位置不在顶位置加上未知移除数以及底位置减去未知移除数的范围中，则说明即使未知移除全为同一个操作也无法移除当前位置，输出 +。
• 情况三：如果当前位置不在顶位置以及底位置之间，则一定被移除了，输出 -。
• 情况四：剩余情况即为不确定，输出 ?。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void solve()
{
    int n,k,ctop=0,cback=0,uk=0;string s;
    cin>>n>>k>>s;
    cback=n;//初始化底位置
    for(char c:s)
    {
        if(c=='0')//更新顶位置
        {
            ctop++;
        }
        else if(c=='1')//更新底位置
        {
            cback--;
        }
        else//更新未知位置
        {
            uk++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(k>=n)cout<<"-";//情况1
        else if(i>ctop+uk&&i<cback-uk+1)cout<<"+";//情况2
        else if(i<=ctop||i>=cback+1)cout<<"-";//情况3
        else cout<<"?";//情况4
    }
    puts("");
}
signed main()
{
    int t;
    cin>>t;//别忘了 t 组样例
    while(t--)
    {
        solve();
    }
    return 0;
}

复杂度

时间复杂度为 $\mathcal{O}(t(k+n))$。