NOIp 2016 提高组题解

发表于   |   分类于   |     |   阅读次数

照例

好久不刷题不写题解了。想想自己也大三了。看到子楚兄说自己退役的一瞬间，突然发现自己的时间其实也只剩下一年不到了。
到现在ACM连个铜都没拿过，CCPC也是打铁。再不好好刷题再也没时间了。
跟队友开玩笑说明年要拿金。但我真的希望不是玩笑。

刷题，我生命中最美的两个字！

Day 1

T1 toy 玩具谜题

原题链接

解释

水题，模拟就行。
我取了个巧，把0换成-1，然后乘就可以。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>

typedef long long LL;

int main()
{
	int n, m, d[100010];
	char name[100010][15];
	
	scanf("%d %d", &n, &m);
	
	for (int i=1; i<=n; i++)
	{
		scanf("%d %s", &d[i], name[i]); getchar();
		if (!d[i]) d[i] = -1;
	}
	
	int a, s;
	int pos = 1;
	
	for (int i=0; i<m; i++)
	{
		scanf("%d%d", &a, &s);
		if (!a) a = -1;
		pos -= a * d[pos] * s;
		if (pos <= 0) pos += n;
		if (pos > n) pos -= n;
	}
	
	printf("%s\n", name[pos]);
}

T2 running 天天爱跑步

原题链接

解释

两天最难的题了吧。一开始想的是骗分。思路是网上看来的。
首先所有的路径一定是从起点经过LCA（最小公共祖先）到达终点，先上后下（也有可能只上或只下）。
于是我们把s到t的路径拆分成s到top（向上）再由top到t（向下）。
如果把节点v深度记为d[v]的话，那么在向上的过程中 时间+深度 是定值d[s]。
同样，向下过程中 深度-时间 是定值d[t]-len（len = d[s]+d[t]-2*d[top]，是路径总长度，也是总时间）。
换句话说，对于从s到top这条路径上所有的点v，如果它的观察时间w[v]满足w[v]+d[v] == d[s]；同理，向下满足d[v]-w[v] == d[t]-len，那么它的答案数就要+1。

有几个点吧，第一个是LCA，第二个是树的前缀和。
LCA有人说用Tarjan，我比较菜，不会。我能接受的一种O(nlogn)的方法就是开一个f[0..N][0..logN]的数组，f[i][j]表示结点i的第2^j级父节点。这样找LCA的时候就是O(logn)级别的了。
然后说到，在给s到top或者top到t做标记的时候我们是不能遍历一个个做标记的，所以我们先O(1)的做标记。
比如s到top时，我们在s处做+1标记，在top处做-1标记，之后在求结果的时候深搜求子树和。
用两个数组（桶）up[i]、down[i]记录当前搜索路径下定值为i的路径数（为了避免负数，down数组下标需要加上一个MAXN）
然后就没有了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 300007 

using namespace std;

int first[MAXN*20], last[MAXN*2], next[MAXN*2], num;
int first1[MAXN*20], last1[MAXN*2], next1[MAXN*2], num1;
int first2[MAXN*20], last2[MAXN*2], next2[MAXN*2], num2;
int first3[MAXN*20], last3[MAXN*2], next3[MAXN*2], num3;
int first4[MAXN*20], last4[MAXN*2], next4[MAXN*2], num4;
int d[MAXN];
int w[MAXN];
int ans[MAXN];
int up[MAXN*2];
int down[MAXN*2];
int f[MAXN][25];

int lca(int x, int y)
{
	if (d[x] < d[y])
	{
		swap(x, y);
	}
	for (int i=20; i>=0; i--)
	{
		if (d[f[x][i]] >= d[y])
		{
			x = f[x][i];
		}
	}
	if (d[x] != d[y])
		x = f[x][0];
	
	for (int i=20; i>=0; i--)
	{
		if (f[x][i] != f[y][i])
		{
			x = f[x][i];
			y = f[y][i];
		}
	}
	
	return (x != y) ? f[x][0] : x;
}

void dfs(int v)
{
	int x = up[d[v]+w[v]];
	int y = down[d[v]-w[v]+MAXN];
	for (int i=first1[v]; i; i=next1[i])
	{
		up[last1[i]]++;
	}
	for (int i=first2[v]; i; i=next2[i])
	{
		down[last2[i]+MAXN]++;
	}
	for (int i=first[v]; i; i=next[i])
	{
		if (last[i] != f[v][0])
		{
			dfs(last[i]);
		}
	}
	ans[v] = up[d[v]+w[v]] + down[d[v]-w[v]+MAXN]-x-y;
	for (int i=first3[v]; i; i=next3[i])
	{
		up[last3[i]]--;
		if (last3[i] == d[v]+w[v])
			ans[v]--;
	}
	for (int i=first4[v]; i; i=next4[i])
	{
		down[last4[i]+MAXN]--;
	}
}

void calc_deep(int v, int fa)
{
	d[v] = d[fa]+1;
	f[v][0] = fa;
	for (int i = first[v]; i; i=next[i])
	{
		if (last[i] != fa)
		{
			calc_deep(last[i], v);
		}
	}
}

void add(int u, int v)
{
	last[++num] = v;
	next[num] = first[u];
	first[u] = num;
}

void add_up(int u, int v)
{
	last1[++num1] = v;
	next1[num1] = first1[u];
	first1[u] = num1;
}

void add_down(int u, int v)
{
	last2[++num2] = v;
	next2[num2] = first2[u];
	first2[u] = num2;
}

void add_top_up(int u, int v)
{
	last3[++num3] = v;
	next3[num3] = first3[u];
	first3[u] = num3;
}

void add_top_down(int u, int v)
{
	last4[++num4] = v;
	next4[num4] = first4[u];
	first4[u] = num4;
}



int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	
	for (int i=0; i<n-1; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	
	calc_deep(1, 0);
	for (int j=1; j<=20; j++)
	{
		for (int i=1; i<=n ;i++)
		{
			f[i][j] = f[f[i][j-1]][j-1];
		}
	}
	
	for (int i=1; i<=n; i++)
	{
		scanf("%d", &w[i]);
	}
	
	for (int i=1; i<=m; i++)
	{
		int s, t;
		scanf("%d%d", &s, &t);
		int top = lca(s, t);
		int len = d[s]+d[t]-d[top]-d[top];
		int diff = d[t] - len;
		add_up(s, d[s]);
		add_down(t, diff);
		add_top_up(top, d[s]);
		add_top_down(top, diff);
	}

	dfs(1);
	
	for (int i=1; i<=n; i++)
    {
    	printf("%d ",ans[i]);
	}
}

T3 classroom 换教室

原题链接

解释

dp，几乎算是模板题。
递推式自己看代码吧。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>
#define MAXN 2010 
#define MAXL 10000000

int c[MAXN];
int d[MAXN];
double k[MAXN];
int w[MAXN][MAXN];
double f[MAXN][MAXN][3];

double min(double a, double b)
{
	return a < b ? a : b;
}

int main()
{
	int n, m, v ,e;
	int i, j, mid;
	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<=v; i++)
	{
		for (int j=1; j<=v; j++)
		{
			w[i][j] = MAXL;
		}
	}
	for (i=1; i<=v; i++)
	{
		w[i][i] = 0;
	}
	for (i=0; i<e; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		scanf("%d", &w[u][v]);
		if (w[v][u] > w[u][v])
			w[v][u] = w[u][v];
		else
			w[u][v] = u == v ? 0 : w[v][u];
	}
	for (mid=1; mid<=v; mid++)
		for (i=1; i<=v; i++)
			for (j=1; j<=v; j++)
			{
				if (w[i][j] > w[i][mid] + w[mid][j])
				{
					w[i][j] = w[i][mid] + w[mid][j];
				}
			}
	
	f[0][0][0] = 0;
	
	for (i=0; i<=n; i++)
	{
		for (j=0; j<=m; j++)
		{
			if (i<j) 
			{
				f[i][j][0] = f[i][j][1] = MAXL;
			} 
			else 
			{
				if (i == 0 && j == 0) 
					f[i][j][0] = 0;
				else
					f[i][j][0] = min(f[i-1][j][0] + w[c[i-1]][c[i]], 
							 f[i-1][j][1] + k[i-1] * w[d[i-1]][c[i]] + (1-k[i-1]) * w[c[i-1]][c[i]]);
				if (j==0)
					f[i][j][1] = MAXL;
				else			 
					f[i][j][1] = min(f[i-1][j-1][0] + (1-k[i]) * w[c[i-1]][c[i]] + k[i] * w[c[i-1]][d[i]],
							 f[i-1][j-1][1] + k[i] * k[i-1] * w[d[i-1]][d[i]] + k[i] * (1-k[i-1]) * w[c[i-1]][d[i]] + (1-k[i]) * k[i-1] * w[d[i-1]][c[i]] + (1-k[i-1]) * (1-k[i]) * w[c[i-1]][c[i]]);
			
				
			}
		}
	}
	
	double ans = f[n][0][0];
	for (int j=1; j<=m && j<=n; j++)
	{
		if (f[n][j][0] < ans) ans = f[n][j][0];
		if (f[n][j][1] < ans) ans = f[n][j][1];
	}
	printf("%.2lf", ans);
	 
}

Day 2

T1 problem 组合数问题

原题链接

解释

杨辉三角性质+二维前缀和。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#define MAXN 2016

typedef long long LL;

LL C[MAXN][MAXN];
LL ans[MAXN][MAXN];

int main()
{
	int t, k;
	scanf("%d%d", &t, &k);
	
	C[0][0] = 1;
	for (int i=1; i< 2010; i++)
	{
		C[i][0] = 1;
		ans[i][0] = 0; 
		for (int j=1; j<i; j++)
		{
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % k;
			ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1];
			if (C[i][j] == 0) ans[i][j]++;
		}
		C[i][i] = 1;
		ans[i][i] = ans[i][i-1];
	}
	
	while (t--)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		if (m > n) m = n;
		printf("%lld\n", ans[n][m]);
	}
}

T2 earthworm 蚯蚓

原题链接

解释

一开始用的queue，结果爆常数了。一怒之下开个10^6的数组好了。
由于切的比例p是定值，所以先被切的一定比后被切的长，所以直接把原长排序、再把切下来的两端分别放进两个队列，每次取队首的比，最长的拿来切。
每回合所有的增长转化为被切的两个缩短。需要注意的是切之前要算一下原长再切。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <queue>
#include <cstdlib>
#include <algorithm>
#define N 2140000000
#define MAXM 7200100

using namespace std;

int q1[MAXM], q2[MAXM], q3[MAXM];
int head1=0, head2=0, head3=0;
int tail1=-1, tail2=-1, tail3=-1;

int Trunc(double x)
{
	return (long long)(x + N) - N;
}

bool cmp(int a, int b)
{
	return a>b;
}

int main()
{
	int n, m, q, u, v, t;
	scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
	
	for (int i=0; i<=n+m+1; i++)
	{
		q1[i] = q2[i] = q3[i] = -N;
	}
	
	int tmp;
	for (int i=0; i<n; i++)
	{
		scanf("%d", &q1[i]);
	}
	sort(q1, q1+n, cmp);
	tail1 = n-1;
	
	double p = (double)u/v;

	int *t1, *t2, *t3;
	t1 = q1+head1;
	t2 = q2+head2;
	t3 = q3+head3;
	for (int i=0; i<m; i++)
	{
		if (*t1 >= *t2)
		{
			if (*t1 >= *t3)
			{
				tmp = *t1;
				head1++;
				t1++;
			}
			else
			{
				tmp = *t3;
				head3++;
				t3++;
			}
		}
		else
		{
			if (*t2 >= *t3)
			{
				tmp = *t2;
				head2++;
				t2++;
			}
			else
			{
				tmp = *t3;
				head3++;
				t3++;
			}
		}
		tmp += q * i;
		q2[++tail2] = Trunc(tmp * p - (i+1) * q);
		q3[++tail3] = tmp - (int)(tmp * p) - (i+1) * q;
		
		if ((i+1) == t) printf("%d", tmp);	
		else if ((i+1) % t == 0) printf(" %d", tmp);	
	}
	printf("\n");
	
	int tt = 0;
	while (*t1 != -N || *t2 != -N || *t3 != -N)
	{
		tt++;
		if (*t1 >= *t2)
		{
			if (*t1 >= *t3)
			{
				tmp = *t1;
				head1++;
				t1++;
			}
			else
			{
				tmp = *t3;
				head3++;
				t3++;
			}
		}
		else
		{
			if (*t2 >= *t3)
			{
				tmp = *t2;
				head2++;
				t2++;
			}
			else
			{
				tmp = *t3;
				head3++;
				t3++;
			}
		}
		
		if (tt == t) printf("%d", tmp + m*q);
		else if (tt % t == 0) printf(" %d", tmp + m*q);
		
		
	}
}

T3 angrybirds 愤怒的小鸟

原题链接

解释

状压dp。
i看成二进制，由低到高第x位表示第x只猪。0为未击中，1为击中。
先两两初始化出由这两个点确定的抛物线可以击中的所有的猪（击中就或上这一位），然后O(2^n)的dp就可以了。
有几个坑，一个是a有可能大于等于0，另一个是double由于精度的问题等于要用abs(a-b)<EXP的方式判断。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <cstdio>
#define MAXN 265000

#define EXP 1e-6

typedef long long LL;

double x[20];
double y[20];
int f[MAXN];

LL pow2[20];
LL route[20][20];

double abs(double x)
{
	return x>=0 ? x : -x;
}

int log2(LL x)
{
	switch (x)
	{
		case 1:
			return 0;
		case 2:
			return 1;
		case 4:
			return 2;
		case 8:
			return 3;
		case 16:
			return 4;
		case 32:
			return 5;
		case 64:
			return 6;
		case 128:
			return 7;
		case 256:
			return 8;
		case 512:
			return 9;
		case 1024:
			return 10;
		case 2048:
			return 11;
		case 4096:
			return 12;
		case 8192:
			return 13;
		case 16384:
			return 14;
		case 32768:
			return 15;
		case 65536:
			return 16;
		case 131072:
			return 17;
		case 262144:
			return 18;
		case 524288:
			return 19;
	}
	return -1;
}

int main()
{
	pow2[0] = 1;
	for (int i=1; i<19; i++)
	{
		pow2[i] = pow2[i-1] * 2;
	}
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i=0; i<n; i++)
		{
			scanf("%lf%lf", &x[i], &y[i]);
		}
		for (int i=0; i<n-1; i++)
		{
			for (int j=i+1; j<n; j++)
			{
				double a = (x[i]*y[j]-x[j]*y[i])/(x[i]*x[j]*(x[j]-x[i]));
				double b = (x[j]*x[j]*y[i]-x[i]*x[i]*y[j])/(x[i]*x[j]*(x[j]-x[i]));
				if (a >= 0 || abs(x[j]-x[i]) < EXP) {
					route[i][j] = pow2[i];
					continue;
				}
				route[i][j] = pow2[i] | pow2[j];
				for (int k=0; k<n; k++)
				{
					if (abs(a*x[k]*x[k]+b*x[k]-y[k]) < EXP) 
					{
						route[i][j] |= pow2[k];
					}
				}
				route[j][i] = route[i][j];
			}
		}
		
		for (LL s=1; s<pow2[n]; s++)
		{
			f[s] = 100;
		}
		
		f[0] = 0;
		for (LL s=0; s<pow2[n]-1; s++)
		{
			int i = log2(((s ^ (s+1)) + 1) >> 1);
			LL tmp = 0;
			for (int j=i+1; j<n; j++)
			{
				tmp =  s | route[i][j];
				if (f[tmp] > f[s] + 1)
					f[tmp] = f[s] + 1;
			}
			if (tmp == 0) {
				tmp = pow2[n]-1;
				if (f[tmp] > f[s] + 1)
					f[tmp] = f[s] + 1;
			}
		}
		printf("%d\n", f[pow2[n]-1]);
	}
}