zoom 8.10 笔试

zoom 8.10 笔试

第一题就是建树 dfs一边

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace  std;
using ll= long long;
using pii =pair<int,int> ;

const int N=1e5+10;

int n;
char str[N];
int h[N],e[N<<1],ne[N<<1],idx;
bool st[N];

void add(int x,int y){
    e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}

struct Node{
    int id,x,y;
};

ll bfs(){
    ll res=0;
    queue<Node> q;
    q.push({1,0,0});
    while(q.size()){
        auto cur=q.front();q.pop();
        if(st[cur.id]) continue;
        if(str[cur.id]=='R') cur.x++;
        else cur.y++;
        res+=abs(cur.x-cur.y);
        st[cur.id]=true;
        for(int i=h[cur.id];~i;i=ne[i]){
            int v=e[i];
            if(st[v]) continue;
            q.push({v,cur.x,cur.y});
        }
    }
    return res;
}


int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>str[i];
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        add(x,y),add(y,x);
    }

    cout<<bfs()<<endl;
    return 0;
}

第二题 并查集 记录下连通块大小即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace  std;
using ll= long long;
using pii =pair<int,int> ;

const int N=1e5+10;

int n,m;

unordered_map<string,int> name;
unordered_map<string ,vector<int>> h;

int f[N],si[N];
int idx=0;

int get(int x){
    if(x!=f[x]) f[x]=get(f[x]);
    return f[x];
}

void merge(int x,int y){
    int fx=get(x),fy=get(y);
    if(fx!=fy) {
        f[fx]=fy;
        si[fy]+=si[fx];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>m;

    for(int i=1;i<N;i++) {
        f[i]=i;
        si[i]=1;
    }

    while(m--){
        int op;
        cin>>op;
        string s;
        if(op==1){
            cin>>s>>n;
            for(int i=0;i<n;i++){
                string t;
                cin>>t;
                if(name.count(t)) h[s].push_back(name[t]);
                else {
                    name[t]=++idx;
                    h[s].push_back(name[t]);
                }
            }
            for(int i=0;i<h[s].size()-1;i++){
                merge(h[s][i],h[s][i+1]);
            }
        }else if(op==2) {
            cin>>s;
            if(!h.count(s)) cout<<"error"<<endl;
            else{
                int fx=get(h[s][0]);
                cout<<si[fx]-h[s].size()<<endl;
            }
        }
    }
    return 0;
}