1112 Stucked Keyboard (20 分)

太菜了,面对一个(20)分的题乱搞许久。

题意

键盘上有一些键位坏了,当按一次这些键时,都会固定输出k次这些字符。现在告诉你k的值,以及最终输出的字符串,输出可能坏的键位和原始字符串。

思路

由于坏的键位每按一次就会出现k个重复键位,因此对任何一个键位,只要它在字符串中每次连续出现的长度都是k的整数倍,那么这个键位就有可能是坏的,应当被输出。反过来说,只要某个键位存在一段连续重复的长度不是k的整数倍,那么这个键位一定是好的。

例如当k=3时,字符串"aaabbbaaaaaabbbb"中的键位'a'有可能是坏的,因为每次连续出现'a'的长度都是3的倍数(即"aaa"和"aaaaa"共两段);而键位"b'则
一定是好的,因为在这个字符串中虽然有一段连续的'b'的长度是3的倍数(即"bbb"这一段),但也存在一段连续的b的长度为4,不是3的倍数,因此'b'一定是好的。

题解

  1. 设置数组vis,其中vis[c]为0时表示键位c有可能是坏的,vis[c]为1时表示键位c一定是好的,vis[c]为2时表示键位c是己输出的坏键。vis数组将初始化为全0,表示初始状态下每个键位都可能是坏的。

  2. 遍历输入的字符串,对其中每一段连续重复键位,只要其长度不是k的倍数,则说明该键位一定是好的,将其vis值设置为1。遍历完成后,我们就可以知道每个键位是否是好的。

  3. 接下来输出坏键。遍历输入的字符串,如果当前键位的vis值为0,则说明该键位可能是坏键,将其输出。由于每个坏键只输出一次,因此在输出后将该键位的vis值修改为2,表示已输出的坏键,不再重复输出。

  4. 接着输出还原的字符串。遍历输入的字符串,如果当前键位的isStuck值为2,则说明该键位是上一步已输出的坏键,因此此处只输出一次,然后将下标增加k,以跳过重复部分;否则说明该键位是好键,在输出一次后将下标加1。

注意点

坏键的输出顺序是其在字符串中的出现顺序,而非字典序。

代码

string s;
int vis[130];
int n;

int main()
{
    cin>>n;
    cin>>s;

    for(int i=0;i<s.size();)
    {
        int j=i;
        while(j<s.size() && s[j] == s[i])
            j++;
        if((j-i) % n) vis[s[i]]=true;
        i=j;
    }

    for(auto t:s)
        if(!vis[t])
        {
            vis[t]=2;
            cout<<t;
        }
    cout<<endl;
            

    for(int i=0;i<s.size();)
    {
        if(vis[s[i]] == 2)
        {
            cout<<s[i];
            i+=n;
        }
        else
        {
            cout<<s[i];
            i++;
        }
    }
    cout<<endl;

    //system("pause");
    return 0;
}
原文地址:https://www.cnblogs.com/fxh0707/p/14410855.html