题解：UVA12936 Hehe

· · 题解

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

前置知识

思路

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

时间复杂度为 O(nm)，n 为组数，m 为话的长度，还要加上 map 的时间复杂度 (\log n)，但是因为没有 nm 大，所以不考虑。

Code

#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;
}