Home PAT 1112 Stucked Keyboard
Post
Cancel

PAT 1112 Stucked Keyboard

Link

找连续有 k 个相同字符的子串, 可以考虑这题中用 pre 记录前一个字符、用 cnt%k==0 判断的方法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <unordered_set>
using namespace std;
int k;
char s[1010];
int v[40];
unordered_set<char>sett;
string stuck="",ans="";
inline int getIndex(char ch){
    return isdigit(ch)?ch-'0':(ch=='_'?37:ch-'a'+11);
}
int main() {
    scanf("%d%s",&k,s);
    char pre='#';
    int cnt=0;
    for(int i=0;i<strlen(s);++i){
        if(s[i]==pre) cnt++;
        else if(cnt%k==0){
            if(v[getIndex(pre)]!=-1) v[getIndex(pre)]=1;//目前可能是stucked
            cnt=1;
            pre=s[i];
        }else{
            v[getIndex(pre)]=-1;//一定不是stucked
            cnt=1;
            pre=s[i];
        }
    }
    if(cnt%k==0){
        if(v[getIndex(pre)]!=-1) v[getIndex(pre)]=1;
    }else v[getIndex(pre)]=-1;
    for(int i=0;i<strlen(s);){
        if(v[getIndex(s[i])]==1){
            if(!sett.count(s[i])){
                stuck+=s[i];
                sett.insert(s[i]);
            }
            ans+=s[i];
            i+=k;
        }else{
            ans+=s[i];
            i++;
        }
    }
    cout<<stuck<<endl<<ans<<endl;
    return 0;
}
This post is licensed under CC BY 4.0 by the author.