题解：UVA12936 Hehe

这是一道~~可癌的~~红黑树与字符串组合题。

前置知识

map
string

思路

黄题肯定不能写红黑树，我们可以使用 map，可以把每组人的字符串为键，说的话为值，存入 map 中，然后最后遍历 map，判断值是否满足条件，如果满足，那么 ans ++，无论满不满足，都要 cnt ++，答案转化成小数就是

ans \div cnt

，再转化成百分数形式即可。

时间复杂度为

O(nm)

，

n

为组数，

m

为话的长度，还要加上 map 的时间复杂度

(\log n)

，但是因为没有

nm

大，所以不考虑。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
string str,name,info,a,b,rev;
map<string,string> mp;
map<string,bool> vis;
int pos,tmp,ans,cnt;
bool check(string str){
	int siz = str.size();
	if(siz < 4){
		return false;
	}
	for(int i = 0;i < siz;i ++){
		if(str[i] != 'h' and str[i] != 'e'){
			return false;
		}
		if(str[i] == 'h' and (i != 0 and str[i - 1] != 'e')){
			return false;
		}
		if(str[i] == 'e' and (i == 0 or str[i - 1] != 'h')){
			return false;
		}
	}
	if(str[siz - 1] != 'e'){
		return false;
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while(getline(cin,str)){
		pos = str.find(':');
		name = str.substr(0,pos);
		info = str.substr(pos + 2);
		for(char &c : info){
			if(c >= 'A' and c <= 'Z'){
				c = c - 'A' + 'a';
			}
		}
		if(vis[name] == true){
			mp[name] = info;
		}else{
			tmp = str.find("->");
			a = str.substr(0,tmp);
			b = str.substr(tmp + 2,pos - tmp - 2);
			rev = b + "->" + a;
			mp[rev] = info;
			vis[rev] = true;
		}
	}
	for(auto i : mp){
		cnt ++;
		str = "";
		for(char c : i.second){
			if(c >= 'a' and c <= 'z'){
				str += c;
			}else{
				ans += check(str);
				str = "";
			}
		}
		ans += check(str);
	}
	cout << fixed << setprecision(0) << (ans * 1.0) / (cnt * 1.0) * 100.0 << "%\n";
	return 0;
}

文章操作

前置知识

思路

Code

相关推荐

评论

题解：UVA12936 Hehe