P11138 [LGAPC001] C - Not APC 题解

· · 题解

题目传送门：P11138 [APC001] C - Not APC

题意简述

消消乐。如果能找到按顺序的 APC 串就消掉，要让字符串尽量小并输出过程。

题目分析

像这道题一样用字符串、栈或队列的题已经有很多了，本题不过是要输出过程。

我们建三个队列来存字符 A、P、C 的数量和位置，遍历一遍字符串。当我们看到字符 A时，肯定要存入队列以备后面的 P 和 C；当我们看到 P 时，如果加上它后存 P 的队列数量小于等于存 A 的队列，那这些字符都能匹配到 A；如果是 C 则要当存 A 和 P 的队列都比它大，才考虑将它入队。

一旦存 C 的队列有值（此时另外两个队列一定也有），则为了利益最大就正好从队列最前端的 A 和 P 选字符，将这三个消掉并将这次的操作存入另一个队列。

此时将这三个消掉的字符在字符串中的位置要替换成一个不存在的以便之后输出。

输出时先遍历一遍字符串，如果不是之前的专用替换字符就输出，之后输出存操作的队列的长度，然后次序输出。

……枯燥的文字好抽象啊，还是上代码吧。

编写代码

首先初始化各种队列，为了方便定义一个三元组结构体类型的队列存操作：

#include<iostream>
#include<queue>
using namespace std;
int t;
string s;
queue<int>qa,qb,qc;
struct three{
    int a,b,c;
};
queue<three>q;

然后编写字符串处理部分：

for(int i=0;i<s.size();i++){
  if(s[i]=='A')qa.push(i+1);
  else if(s[i]=='P'&&(qa.size()>qb.size()))qb.push(i+1);
  else if(s[i]=='C'&&(qb.size()>qc.size())){
    qc.push(i+1);
    three o;o.a=qa.front(),o.b=qb.front(),o.c=qc.front();
    s[o.a-1]=char(0),s[o.b-1]=char(0),s[o.c-1]=char(0);
    qa.pop(),qb.pop(),qc.pop();
    q.push(o);
  }
}

当字符为能用到的 C 时，（放存它的队列只是为了清晰明了）首先把三元组存起来入队，然后把入队的三个字符出队，再占位删除字符串中的相应位置。

然后是输出部分：

bool b=1;
for(int i=0;i<s.size();i++){
  if(s[i]!=char(0)){
    cout<<s[i];
    b=0;
  }
}
if(b)cout<<"Perfect";
cout<<'\n'<<q.size()<<'\n';
while(!q.empty()){
  cout<<q.front().a<<' '<<q.front().b<<' '<<q.front().c<<'\n';
  q.pop();
}

每次操作边输出边出队即可。注意：

知周所众，多测函数好。所以这是我的主函数（起名废默默碎了）：

int main(){
    cin>>t;
    while(t--){
        cin>>s;
        doing();
        while(!qa.empty())qa.pop();
        while(!qb.empty())qb.pop();
        while(!qc.empty())qc.pop();
    }
    return 0;
}

这题除了难点外还是蛮简单的，下面放完整代码：

完整代码

（赛时）

#include<iostream>
#include<queue>
#define doing doing()
using namespace std;
int t;
string s;
queue<int>qa,qb,qc;
struct three{int a,b,c;};
queue<three>q;
void doing{
    for(int i=0;i<s.size();i++){
        if(s[i]=='A')qa.push(i+1);
        else if(s[i]=='P'&&(qa.size()>qb.size()))qb.push(i+1);
        else if(s[i]=='C'&&(qb.size()>qc.size())){
            qc.push(i+1);
            three o;o.a=qa.front(),o.b=qb.front(),o.c=qc.front();
            s[o.a-1]=char(0),s[o.b-1]=char(0),s[o.c-1]=char(0);
            qa.pop(),qb.pop(),qc.pop();
            q.push(o);
        }
    }
    bool b=1;
    for(int i=0;i<s.size();i++){
        if(s[i]!=char(0)){
            cout<<s[i];
            b=0;
        }
    }
    if(b)cout<<"Perfect";
    cout<<'\n'<<q.size()<<'\n';
    while(!q.empty()){
        cout<<q.front().a<<' '<<q.front().b<<' '<<q.front().c<<'\n';
        q.pop();
    }
    return ;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>s;
        doing;
        while(!qa.empty())qa.pop();
        while(!qb.empty())qb.pop();
        while(!qc.empty())qc.pop();
    }
    return 0;
}

赛时 AC。当然我们可以把没必要的队列简化掉：

#include<iostream>
#include<queue>
using namespace std;
queue<int>qa,qp;
struct three{
    int a,b,c;
};
queue<three>q;
void doing(string s){
    for(int i=0;i<s.size();i++){
        if(s[i]=='A')qa.push(i+1);
        else if(s[i]=='P'&&(qa.size()>qp.size()))qp.push(i+1);
        else if(s[i]=='C'&&(!qp.empty())){
            three o;o.a=qa.front(),o.b=qp.front(),o.c=i+1;
            s[o.a-1]=char(0),s[o.b-1]=char(0),s[i]=char(0);
            qa.pop(),qp.pop(),q.push(o);
        }
    }
    bool b=1;
    for(int i=0;i<s.size();i++){
        if(s[i]!=char(0)){
            cout<<s[i];
            b=0;
        }
    }
    if(b)cout<<"Perfect";
    cout<<'\n'<<q.size()<<'\n';
    while(!q.empty()){
        cout<<q.front().a<<' '<<q.front().b<<' '<<q.front().c<<'\n';
        q.pop();
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        doing(s);
        while(!qa.empty())qa.pop();
        while(!qp.empty())qp.pop();
    }
    return 0;
}

AC 记录。