究竟是什么题，让一众大佬（我们机房）分分只能吃罚时？

思路：

可以发现，如果按照题面所给出的操作进行模拟，那么空间肯定是不允许的（时间好像也不行）。同时这些操作中其实有很多对最终的答案根本没有影响。

所以考虑从答案开始倒推。最后服务器的字符串就是最后的那个操作 3 的 PC 端的字符串，而这个 PC 端字符串又是从上一次操作 1 时的服务器字符串再在末尾加上它对应的操作 2 的字符串。

由此一直向前递归直到再也没有前驱服务器字符串或是 PC 端字符串（空字集）。

这样时间

O(Q)

就搞完了。

代码：

（似乎还有更简单的实现方法，我的有点复杂了）

CPP

#include<bits/stdc++.h>
using namespace std;
long long n,q,lt=-1;
struct sss{
    long long op,p;
    string s;
}a[200005];
inline string dfs(long long now,long long op){
    string t="";
    if(op!=-1){
        for(int i=now;i>=0;i--){
            if(a[i].op==1 && a[i].p==op || i==0){
                t=dfs(i,-1);
                for(int j=i;j<=now;j++){
                    if(a[j].op==2 && a[j].p==op)t+=a[j].s;
                }
                return t;
            }
        }
    }
    for(int i=now;i>=1;i--){
        if(a[i].op==3)return dfs(i,a[i].p);
    }
    return t;
}
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=q;i++){
        scanf("%lld%lld",&a[i].op,&a[i].p);
        if(a[i].op==2)cin>>a[i].s;
        if(a[i].op==3)lt=i;
    }
    if(lt!=-1)cout<<dfs(lt,a[lt].p);
}

题解：AT_abc411_d [ABC411D] Conflict 2

文章操作

思路：

代码：

相关推荐

评论

题解：AT_abc411_d [ABC411D] Conflict 2