NOIP2018 解题报告

D1T1 铺设道路

分析

这题就是NOIP2013 积木大赛原题=。=，贪心地想，如果 $a_i > a_{i-1}$ai​>ai−1​， $ans+=a_i-a_{i-1}$ans+=ai​−ai−1​，因为搞 $a_{i-1}$ai−1​ 的时候，能尽量搞 $a_i$ai​ 就搞 $a_i$ai​。

代码如下

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100001], max1, s;
int main(){
	int i, j, n, m;
	scanf("%d", &n);
	for(i=1;i<=n;i++) scanf("%d", &a[i]);
	for(i=1;i<=n;i++){
		if(a[i]>a[i-1]) s += a[i]-a[i-1];
	}
	printf("%d",s);
	return 0;
} 

D1T2 货币系统

分析

由于 $b$b 与 $a$a 等价且 $b$b 要尽量小，$b$b 肯定是 $a$a 的子集，其中对于 $x\in a,x \notin b$x∈a,x∈/​b，$x$x 能用 $b$b 中的元素表示。
于是我们将 $a$a 排个序跑个背包就可以了。

代码如下

#include <bits/stdc++.h>
using namespace std;
int f[25005], a[105], ans;
int main(){
	int i, j, n, m, T;
	scanf("%d", &T);
	while(T--){
		ans = 0;
		memset(f, 0, sizeof(f));
		scanf("%d", &n);
		for(i = 1; i <= n; i++) scanf("%d", &a[i]);
		sort(a + 1, a + i);
		f[0] = 1;
		for(i = 1; i <= n; i++){
			if(f[a[i]]) continue;
			ans++;
			for(j = a[i]; j <= 25000; j++) f[j] += f[j - a[i]];
		}
		printf("%d\n", ans);
	}
	return 0;
}

D1T3 赛道修建

分析

要求最小的最大，于是我们二分。
那怎么 $check$check 呢？
首先，如果是一条链的情况，明显就是长度到了 $t$t 就 $tot+1$tot+1。
于是我们从下往上每到一个分叉点，一定汇聚了多条长度小于 $t$t 的链，如图。

红色的是 $3$3 条未到 $t$t 的链，显然只有 $1$1 条可以继续往上延伸，其他链都要在这里进行合并。于是我们就对每个节点维护一个 $multiset$multiset，放置这些链。然后每次从这些链中贪心地合并，最后剩的最大那条链向上传递。这样我们就保证了长度大于 $t$t 的链总数尽量大。
总结就是这道题用了几个贪心：
第一个是单链上要贪心，第二个是合并的时候要贪心，第三个是传递的时候要贪心，这些贪心保证了解的最优性。

代码如下

#include <bits/stdc++.h>
#define N 50005
#define inf 2147483647
using namespace std;
struct node{
	int a, b, c, n;
}d[N * 2];
int h[N], cnt, n, m, t, f[N], tot;
int read(){
	int x, f = 1;
	char ch;
	while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
	x = ch - 48;
	while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
	return x * f;
}
void cr(int a, int b, int c){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a, int p){
	int i, j, b, c, ret = 0;
	multiset<int> s;
	set<int>::iterator it;
	for(i = h[a]; i; i = d[i].n){
		b = d[i].b;
		c = d[i].c;
		if(b == p) continue;
		dfs(b, a);
		if(f[b] + c >= t) tot++;
		else s.insert(f[b] + c);
	}
	while(!s.empty()){
		if(s.size() == 1){
			f[a] = max(f[a], *s.begin());
			break;
		}
		it = s.lower_bound(t - *s.begin());
		if(it == s.begin() && s.count(*it) == 1) it++;
		if(it == s.end()){
			f[a] = max(f[a], *s.begin());
			s.erase(s.begin());
		}
		else{
			tot++;
			//printf("%d %d\n", *it, *s.begin());
			s.erase(it);
			s.erase(s.begin());
		}
	}
}
int ok(int t){
	dfs(1, 1);
	if(tot >= m) return 1;
	return 0;
}
int main(){
	int i, j, a, b, c, l = inf, r = 0;
	scanf("%d%d", &n, &m);
	for(i = 1; i < n; i++){
		a = read(); b = read(); c = read();
		cr(a, b, c);
		cr(b, a, c);
		r += c;
		l = min(l, c);
	}
	r /= m;
	while(l < r){
		for(i = 1; i <= n; i++) f[i] = 0;
		tot = 0;
		t = l + r + 1 >> 1;
		if(ok(t)) l = t;
		else r = t - 1;
	}
	printf("%d", l);
	return 0;
}

D2T1 旅行

分析

这道题考的应该是边排序，首先对 $m = n$m=n 的情况，我们枚举断掉的边，那么问题就变成了 $m = n-1$m=n−1 的情况。我们考虑在 $O(n)$O(n) 复杂度下解决 $m = n - 1$m=n−1的情况。
应该不难发现，题目中所得到的序列就是树的 $dfs$dfs 序，我们要让字典序尽量小，只要让每个节点访问的点按从小到大排序就可以了。如何实现这个排序呢？
我的做法是先让所有边的出点按从小到大排序，然后单独对每个点再来加边（emmm我突然发现有点难说，大家看代码吧

代码如下

#include <bits/stdc++.h>
#define N 10005
using namespace std;
struct node{
	int a, b, c, n;
	bool operator < (const node & A) const{
		return b < A.b;
	}
}d[N], e[N], re[N];
int h[N], p[N], v[N], vis[N], n, cnt, ret, tot, ans[N];
int mp[5005][5005];
void cr(int a, int b){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void crr(int a, int b){
	e[++ret].a = a; e[ret].b = b; e[ret].n = p[a]; p[a] = ret;
}
void dfs(int a){
	int i, b;
	v[a] = 1;
	printf("%d ", a);
	for(i = h[a]; i; i = d[i].n){
		b = d[i].b;
		if(!v[b]) dfs(b);
	}
}
void dfs1(int a){
	int i, b;
	v[a] = 1;
	vis[++tot] = a;
	for(i = h[a]; i; i = d[i].n){
		b = d[i].b;
		if(mp[a][b]) continue;
		if(!v[b]) dfs1(b);
	}
}
void cmp(){
	int i, j;
	for(i = 1; i <= n; i++){
		if(vis[i] < ans[i]){
			for(j = 1; j <= n; j++) ans[j] = vis[j];
			return;
		}
		if(vis[i] > ans[i]) return;
	}
}
int main(){
	int i, j, m, a, b;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= m; i++){
		scanf("%d%d", &a, &b);
		re[i].a = a; re[i].b = b;
		e[++tot].a = a; e[tot].b = b;
		e[++tot].a = b; e[tot].b = a;
	}
	sort(e + 1, e + tot + 1);
	for(i = 1; i <= tot; i++){
		a = e[i].a; b = e[i].b;
		crr(a, b);
	}
	for(a = 1; a <= n; a++){
		for(i = p[a]; i; i = e[i].n){
			b = e[i].b;
			cr(a, b);
		}
	}
	if(m == n - 1) dfs(1);
	else{
		for(i = 1; i <= n; i++) ans[i] = n;
		for(i = 1; i <= m; i++){
			tot = 0;
			memset(v, 0, sizeof(v));
			a = re[i].a; b = re[i].b;
			mp[a][b] = mp[b][a] = 1;
			dfs1(1);
			if(tot == n) cmp();
			//printf("=====%d %d %d\n", tot, a, b);
			//for(j = 1; j <= n; j++) printf("%d ", vis[j]);
			//printf("\n");
			mp[a][b] = mp[b][a] = 0;
		}
		for(i = 1; i <= n; i++) printf("%d ", ans[i]);
	}
	return 0;
}

填数游戏和保卫王国我还不会QAQ