求助ABC T3

fenglaiguo @ 2024-10-01 23:54:40

#include<bits/stdc++.h>
using namespace std;
int n,ans;
bool flag[300010];
int as[300010],ps[300010],cs[300010];
string s;
int main() {
    scanf("%d",&n);
    while(n--)
    {
        string s1;
        int a=0,p=0,c=0;
        int k=0,k1=0;
        cin>>s1;
        memset(as,0,sizeof(as));
        memset(ps,0,sizeof(ps));
        memset(cs,0,sizeof(cs));
        memset(flag,0,sizeof(flag));
        for(int i=0;i<s1.length();i++)
        {
            if(s1[i]=='A' && !a && flag[i]==0)
            {
                a=1;
                as[k]=i;
//              printf("sb%d",i);
            }
            else if(s1[i]=='A' && a && flag[i]==0 && k1==0)
            {
                k1=i;
//              printf("sb%d",k1);
            }
            else if(s1[i]=='P' && a && !p && flag[i]==0)
            {
                p=1;
                ps[k]=i;
            }
            else if(s1[i]=='C' && p && a && flag[i]==0)
            {
                a=0,p=0;
                cs[k]=i;
                flag[as[k]]=1;
                flag[ps[k]]=1;
                flag[cs[k]]=1;
                k++;
                if(k1)
                {
                    i=k1-1;
                    k1=0;
                }
            }
        }
        if(k*3==s1.length()) printf("Perfect");
        else for(int i=0;i<s1.length();i++)
        {
            if(!flag[i])
            {
                printf("%c",s1[i]);
            }
        }
        printf("\n%d\n",k);
        for(int i=0;i<k;i++)
        {
            printf("%d %d %d\n",as[i]+1,ps[i]+1,cs[i]+1);
        }
    }
}

by Terrible @ 2024-10-02 00:16:38

截至目前 AtCoder 有 373 场完赛的 ABC。严格地说，其中没有一个题目是以 T3 作题号的。

如果你问的是 C 题的话，请务必说明是哪道 C 题。反正不是最近几场吧？

by InQueue @ 2024-10-02 00:27:22

@Terrible 我猜他说的是昨天举办的 ABC 模拟

by _8008008 @ 2024-10-02 00:31:03

@fenglaiguo 他们说SPJ对行末空格敏感，你试试

by Terrible @ 2024-10-02 01:03:27

这个 300010 不是 3\times 10^5？题目给的是 \sum|S|\leqslant 3\times10^6，从而存在一组数据就是 3\times 10^6 这么大的呢？

by fenglaiguo @ 2024-10-02 02:42:28

@Terrible 会超时

by fenglaiguo @ 2024-10-02 02:42:41

@InQueue 是的

by Terrible @ 2024-10-02 13:12:31

@fenglaiguo

①空间应该确实开得不够，空间开够了的话，memset 就要注意了，因为 sizeof(完整数组) 是比较大的，不过在本题中 10 遍 memset(完整数组) 都不是大问题（虽然这么做的时间耗费也不小，但不是主要的 TLE 原因）。

关于节省 memset 时间：在程序执行完后，确定清理空间的总量，不要一刀切：

memset(as,0,sizeof(int)*(k+1));
memset(ps,0,sizeof(int)*(k+1));
memset(cs,0,sizeof(int)*(k+1));
memset(flag,0,sizeof(bool)*(s1.length()+1));

②i=k1-1; 似乎会使求解方法不是线性的，应该是超时的主要原因。说实话，我没有完全看懂你的写法。

③一个可能的方法如下：

开两个栈，

　sa：一个栈，从前往后存 'A' 出现的位置。

　sp:一个二元栈，从前往后找 'P'，遇到 'P' 后，看看 sa 里有没有 'A'，如果有，取出一个 'A' 的位置 pa，连同 'P' 当前的位置 pp 一起加入 sp 中。

每次遇到 C 时，看看 sp 有没有 'A''P' 两个的位置，取出来，就是一次消除了，做一下记录。

#include<stack>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
using pii=pair<int,int>;
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int T;cin>>T;
    while(T--)
    {
        string s;cin>>s;
        vector<bool>notexists(s.size());
        stack<int>sa;
        stack<pii>sp;
        vector<int>pileofans;
        pileofans.reserve(s.size());
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='A')sa.push(i);
            else if(s[i]=='P')
            {
                if(!sa.empty())sp.emplace(sa.top(),i),sa.pop();
            }
            else
            {
                if(!sp.empty())
                {
                    auto[pa,pp]=sp.top();sp.pop();
                    pileofans.push_back(pa);
                    pileofans.push_back(pp);
                    pileofans.push_back(i);
                    notexists[pa]=1;
                    notexists[pp]=1;
                    notexists[i]=1;
                }
            }
        }
        if(pileofans.size()==s.size())cout<<"Perfect\n";
        else
        {
            for(int i=0;i<s.size();i++)if(!notexists[i])cout<<s[i];
            cout<<'\n';
        }
        cout<<pileofans.size()/3<<'\n';
        for(int i=0;i<pileofans.size();i+=3)
            cout<<pileofans[i]+1<<' '<<pileofans[i+1]+1<<' '<<pileofans[i+2]+1<<'\n';
    }
    return 0;
}