寒假训练营2

D

这道题的题意很简单，有k张技能牌，每张技能牌可以把前\(a_i\)张牌放到最下边，消耗\(b_i\)的花费，现在我们需要的牌在从下往上的第k张，要变到第一张，花费最小的方式。建图的思路就有了，边权就是花费，也就是最短路问题，但是边很灵活，每个点都能建出m条边。

点击查看代码

void solve(long long kk) {
    priority_queue<PII,vector<PII>,greater<PII>>q;
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=n;i++){
        dist[i]=LLONG_MAX;
    }
    dist[k]=0;
    q.push({0,k});
    while(q.size()){
        auto [dis,dian]=q.top();
        q.pop();
        if(dist[dian]<dis)
            continue;
        for(int i=1;i<=m;i++){
            int jl=a[i],hf=b[i];
            jl+=dian;
            jl%=n;
            if(jl==0)
                jl=n;
            if(dist[jl]>hf+dis){
                dist[jl]=hf+dis;
                q.push({dist[jl],jl});
            }
        }
    }

    if(dist[n]==LLONG_MAX)
        cout<<-1<<endl;
    else
        cout<<dist[n]<<endl;
    return ;
}

codeforces 933 (Div.3)

E

F

天梯1

7-6

这题巨简单，但是问题出在了vector的size函数，这个函数的返回值不是int类型，所以要注意可能会出现x<ve.size()-1和x<=ve.size()两个公式不等价的情况。

7-11

这道题大一就做过，当时就没认真补题，现在遇到还是没思路，其实很简单，根据题意可知，这一定是树，也就是跑完树上的几个点之后不用返回起点，那想要最短路就是遍历所有路径之后减去最长的那条路。找最深的结点就是个dfs，那怎么计算出跑完所有点的路径和呢，那就是返回到当前点回到根节点的路径还有多少路径是没有走过的（因为之前的点可能被其他的点走过了，那就不用重复走了）。

点击查看代码

int fa[100010];
int vis[100010];
vector<int>g[100010];
int dp[100010];
void dfs(int x){
    for(auto e:g[x]){
        dp[e]=dp[x]+1;
        dfs(e);
    }
}
void solve(long long kk) {
    int n,m;
    cin>>n>>m;
    int root;
    for(int i=1;i<=n;i++){
        cin>>fa[i];
        if(fa[i]==-1){
            root=i;
        }
        else
            g[fa[i]].push_back(i);
    }
    dp[root]=0;
    dfs(root);
    int max1=0;
    int sum=0;
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        max1=max(max1,dp[x]);
        while(vis[x]==0&&x!=root){
            vis[x]=1;
            sum+=2;
            x=fa[x];
        }
        cout<<sum-max1<<endl;
    }
    return ;
}

7-12

这个题其实不难，就是一直不停的套map，因为这个明显也是树，但是可以优化的点是那些老人一定为叶子结点，那我们直接将一个管理机构下的老人数记作这个点的权值，在老人更换机构时就不用考虑边的问题了，直接更换双方的权值即可，求一个管理机构下的老人总数，就是以它为根节点的dfs搜索，权值求和就好，但是有一个段错误，不太懂问题在哪。

点击查看代码

map<pair<string,string>,int>d;
map<string,string>fa;
map<string,vector<string>>ve;
map<string ,int>xx;
int dfs(string s){
    int ans=xx[s];
    for(auto e:ve[s]){
        ans+=dfs(e);
        //cout<<e<<" "<<s<<" "<<ans<<endl;
    }
    return ans;
}
void solve(long long kk) {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        string s1,s2;
        cin>>s1>>s2;
        fa[s1]=s2;
        ve[s2].push_back(s1);
        if(s1[0]>='0'&&s1[0]<='9')
            xx[s2]++;
//        cout<<i<<" "<<s2<<" "<<xx[s2]<<endl;
//        for(auto e:ve[s2]){
//            cout<<e<<" ";
//        }
//        cout<<"-----\n";
        //fa[s1]=s2;
    }
    while(1){
        string s1;
        cin>>s1;
        if(s1=="E"){
            break;
        }
        if(s1=="T"){
            string s2,s3;
            cin>>s2>>s3;
            string ss=fa[s2];
            xx[ss]--;
            //cout<<ss<<" "<<s2<<" "<<s3<<endl;
            ve[s3].push_back(s2);
            fa[s2]=s3;
            xx[s3]++;
        }
        else if(s1=="Q"){
            string s2;
            cin>>s2;
            int ans=0;
            ans=dfs(s2);
            cout<<ans<<endl;
        }

    }
    return ;
}