8.19小红书笔试AK

1、模拟，对输入的单词进行计数&判断是否可以记忆即可。

#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cnt=1;
    unordered_map<string, int>mp;
    unordered_set<string>se;
    for(int i=0; i<n; i++){
        string s;
        cin>>s;
        mp[s]++;
        //  背诵次数大于等于cnt时可以记忆，并更新下个单词需要记忆的次数。
        if(mp[s]>=cnt&&!se.count(s)){
            se.insert(s);
            cnt++;
        }
    }
    cout<<se.size()<<endl;
    return 0;
}

2、字符串替换，有2个坑，不加传递关系只能a18%：既然n和u可以相互替换，m可以拆分成两个n，那么m也可以拆分成两个u，即替换关系是可以传递的；其次，根据传递关系，b，d，p，q两两之间也是等价的。

#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
using namespace std;
unordered_map<string, unordered_map<string, bool> >mp;
bool check(string s){
    int l=0, r=s.length()-1;
    while(l<r){
        if(s[l]!=s[r]){
            string ll = "";
            ll+=s[l];
            string rr = "";
            rr+=s[r];
            if(mp[ll][rr]||mp[rr][ll]){
                l++;
                r--;
                continue;
            }
            if(ll=="w"||ll=="m"){
                if(ll=="w"&&s[r]=='v'){
                    s[l]='v'; // w拆分成两个v，l指针不需要移动，并修改为v
                    r--;
                    continue;
                }
                if(ll=="m"&&s[r]=='n'){
                    s[l]='n';
                    r--;
                    continue;
                }
                if(ll=="m"&&s[r]=='u'){
                    s[l]='u';
                    r--;
                    continue;
                }
            }
            if(rr=="w"||rr=="m"){
                if(rr=="w"&&s[l]=='v'){
                    l++;
                    s[r]='v';
                    continue;
                }
                if(rr=="m"&&s[l]=='n'){
                    l++;
                    s[r]='n';
                    continue;
                }
                if(rr=="m"&&s[l]=='u'){
                    l++;
                    s[r]='u';
                    continue;
                }
            }
            return false;
        }
        else{
            l++;
            r--;
        }
    }
    return true;
}
int main(){
    mp["w"]["vv"]=1;
    mp["m"]["nn"]=1;
    
    mp["b"]["d"]=1;
    mp["b"]["q"]=1;
    mp["b"]["p"]=1;
    
    mp["d"]["p"]=1;
    mp["d"]["q"]=1;

    mp["p"]["q"]=1;
    
    mp["n"]["u"]=1;
    mp["uu"]["m"]=1;
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        string s;
        cin>>s;
        bool ok = check(s);
        if(ok)puts("YES");
        else puts("NO");
    }
    
    return 0;
}

3、直接dfs搜索即可，首先，注意cost>k或者超过3个城市就return，其次，结果需要用long long存储。

#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
using namespace std;
const int N=1e5+5;
int n, m, k;
int a[N], h[N], vis[N];
struct Edge{
    int to;
    int w;
    Edge(){
    }
    Edge(int _to, int _w){
        to=_to;
        w=_w;
    }
};
vector<Edge>edges[N];
long long ans;
void dfs(int cur, long long value, int cost, int depth){
    if(cost>k||depth>3)return;
    ans=max(ans, value);
    for(int i=0; i<edges[cur].size(); i++){
        Edge edge = edges[cur][i];
        if(vis[edge.to])continue;
        vis[edge.to]=1;
        dfs(edge.to, value+a[edge.to], cost+h[edge.to]+edge.w,depth+1);
        vis[edge.to]=0;
    }
}
int main(){
    
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    } 
    for(int i=1; i<=n; i++){
        cin>>h[i];
    }  
    for(int i=0; i<m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        edges[u].push_back(Edge(v,w));
        edges[v].push_back(Edge(u,w));
    }


    for(int i=1; i<=n; i++){
        vis[i]=1;
        dfs(i,a[i],h[i],1);
        vis[i]=0;
    }
    cout<<ans<<endl;
    return 0;
}