CWOI 2019 NOIP 暑假测试六

Author：薇薇安
发布时间：July 25, 2019
252views
No comments
1441 words
Categories：题解

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

先推歌曲吧。

## Problem A 玩具车

该题目为[Codeforces545A](http://codeforces.com/problemset/problem/545/A)原题，点击查看完整[翻译](https://www.luogu.org/problem/CF545A)

### 题面

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

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

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

### 题解

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

### 代码

```cpp
#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 分。

### 代码

```cpp
#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`序，博主也很无语，为啥一群大佬写树链剖分？

### 代码

```cpp
#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;
}
```

<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/426.html">https://www.starroad.top/archives/426.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote>

Last modification：July 26th, 2019 at 11:09 am

如果您觉得我的文章有用，给颗糖糖吧~