不说那么多，惊天水数据。

先推歌曲吧。

Problem A 玩具车

该题目为Codeforces545A原题，点击查看完整翻译

题面

Susie和他哥哥都很喜欢玩玩具车，今天他们将进行一场友谊赛。有$n$辆玩具车，每辆玩具车两两相撞，碰撞结果刚好组成了一个 $n \times n$的矩阵，$a_{i,j}$表示第$i$辆车与第$j$辆车的碰撞结果。在矩阵中只有五种数：

• $-1$：表示两辆车没有相撞（$-1$仅出现在对角线上）
• $0$：表示两辆车都没有被撞翻。
• $1$：表示第$i$辆车被撞翻了。
• $2$：表示第$j$辆车被撞翻了。
• $3$：表示两辆车都被撞翻了。

比赛结束后，Susie想知道有多少辆车没有被撞翻，具体是哪些车。

题解

统计每行$1$和$3$的个数，如果二者只要有其中之一，就意味着车翻了。

代码

#include <iostream>
#include <cstring>
#include <bitset>
using namespace std;
const int MAXN=1005;
int main(){
#ifndef OFF_LINE
    freopen("toy.in","r",stdin);
    freopen("toy.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    int n,ans=0;
    bitset<MAXN> vis;
    vis.set();
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int t;
            cin>>t;
            switch(t){
                case -1:
                case 0:
                    break;
                case 1:
                    vis.reset(i);
                    break;
                case 2:
                    vis.reset(j);
                    break;
                case 3:
                    vis.reset(i);
                    vis.reset(j);
                    break;
                default:
                    cerr<<"ERROR:"<<__LINE__<<endl;
            }
        }
    }    
    cout<<n+vis.count()-MAXN<<endl;
    for(int i=1;i<=n;i++){
        if(vis[i]){
            cout<<i<<" ";
        }
    }    
    cout<<endl;
    return 0;    
}

Problem B 花花的聚会

题面

花花住在H国。H国有$n$个城市，其中$1$号城市为其首都。城市间有$n-1$条道路。从任意一个城市出发，都可以沿着这些道路一路走到首都。事实上，从任何一个城市走到首都的路径是唯一的。

过路并不是免费的。想要通过某一条道路，你必须使用一次过路券。H国一共有$m$种过路券，每张过路券以三个整数表示：$v,k, w$，表示你可以在城市$v$以价格$w$买到一张过路券。这张券可以使用$k$次。这意味着，拿着这张券通过了$k$条道路之后，这张券就不能再使用了。

请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券，并且在所在的城市再买一张。

花花家在首都。他有$q$位朋友，他希望把这些朋友们都邀请到他家做客。所以他想要知道每位朋友要花多少路费。他的朋友们都很聪明，永远都会选择一条花费最少的方式到达首都。花花需要准备晚餐去了，所以他没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么？

题解

题意

有一棵$n$个节点的有根树，在某些节点$v_i$，可以选择花费$w_i$的代价，向上跳$[1,k_i]$步。现有$q$个询问，询问一些节点跳到根的最少代价。

解法

不难发现，我们可以用动态规划的思想来解决这个问题。记$f_u$为$u$跳到根的最少代价。则不难得出转移方程：$f_u=minff[v]+wig$，其中$v$是$u$的祖先，且存在一种车票$u_i,w_i,k_i$并满足$dep[u] - dep[v] \leq ki$。这个DP方程的边界条件为$f_{root} = 0$。这样对于每种车票，我们可以暴力枚举所有合法的$v$，从而求得答案。优化该解法的DP转移。事实上我们只需在较快的时间内求得树上某一段区间的$minff[u]g$，即可较好地解决这个问题。而维护树上区间最值有树链剖分、动态树等许多数据结构能够胜任。在这里我们考虑用倍增的思想，维护$u$往上跳$2^i$步到的祖先$v$和$u$到$v$这一段$f$值的最小值，这样我们对于每一个节点$u$可以在$O(log_2n)$的时间内求得$minff[v]g$。时间复杂度为O(nlogn)，期望得分100 分。

代码

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
const int MAXN=100005;
struct Edge{
    int v;
    int next;
};
int head[MAXN],cnt,fat[MAXN],dp[MAXN];
vector<pair<int,int>> vec[MAXN];
Edge e[MAXN<<1];
void addedge(int u,int v){
    cnt++;
    e[cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void pre_dfs(int u=1,int fa=0){
    fat[u]=fa;
    for(int i=head[u];i;i=e[i].next){
        if(fa!=e[i].v){
            pre_dfs(e[i].v,u);
        }
    }
}
int dfs(int n){
    int ans=INT_MAX;
    if(dp[n]||n==1){
        return dp[n];
    }
    for(unsigned int i=0;i<vec[n].size();i++){ 
        int now=INT_MAX,x;
        x=fat[n];
        for(int j=1;j<=vec[n][i].first;j++){
            now=min(now,dfs(x));
            x=fat[x];
        }
        ans=min(ans,now+vec[n][i].second);
    }
    return dp[n]=ans;
}
int main(){
#ifndef OFF_LINE
    freopen("party.in","r",stdin);
    freopen("party.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    int n,m,q;
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        addedge(a,b);
        addedge(b,a);
    }
    pre_dfs();
    for(int i=0;i<m;i++){
        int v,k,w;
        cin>>v>>k>>w;
        vec[v].push_back(make_pair(k,w));
    }
    cin>>q;
    while(q--){
        int fr;
        cin>>fr;
        cout<<dfs(fr)<<endl;
    }
    return 0;
}

Problem C 送信

题面

小明是一名邮递员，他工作的城市被分为$n$个区域，由$n-1$土路连接，小明的公司在$1$号区域，接下来的日子里他有$m$个送信任务。由于城市化的推进，小明所在的城市计划将所有道路都改造成公路，所以小明不得不在他送信的途中走一些公路或土路。小明每次送信都是从邮局出发将信送到某个地方，他想知道每次送信的过程中走过的土路条数。

题解

裸的DFS序，博主也很无语，为啥一群大佬写树链剖分？

代码

#include <iostream>
using namespace std;
const int MAXN=250005;
struct Edge{
    int v;
    int next;
};
int head[MAXN],cnt,dfs_clock,l[MAXN],r[MAXN],dep[MAXN];
Edge e[MAXN<<1];
void addedge(int u,int v){
    cnt++;
    e[cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u=1,int fa=0){
    dep[u]=dep[fa]+1;
    l[u]=++dfs_clock;
    for(int i=head[u];i;i=e[i].next){
        if(fa!=e[i].v){
            dfs(e[i].v,u);
        }
    }
    r[u]=dfs_clock;
}
int sum[MAXN];
int lowbit(int x){
    return x&-x;
}
void add(int pos,int num=1){
    for(int i=pos;i<=dfs_clock;i+=lowbit(i)){
        sum[i]+=num;
    }
}
int query(int pos){
    int ans=0;
    for(int i=pos;i>0;i-=lowbit(i)){
        ans+=sum[i];
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        addedge(a,b);
        addedge(b,a);
    }
    dfs();
    cin>>m;
    for(int i=n+m-1;i>0&&m!=0;i--){
        char c;
        int x,y;
        cin>>c;
        switch(c){
            case 'A':
                cin>>x>>y;
                if(dep[x]>dep[y]){
                    swap(x,y);
                }
                add(l[y]);
                add(r[y]+1,-1);
                break;
            case 'W':
                cin>>x;
                cout<<dep[x]-query(l[x])-1<<endl;
                m--;
                break;
            default:
                cerr<<"ERROR:"<<__LINE__<<endl;
        }
    }
    return 0;
}

版权属于：来自星星的薇薇安

本文链接：https://www.starroad.top/archives/426.html

如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！