PAT 甲级 1112 Stucked Keyboard (20 分)

这种20分的题居然还磕绊了不少时间,还有四天考试了真慌啊…

思路:

1.提前分别将k个0-9、a-z、下划线组成的字符串存到以对应字符为key值的map里;
2.用字符串存储屏幕上的字符串,然后挨个遍历;
3.设置一个map,存储这个键有没有被卡住,默认为false;
4.每遍历到一个字符,如果以这个字符串开始的k个字符不等于k个这个字符,那么这个键就没有被卡住;若等于k个这个字符,那i+=k-1;
5.在整个字符串的后k-1个字符,我们可以认为它们都是没有卡住的,但是注意,比如第k-2个字符卡住,它也会打出字符到后k-1个,所以我们不能分开遍历字符串的两部分,放在一起遍历的话,第四点说到的i+=k-1可以避免这个问题;(别问我为什么这么啰嗦,问就是我在这吃亏了@_@)
6.最后遍历字符串,如果遍历到卡住的就输出,并以map标记它已经输出过,并且利用s.erase(i,k-1);来删除多余的,最后换行输出删完之后的字符串就好了;

代码:

#include<iostream>
#include<map>
#include<string>
using namespace std;
map<char,string> wds;
int k;
map<char,bool> safe,detected;
void initial(){	
	for(int i=0;i<=36;i++){
		string s;
		i==36?s.insert(0,k,'_'):s.insert(0,k,(i>=0&&i<=9)?i+'0':i-10+'a');
		wds[s[0]]=s;
	}
}
int main(){
	cin>>k;
	initial();
	string s;
	cin>>s;
	for(int i=0;i<s.length();i++){
		if(i<=s.length()-k){
			if(s.substr(i,k)!=wds[s[i]]) safe[s[i]]=true;
			if(s.substr(i,k)==wds[s[i]]) i+=k-1;
		}
		else safe[s[i]]=true;
	}
	for(int i=0;i<s.length();i++){
		if(!safe[s[i]]&&!detected[s[i]]){
			cout<<s[i];
			detected[s[i]]=true;
		}
		if(!safe[s[i]]) s.erase(i,k-1);
	}
	cout<<"
"+s;
	return 0;
}
原文地址:https://www.cnblogs.com/yuhan-blog/p/12309017.html