PAT甲级 1112 Stucked Keyboard

题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805357933608960

这道题初次写的时候，思路也就是考虑从头到尾遍历一遍，然后如果一个字符重复出现k的倍数次的话，那么这个键就是坏的。

但是这样做交了一发是错的。

后来一想，如果 k = 3，然后出现了aaaba这样一个字符串，那我们并不能仅仅凭a出现了3次就认为a是一个坏键，因为如果它是坏键，那么每一次它在字符串中出现的时候出现的次数都会是k的倍数。

所以思路就变得稍微复杂一些了，用c++ stl中的set来辅助一下，多遍历一遍，第一遍遍历，将出现了k的倍数次的字符放进set中，第二次遍历，如果该字符在set中，并且该字符在某处连续出现的次数不是k的倍数，就可以判断它肯定不是坏键，则要将其取出set。set中的元素表示的就是坏键。

最后再遍历一遍，按照这些字符在字符串中出现的顺序，将坏键放入数组中。

最后一遍遍历，输出原序列。也就是对于坏键，只输出一次，然后就跳过那些因为坏键而多输出的字符，继续输出下面的字符即可。

至于如何求某个字符在某个位置连续出现的长度，就像上一篇博客，天梯赛L1-058 6翻了 一样，从后往前扫一遍，如果s【i】 == s【i+1】，那么a【i】= a【i+1】，否则a【i】就直接等于1。

代码题解：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 100005;

const int INF = 0x3f3f3f3f;

int k,N,mlen = INF;

string s;

int a[1005];

char seq[1005],p[1005];

int cnt = 0,num = 0;

set<char> ss,aa;

int main(){

	#ifndef ONLINE_JUDGE

//		freopen("in.txt","r",stdin);

	#endif

	scanf("%d",&k);

	cin>>s;

	int len = s.length();

	a[len-1] = 1;

	for(int i=len-2;i>=0;i--){

		if(s[i] == s[i+1]) a[i] = a[i+1] + 1;

		else a[i] = 1;

	}

	for(int i=0;i<len;){

		if(a[i] % k == 0){

			aa.insert(s[i]);

			i += a[i];

		}

		else i++;

	}

	for(int i=0;i<len;){

		if(aa.count(s[i])){

			if( a[i] % k != 0 )

				aa.erase(s[i]);

			i += a[i];

		}

		else i++;

	}

	for(int i=0;i<len;){

		p[num++] = s[i];

		if(aa.count(s[i])){

			if(!ss.count(s[i])){

				ss.insert(s[i]);

				seq[cnt++] = s[i];

			}

			i += k;

		}

		else i++;

	}

	for(int i=0;i<cnt;i++){

		cout<<seq[i];

	}cout<<endl;

	for(int i=0;i<num;i++){

		cout<<p[i];

	}cout<<endl;

	return 0;

}

巴特西

PAT甲级 1112 Stucked Keyboard

最新文章

热门文章