PAT甲级1112.

目录

A1112

题目

样例

输入:

3
caseee1__thiiis_iiisss_a_teeeeeest

输出:

ei
case1__this_isss_a_teest

补充样例

输入:

3
caseeeaaa1__thiiisa_iiisss_a_aaaaaateeeeeest

输出:

ei
caseaaa1__thisa_isss_a_aaaaaateest

思路和坑点

　　思路:
　　这个题目的问题在于如何准确辨别坏键，即理解坏键的情况，根据示例可知必须是每次都出现了连续k个或者k的整数倍个字符的才算做是坏键，因此需要对连续出现的字符进行计数并进行判定即可。因此需要计数器统计连续字符，还需要有一个Table来标记坏键，这里可能出现误判的情况，比如序列的前部分和后部分都出现了k整数倍的字符串，但是中间出现了非k整数倍的情况，说明这个键是好的（补充样例中的字符a就不是坏键，理解起来好理解，但是程序来判定上需要注意逻辑实现的时候不要漏掉），那么此处需要注意好键的标记优先级高于坏键，具体可以参考代码实现部分的注释说明。
　　坑点：
　　主要在于坏键和连续出现的好键之间的区分和判定。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    map<char,int> mp;                           //标识键是否损坏 ,1表示正常，2表示坏键 （最好不使用true和false，因为判定时，不存在的map键值为0，即false，影响判定） 
    string wrong="",real="",str;                //wrong存放可疑的坏键,real真正的输出字符串,str用于存放读入的字符串
    cin>>n>>str;
    str+="E";                                   //为了结尾处的判定能够写在循环内，在末尾加上一个不属于统计范围的字符
    int cnt=1;                                  //统计重复次数，初始化为1； 
    for(int i=1;i<str.size();i++){              //从第二个字符开始，第一个字符默认统计在内，个数为cnt的初始值1 
        if(str[i]==str[i-1])                    //如果与前一个字符相同，表示连续，cnt++ 
            cnt++;
        else{                                   //否则判定是否是坏键 
            if(cnt%n!=0)                        //如果不是整数倍，则证明是好键 
                mp[str[i-1]]=1;                 //好键可以覆盖误判的坏键标记，如果前面出现过一次整数倍，后边出现了不是整数倍，说明前边坏键判定不正确，需要修正 
            else{
                if(mp.find(str[i-1])==mp.end())
                    wrong.push_back(str[i-1]);  //当前的键被怀疑是坏键，则加入可疑坏键序列。其中可以坏键不要重复添加
                if(mp[str[i-1]]!=1)
                    mp[str[i-1]]=2;             //确定时坏键的时候需要优先判定是不是好键，如果已经提前被标记为好键，则此时进入坏键判定为后边整数倍序列误判所致 
            }
            cnt=1;                              //更新计数器
        }
    }
    cnt=1;                                      //最终完全确定坏键以后，遍历统计一遍，对于重复的字符，如果是正常重复就输出cnt个，否则输出cnt/n个 
    for(int i=1;i<str.size();i++){
        if(str[i]==str[i-1])                    //连续部分进行计数
            cnt++;
        else{
            if(mp[str[i-1]]==1)                 //如果是好键，正常重复cnt个
                for(int j=0;j<cnt;j++)
                    real+=str[i-1];
            else
                for(int j=0;j<cnt/n;j++)        //如果是坏键，需要除以卡键次数
                    real+=str[i-1];
            cnt=1;                              //更新计数器
        }
    }
    for(int i=0;i<wrong.size();i++){            //输出坏键 
        if(mp[wrong[i]]==2)
            putchar(wrong[i]);
    }
    cout<<'\n'<<real;                           //输出真实的字符串 
    return 0;    
}