不说那么多，惊天水数据。
先推歌曲吧。
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.ariels.xyz/archives/426.html
本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。
