1112 Stucked Keyboard (20 分)

2019-04-26

1112 Stucked Keyboard (20 分)

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:

1 2	3 caseee1__thiiis_iiisss_a_teeeeeest

Sample Output:

1 2	ei case1__this_isss_a_teest

作者: CHEN, Yue

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

给出一串由坏键盘打出的字符串。敲一次坏的键会重复k次，求哪些键是坏的，并求原字符串。

分析

虽然20分，但是一开始想歪了，想用每个字符出现总次数除以各字符连续出现的次数。是连续出现的次数是要根据k算的，比如k=3，那1-3个e算一次，4-6个e就得算成两次，特别复杂。

后来换了思路。利用map代表字符是否可能为坏键，初始化为1。然后遍历字符串，统计每个字符连续出现个数，不整除k的是正常的键。

最后输出时candi为0代表是好的键。为1代表第一次检测到，输出并改为2。为2说明是坏键，向后数k-1个。

代码

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include <sstream>

using namespace std;
int k;
string s;
map<char,int> candi;
int main() {
    cin >> k>>s;
    for(int i=0;i<s.length();i++)
        candi[s[i]]=1;

    for(int i=0;i<s.length();){
        int c=1;
        while(i+c<s.length()&&s[i]==s[i+c])
            c++;
        if(c%k!=0)
            candi[s[i]]=0;
        i+=c;
    }
    string orign;
    for(int i=0;i<s.length();i++){
        orign+=s[i];
        if(candi[s[i]]==1) {
            cout<<s[i];
            candi[s[i]]=2;
        }
        if(candi[s[i]]==2)
            i+=(k-1);
    }
    cout<<endl<<orign;
    return 0;
}