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 t t 被某一个观察员 i i i 观察到需满足
d e p t = d e p i + w i dep_t = dep_i + w_i dept=depi+wi,这样一来我们统计每个观察员 i i i 能观察到多少从下面上来的人只需要看 i i i 的子树中有多少 d e p j = d e p i + w i dep_j=dep_i+w_i depj=depi+wi 的即可。(被统计的前提当然是那条链经过 i i i

下面来看第二种情况。大概长这样。

首先我们为了方便统计,一般都是统计子树中的值。
那么我们怎么看 观察员 i i i 能统计到多少下来的人呢?
推一推柿子,可以看到 l e n ( d e p y d e p i ) = w i l e n d e p y = w i d e p i len-(dep_y-dep_i)=w_i\Rightarrow len-dep_y=w_i-dep_i len(depydepi)=wilendepy=widepi,这样我们只要统计 i i i 的子树中有多少 l e n d e p y = w i d e p i len - dep_y=w_i-dep_i lendepy=widepi的值就可以了。

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

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

第二种做法是用 d f s dfs dfs d f s dfs dfs 的过程中维护一个桶,每次路过端点时 t o n g [ d e p [ x ] ] + 1 tong[dep[x]]+1 tong[dep[x]]+1,路过 l c a lca lca t o n g [ d e p [ x ] ] 1 tong[dep[x]]-1 tong[dep[x]]1,这样我们就能一遍 d f s dfs dfs 完成统计。这种做法关键在于从每个点 d f s 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 换教室

分析

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

代码如下

#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 k k 是对每个询问的。于是我们想到预处理。直接预处理出 c [ i ] [ j ] c[i][j] c[i][j] 是否是
k k k 的倍数,然后用二维前缀和即可 O ( 1 ) O(1) 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
然后不难注意到,不切的蚯蚓之间的相对长度是不变的,每次都加 q q q 很不好。我们只需要将切出来的两段减 q q q 就好了。然后再用优先队列可以达到 80 p t s 80pts 80pts
讲讲正解。
维护三个有序数组。
首先将蚯蚓从大到小排序,每次切出来的两条新蚯蚓分别放入另外两个数组。不难发现,这样出来的三个数组都是从大到小有序的。我们每次只需要从 3 3 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 m m,因为我们用 n n n 只小鸟肯定可以打完,不存在无解的情况,出题人给出来是为了某些同学写搜索剪枝用的。
然后我们回到题目。注意到 n n n 很小,考虑状压。
一条抛物线肯定由两只小猪连成,我们可以用 g [ i ] [ j ] g[i][j] g[i][j] 表示 i , j i,j i,j 这两只小猪连成的抛物线能打到的小猪集合。我们用 f [ s ] f[s] f[s] 表示打到的小猪集合为 s s s 时用的最少抛物线。枚举 i , j i,j i,j,那么转移方程为:
f [ s ] = m i n ( f [ s f[s] = min(f[s f[s]=min(f[s^ ( s (s (s& g [ i ] [ j ] ) ] + 1 ) g[i][j])]+1) g[i][j])]+1),就是先取 s s s g [ i ] [ j ] g[i][j] g[i][j] 的交集,然后咔咔掉。这样子复杂度时 O ( n 2 2 n ) O(n^2*2^n) O(n22n)的,能不能更优呢?当然可以。
我们每条抛物线之间时没有先后顺序的,那么我们就可以让最后一只猪作为抛物线的一个点,然后枚举另一只猪作为另一个点,这样复杂度就是 O ( n 2 n ) O(n*2^n) O(n2n)的。

代码如下

//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;
}