NOIP2016解题报告

程序员文章站 2022-04-27 13:06:17

...

D1T1 玩具谜题

分析

直接模拟即可

代码如下

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char s[100003][11];
int a[100003];
int main(){
	int i, j, n, m, t = 1, w;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++){
		scanf("%d%s", &a[i], s[i]);
	}
	for(i = 1; i <= m; i++){
		scanf("%d%d", &j, &w);
		if(!(j ^ a[t])) t = (t - w + n - 1) % n + 1;
		else t = (t + w - 1) % n + 1;
	}
	printf("%s", s[t]);
	return 0;
}

D2T2 天天爱跑步

分析

一条链总是由上去和下来两部分组成。
这题我们分两种情况思考。
第一种：上去的时候被观察到
第二种：下来的时候被观察到

我们先来看第一种情况，不难发现，一个点 $t$ 被某一个观察员 $i$ 观察到需满足
$dep_t = dep_i + w_i$ ，这样一来我们统计每个观察员 $i$ 能观察到多少从下面上来的人只需要看 $i$ 的子树中有多少 $dep_j=dep_i+w_i$ 的即可。（被统计的前提当然是那条链经过 $i$ ）

下面来看第二种情况。大概长这样。
NOIP2016解题报告
首先我们为了方便统计，一般都是统计子树中的值。
那么我们怎么看观察员 $i$ 能统计到多少下来的人呢？
推一推柿子，可以看到 $len-(dep_y-dep_i)=w_i\Rightarrow len-dep_y=w_i-dep_i$ ，这样我们只要统计 $i$ 的子树中有多少 $len - dep_y=w_i-dep_i$ 的值就可以了。

于是我们的思路就出来了。
下面思考一下怎么统计。

第一种做法是用桶型线段树。对每个深度维护一颗线段树，最后对每个观察员 $i$ 统计 $i$ 能观察到多少人。

第二种做法是用 $dfs$ ， $dfs$ 的过程中维护一个桶，每次路过端点时 $tong[dep[x]]+1$ ，路过 $lca$ 时 $tong[dep[x]]-1$ ，这样我们就能一遍 $dfs$ 完成统计。这种做法关键在于从每个点 $dfs$ 相当于是遍历子树，也就是在进行统计的过程，回溯回来，说明统计已经结束了。

给出的代码是用桶型线段树的（比较好打hhh

代码如下

#include <bits/stdc++.h>
#define lson l, m, lch[rt]
#define rson m + 1, r, rch[rt]
#define N 300005
using namespace std;
struct node{
	int a, b, n;
}d[N * 2];
int h[N], cnt, ret, tot;
int fa[N], son[N], dfn[N], siz[N], dep[N], top[N], re[N], w[N];
int x[N], y[N], lca[N], len[N], ans[N];
int root[N * 10], lch[N * 30], rch[N * 30], sum[N * 30];
void cr(int a, int b){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs1(int a){
	int i, b;
	siz[a] = 1;
	for(i = h[a]; i; i = d[i].n){
		b = d[i].b;
		if(b == fa[a]) continue;
		fa[b] = a;
		dep[b] = dep[a] + 1;
		dfs1(b);
		siz[a] += siz[b];
		if(siz[b] > siz[son[a]]) son[a] = b;
	}
}
void dfs2(int a, int f){
	int i, b;
	top[a] = f;
	dfn[a] = ++tot; re[tot] = a;
	if(son[a]) dfs2(son[a], f);
	for(i = h[a]; i; i = d[i].n){
		b = d[i].b;
		if(b != son[a] && b != fa[a]) dfs2(b, b);
	}
}
int get(int a, int b){
	int f1 = top[a], f2 = top[b];
	while(f1 != f2){
		if(dep[f1] < dep[f2]) swap(f1, f2), swap(a, b);
		a = fa[f1], f1 = top[a];
	}
	if(dep[b] < dep[a]) return b;
	return a;
}
void update(int l, int r, int &rt, int p,  int c){
	if(!p) return; 
	if(!rt) rt = ++ret;
	sum[rt] += c;
	if(l == r) return;
	int m = l + r >> 1;
	if(p <= m) update(lson, p, c);
	else update(rson, p, c);
}
int query(int l, int r, int rt, int a, int b){
	if(!rt) return 0;
	if(l >= a && r <= b) return sum[rt];
	int m = l + r >> 1, ans = 0;
	if(a <= m) ans += query(lson, a, b);
	if(b > m) ans += query(rson, a, b);
	return ans;
}
int main(){
	int i, j, n, m, a, b;
	scanf("%d%d", &n, &m);
	for(i = 1; i < n; i++){
		scanf("%d%d", &a, &b);
		cr(a, b);
		cr(b, a);
	}
	dfs1(1);
	dfs2(1, 1);
	for(i = 1; i <= n; i++) scanf("%d", &w[i]);
	for(i = 1; i <= m; i++){
		scanf("%d%d", &x[i], &y[i]);
		lca[i] = get(x[i], y[i]);
		len[i] = dep[x[i]] + dep[y[i]] - 2 * dep[lca[i]];
		update(1, n, root[dep[x[i]]], dfn[x[i]], 1);
		update(1, n, root[dep[x[i]]], dfn[fa[lca[i]]], -1);
	}
	//printf("---------\n");
	//for(i = 1; i <= m; i++) printf("%d ", lca[i]);
	for(i = 1; i <= n; i++) ans[i] += query(1, n, root[dep[i] + w[i]], dfn[i], dfn[i] + siz[i] - 1);
	//for(i = 1; i <= m; i++) printf("%d ", len[i]);
	//printf("\n");
	memset(sum, 0, sizeof(sum));
	memset(root, 0, sizeof(root));
	memset(lch, 0, sizeof(lch));
	memset(rch, 0, sizeof(rch));
	for(i = 1; i <= m; i++){
		update(1, n, root[len[i] - dep[y[i]] + N], dfn[y[i]], 1);
		update(1, n, root[len[i] - dep[y[i]] + N], dfn[lca[i]], -1);
	}
	for(i = 1; i <= n; i++) ans[i] += query(1, n, root[w[i] - dep[i] + N], dfn[i], dfn[i] + siz[i] - 1);
	for(i = 1; i <= n; i++) printf("%d ", ans[i]);
	return 0;
}

D1T3 换教室

分析

这题作为 $noip$ 第一次出的期望题，可能重点不在于 $dp$ ，而在于考察选手对期望的理解吧。
首先 $floyd$ 预处理出任意两点间的最小路程，需注意的是 $mp[i][i] =0$
然后记 $f[i][j][0/1]$ 表示到了第 $i$ 节课，总共换了 $j$ 节，第 $i$ 节换不换的最小期望。分别对 $f[i][j][0]$ 和 $f[i][j][1]$ 进行转移，转移对第 $i-1$ 节课是否换课进行讨论即可。

代码如下

#include <bits/stdc++.h>
#define N 2005
#define maxn 90000000
#define inf 2147483647
using namespace std;
int c[N], d[N], mp[305][305];
double k[N], f[N][N][2], ans = inf;
int main(){
	int i, j, t, n, m, v, e, a, b;
	for(i = 1; i <= 300; i++){
		for(j = 1; j <= 300; j++){
			mp[i][j] = 30000000;
		}
	}
	scanf("%d%d%d%d", &n, &m, &v, &e);
	for(i = 1; i <= n; i++) scanf("%d", &c[i]);
	for(i = 1; i <= n; i++) scanf("%d", &d[i]);
	for(i = 1; i <= n; i++) scanf("%lf", &k[i]);
	for(i = 1; i <= e; i++){
		scanf("%d%d%d", &a, &b, &t);
		if(mp[a][b] > t) mp[a][b] = mp[b][a] = t;
	}
	for(i = 1; i <= v; i++) mp[i][i] = 0;
	for(t = 1; t <= v; t++){
		for(i = 1; i <= v; i++){
			for(j = 1; j <= v; j++){
				mp[i][j] = min(mp[i][j], mp[i][t] + mp[t][j]);
			}
		}
	}
	for(i = 0; i <= 2000; i++)
		for(j = 0; j <= 2000; j++) f[i][j][0] = f[i][j][1] = maxn;
	f[1][0][0] = f[1][1][1] = 0;
	for(i = 2; i <= n; i++){
		f[i][0][0] = f[i - 1][0][0] + mp[c[i - 1]][c[i]];
		for(j = 1; j <= m; j++){
			f[i][j][0] = min(f[i - 1][j][0] + mp[c[i - 1]][c[i]], f[i - 1][j][1] + k[i - 1] * mp[d[i - 1]][c[i]] + (1 - k[i - 1]) * mp[c[i - 1]][c[i]]);
			f[i][j][1] = min(f[i - 1][j - 1][0] + k[i] * mp[c[i - 1]][d[i]] + (1 - k[i]) * mp[c[i - 1]][c[i]], f[i - 1][j - 1][1] + k[i] * k[i - 1] * mp[d[i - 1]][d[i]] + k[i] * (1 - k[i - 1]) * mp[c[i - 1]][d[i]] + (1 - k[i]) * k[i - 1] * mp[d[i - 1]][c[i]] + (1 - k[i]) * (1 - k[i - 1]) * mp[c[i - 1]][c[i]]);
		}
	}
	for(i = 0; i <= m; i++) ans = min(ans, min(f[n][i][0], f[n][i][1]));
	printf("%.2lf", ans);
	return 0;
}

D2T1 组合数问题

分析

注意到 $k$ 是对每个询问的。于是我们想到预处理。直接预处理出 $c[i][j]$ 是否是
$k$ 的倍数，然后用二维前缀和即可 $O(1)$ 回答询问。

代码如下

#include <bits/stdc++.h>
#define N 2005
using namespace std;
int c[N][N], s[N][N];
int main(){
	int i, j, n, m, t, k;
	scanf("%d%d", &t, &k);
	for(i = 0; i <= 2000; i++){
		c[i][0] = 1;
		for(j = 1; j <= i; j++){
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
			if(!c[i][j]) s[i][j] = 1;
			//printf("%d %d %d\n", i, j, s[i][j]);
		}
		if(i > 1)
		for(j = 1; j <= 2000; j++){
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	}
	while(t--){
		scanf("%d%d", &n, &m);
		if(m > n) m = n;
		printf("%d\n", s[n][m]);
	}
	return 0;
}

D2T2 蚯蚓

分析

做这题最暴力的想法是用优先队列（或者不用），每次把最长的切成两段，然后把所有蚯蚓取出来加 $q$ 。
然后不难注意到，不切的蚯蚓之间的相对长度是不变的，每次都加 $q$ 很不好。我们只需要将切出来的两段减 $q$ 就好了。然后再用优先队列可以达到 $80pts$ 。
讲讲正解。
维护三个有序数组。
首先将蚯蚓从大到小排序，每次切出来的两条新蚯蚓分别放入另外两个数组。不难发现，这样出来的三个数组都是从大到小有序的。我们每次只需要从 $3$ 个数组的队首比较取出最大值咔咔掉即可。
复杂度是线性的。

代码如下

#include <bits/stdc++.h>

#define N 7000005
#define LL long long
#define inf 2147483647
using namespace std;
LL a[N], b[N], c[N];
int p1, q1, p2, q2, p3, q3;
LL z = 1, maxn;
int cmp(int x, int y){
	return x > y;
}
int main(){
	int i, j, n, m, q, u, v, t;
	int p;
	scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
	for(i = 1; i <= n; i++) scanf("%lld", &a[i]);
	sort(a + 1, a + i, cmp);

	p1 = p2 = p3 = 1, q1 = n;
	for(i = 1; i <= m; i++){
		maxn = -inf;
		if(p1 <= q1 && maxn < a[p1]) p = 1, maxn = a[p1];
		if(p2 <= q2 && maxn < b[p2]) p = 2, maxn = b[p2];

		if(p3 <= q3 && maxn < c[p3]) p = 3, maxn = c[p3];
		maxn += (i - 1) * q;
		if(i % t == 0) printf("%lld ", maxn);
		b[++q2] = maxn * u / v - i * q;
		c[++q3] = maxn - maxn * u / v - i * q;
		if(p == 1) p1++;
		if(p == 2) p2++;
		if(p == 3) p3++;
		//printf("%d %d %d\n", p1, p2, p3);
	}
	//printf("====%d %d\n====%d %d\n====%d %d\n", p1, q1, p2, q2, p3, q3); 
	printf("\n");
	for(i = 1; ; i++){
		if(p1 > q1 && p2 > q2 && p3 > q3) break;

		maxn = -inf;
		if(p1 <= q1 && maxn < a[p1]) p = 1, maxn = a[p1];
		if(p2 <= q2 && maxn < b[p2]) p = 2, maxn = b[p2];

		if(p3 <= q3 && maxn < c[p3]) p = 3, maxn = c[p3];
		if(i % t == 0) printf("%lld ", maxn + m * q);
		if(p == 1) p1++;
		if(p == 2) p2++;
		if(p == 3) p3++;
	}
	return 0;
}

D2T3 愤怒的小鸟

分析

首先我们可以不管给出的 $m$ ，因为我们用 $n$ 只小鸟肯定可以打完，不存在无解的情况，出题人给出来是为了某些同学写搜索剪枝用的。
然后我们回到题目。注意到 $n$ 很小，考虑状压。
一条抛物线肯定由两只小猪连成，我们可以用 $g[i][j]$ 表示 $i,j$ 这两只小猪连成的抛物线能打到的小猪集合。我们用 $f[s]$ 表示打到的小猪集合为 $s$ 时用的最少抛物线。枚举 $i,j$ ，那么转移方程为：
$f[s] = min(f[s$ ^ $(s$ & $g[i][j])]+1)$ ，就是先取 $s$ 和 $g[i][j]$ 的交集，然后咔咔掉。这样子复杂度时 $O(n^2*2^n)$ 的，能不能更优呢？当然可以。
我们每条抛物线之间时没有先后顺序的，那么我们就可以让最后一只猪作为抛物线的一个点，然后枚举另一只猪作为另一个点，这样复杂度就是 $O(n*2^n)$ 的。

代码如下

//f[s] = min(f[s ^ g[i][j]] + 1)
#include <bits/stdc++.h>
#define eps 1e-6
using namespace std;
int f[1 << 20], g[20][20], re[1 << 20];
double a, b, x[20], y[20];
double get(double x1, double y1, double x2, double y2){
	return (y1 - y2 * x1 / x2) / (x1 * x1 - x1 * x2);
}
int main(){
	int i, j, k, n, m, T, s;
	
	for(i = 0; i < 20; i++) re[1 << i] = i;
	//printf("%d", re[4]);
	scanf("%d", &T);
	while(T--){
		memset(f, 1, sizeof(f));
		memset(g, 0, sizeof(g));
		scanf("%d%d", &n, &m);
		for(i = 0; i < n; i++) scanf("%lf%lf", &x[i], &y[i]);
		for(i = 0; i < n; i++){
			for(j = i + 1; j < n; j++){
				if(fabs(x[i] - x[j]) < eps) continue;
				a = get(x[i], y[i], x[j], y[j]);
				if(a > -eps) continue;
				b = (y[i] - a * x[i] * x[i]) / x[i];
				for(k = 0; k < n; k++){
					if(fabs(y[k] - a * x[k] * x[k] - b * x[k]) < eps) g[i][j] |= (1 << k);
				}
				//printf("%d %d %d\n", i, j, g[i][j]);
			}
		}
		f[0] = 0;
		for(s = 1; s < (1 << n); s++){
			j = re[s&-s];
			f[s] = min(f[s], f[s ^ (1 << j)] + 1);
			for(i = j + 1; i < n; i++){
				if(1 << i & s) f[s] = min(f[s], f[s ^ (s & g[j][i])] + 1);
			}
		}
		printf("%d\n", f[(1 << n) - 1]);
	}
	return 0;
}

上一篇：如何判断网红营销是否符合自己

下一篇：唯美内敛的古代爱情诗词

NOIP2016解题报告

D1T1 玩具谜题

分析

代码如下

D2T2 天天爱跑步

分析

代码如下

D1T3 换教室

分析

代码如下

D2T1 组合数问题

分析

代码如下

D2T2 蚯蚓

分析

代码如下

D2T3 愤怒的小鸟

分析

代码如下

2018技术与创新报告：前沿技术区块链对可持续发展存在潜在贡献

MySQL上机实习报告（一）

生成Oracle的AWR报告

平板市场二季度报告：苹果iPad依然无敌、头部厂商出货均实现两位数增长

报告：苹果降低iPhone出货量安卓手机厂商忙着清库存

会声会影X7好用吗？最新会声会影X7使用评测报告

爱分析《数据智能行业报告》发布解析集奥聚合缘何在政务场景快速落地

python selenium执行所有测试用例并生成报告的方法

一份ASP内存的释放的实验报告

中国区块链技术和应用发展研究报告（2018）编写会议在昆明召开

NOIP2016解题报告

D1T1 玩具谜题

分析

代码如下

D2T2 天天爱跑步

分析

代码如下

D1T3 换教室

分析

代码如下

D2T1 组合数问题

分析

代码如下

D2T2 蚯蚓

分析

代码如下

D2T3 愤怒的小鸟

分析

代码如下

2018技术与创新报告：前沿技术区块链对可持续发展存在潜在贡献

MySQL上机实习报告（一）

生成Oracle的AWR报告

平板市场二季度报告：苹果iPad依然无敌、头部厂商出货均实现两位数增长

报告：苹果降低iPhone出货量 安卓手机厂商忙着清库存

会声会影X7好用吗？最新会声会影X7使用评测报告

爱分析《数据智能行业报告》发布 解析集奥聚合缘何在政务场景快速落地

python selenium执行所有测试用例并生成报告的方法

一份ASP内存的释放的实验报告

中国区块链技术和应用发展研究报告（2018）编写会议在昆明召开

报告：苹果降低iPhone出货量安卓手机厂商忙着清库存

爱分析《数据智能行业报告》发布解析集奥聚合缘何在政务场景快速落地