【PAT甲级 - C++题解】1112 Stucked Keyboard

1112 Stucked Keyboard

On a broken keyboard, some of the keys are always stucked. So when you type some sentences, the characters corresponding to those keys will appear repeatedly on screen for k times.

Now given a resulting string on screen, you are supposed to list all the possible stucked keys, and the original string.

Notice that there might be some characters that are typed repeatedly. The stucked key will always repeat output for a fixed k times whenever it is pressed. For example, when k=3, from the string thiiis iiisss a teeeeeest we know that the keys i and e might be stucked, but s is not even though it appears repeatedly sometimes. The original string could be this isss a teest.

Input Specification:

Each input file contains one test case. For each case, the 1st line gives a positive integer k (1<k≤100) which is the output repeating times of a stucked key. The 2nd line contains the resulting string on screen, which consists of no more than 1000 characters from {a-z}, {0-9} and _. It is guaranteed that the string is non-empty.

Output Specification:

For each test case, print in one line the possible stucked keys, in the order of being detected. Make sure that each key is printed once only. Then in the next line print the original string. It is guaranteed that there is at least one stucked key.

Sample Input:

3
caseee1__thiiis_iiisss_a_teeeeeest

Sample Output:

ei
case1__this_isss_a_teest

题意

因此，当你用该键盘输入一些句子时，与这些键相对应的字符将在屏幕上重复出现 k 次。

现在，给定 k 以及最终屏幕显示的结果字符串，请你找出所有可能坏掉的按键，并给出原始字符串。

例如，当 k=3 时，从字符串 thiiis iiisss a teeeeeest，我们可以推断出 i 和 e 可能被卡住了，因为 i 出现在两个地方，都是连续出现 3 次，能被 k 乘除，而 e 连续出现了 6 次，同样也能被 k 整除。但是 s 并没有被卡住，因为 thiiis 中 s 只出现了 1 次，其长度不能被 k 整除。

所以，原始字符串可能是 this isss a teest。

思路

我们可以用一个 st 数组来记录每个字符是否被卡住。

首先，遍历一遍字符串，筛选出没被卡住的字符，即字符出现的连续长度不能被 k 整除就没有被卡住，而最后剩下没有被筛选出的字符就是被卡住了。

然后再遍历一遍字符串，通过上次遍历得到的 st 数组中的结果输出相应被卡住的字符，并记录原始字符串的结果，然后最后输出。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int st[N];
int main()
{
    int k;
    string str;
    cin >> k >> str;
    //先把没卡住的字符筛选出来，剩下的字符就是卡住的
    for (int i = 0; i < str.size(); i++)
    {
        int j = i + 1;
        while (j < str.size() && str[j] == str[i]) j++;    //找出连续字符
        int len = j - i;
        if (len % k)   st[str[i]] = 1;   //如果长度不能整除k，则该字符没卡住
        i = j - 1;
    }
    //输出卡住的字符
    string res = "";
    for (int i = 0; i < str.size(); i++)
    {
        if (!st[str[i]]) cout << str[i], st[str[i]] = 2;
        if (st[str[i]] == 1)   res += str[i];
        else
        {
            res += str[i];
            i += k - 1;
        }
    }
    cout << endl << res << endl;
    return 0;
}