Nescafe28 树/图论专项练习

Posted on | In |
Words count in article: 2.1k | Reading time ≈ 10

Nescafe28 树/图论专项练习

A 升降梯上(updown)

题意

一个电梯，在 $1～n$ 层中运动，手柄有 $m$ 个控制槽，位于第 $i$ 个槽时可以让电梯移动 $C_i$ 层。手柄移动一个槽耗时 $1$ 秒，电梯移动一层耗时 $2$ 秒。手柄一开始位于 $C_i=0$ 处，求从第 $1$ 层到第 $n$ 层所用的最短时间。

思路

很显然这是一道水题，只要联想到这场比赛的主题就很简单了。

考虑建图，由于 $n$ 并不是很大，所以可以暴力 $O(n\times m)$ 地建图，具体来说就是对每一个节点 $i$ ，把它和所有使 $1\leq i+C_j\leq n$ 的 $j$ 连一条单向边，由于手柄移动需要时间，所以要附带两个属性：边权和此时手柄处在的位置。然后暴力 $\text{SPFA}$ 就行了。

注意

建图不能错，而且由于做法的差异，此处应使用堆优化以保证在取得最短路径的同时手柄处在正确的位置。

代码

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, m;
int a[N];

struct Graph
{
	int cnt, head[N];
	int dis[N];
	bool vis[N];
	
	struct edge
	{
		int to, nxt, weight, type;
	};
	edge e[N];
	
	struct node
	{
		int ver, dist, last;
		friend bool operator < (node a1, node a2)
		{
			return a1.dist > a2.dist;
		}
	};
	
	il void add_edge(int u, int v, int w, int t)
	{
		e[++cnt] = (edge){v, head[u], w, t};
		head[u] = cnt;
	}
	il void Insert(int u, int v, int w, int t)
	{
		add_edge(u, v, w, t);
		add_edge(v, u, w, t);
	}
	
	il void SPFA(int s, int now)
	{
		for (ri i = 1; i <= n; i++)
			dis[i] = inf, vis[i] = 0;
		priority_queue <node> q;
		vis[s] = 1;
		dis[s] = 0;
		q.push((node) {s, 0, now});
		while (!q.empty())
		{
			node ViXbob = q.top();
			q.pop();
			int u = ViXbob.ver, Zhyic = ViXbob.last, Edgration = ViXbob.dist;
			if (dis[u] != Edgration)
				continue;
			for (ri i = head[u]; i; i = e[i].nxt)
			{
				int v = e[i].to, KL = e[i].type;
				if (dis[v] > dis[u] + e[i].weight + abs(KL - Zhyic))
				{
					dis[v] = dis[u] + e[i].weight + abs(KL - Zhyic);
					q.push((node) {v, dis[v], KL});
				}
			}
		}
	}
};
Graph G;

int main()
{
#ifndef Wepdekr
	freopen("updown.in", "r", stdin);
	freopen("updown.out", "w", stdout);
#endif
	n = read(), m = read();
	int now = 0;
	for (ri i = 1; i <= m; i++)
	{
		a[i] = read();
		if (a[i] == 0)
			now = i;
	}
	for (ri i = 1; i <= n; i++)
		for (ri j = 1; j <= m; j++)
		{
			if (i + a[j] < 1 || i + a[j] > n || a[j] == 0)
				continue;
			G.add_edge(i, i + a[j], abs(a[j]) * 2, j);
		}
	G.SPFA(1, now);
	printf("%d\n", (G.dis[n] < inf) ? G.dis[n] : -1);
	return 0;
}
/*
6 3
-1 0 2

*/

B 塔顶试探(probe)

题意

给出一棵有根树的 $\text{DFS}$ 序，问有多少种不同的树可以使 $\text{DFS}$ 序与给出序列相同，答案对 $10^9$ 取模

思路

很显然这是一个 $\text{DP}$ ，由于给出的是 $\text{DFS}$ 序，我们可以知道一棵子树的根节点一定在子树的 $\text{DFS}$ 序列的首位都会出现，我们只需要在两个端点中枚举一个划分点 $k$ ，由乘法原理就可以得到答案。

转移方程如下：

注意

枚举划分点时不要忘记只有一棵子树的情况

代码

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 310;
const int inf = 0x7fffffff;
const double eps = 1e-8;
const int mod = 1e9;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

char s[N];
ll dp[MAXN][MAXN];

int main()
{
#ifndef Wepdekr
	freopen("probe.in", "r", stdin);
	freopen("probe.out", "w", stdout);
#endif
	scanf("%s", s);
	int len = strlen(s);
	for (ri i = 0; i < len; i++)
		dp[i][i] = 1;
	for (ri i = len - 2; i >= 0; i--)
		for (ri j = i + 1; j < len; j++)
		{
			if (s[i] == s[j])
			{
				dp[i][j] = (dp[i][j] + dp[i + 1][j - 1]) % mod;
				for (ri k = i + 2; k < j - 1; k++)
					if (s[i] == s[k])
						dp[i][j] = (dp[i][j] + (dp[i + 1][k - 1] * dp[k][j]) % mod) % mod;
			}
		}
	printf("%lld", dp[0][len - 1]);
	return 0;
}
/*
ABABABA

*/

C 礼物运送(transport)

题意

给出一张无向带权图，有两个人遍历这张图，定义遍历这张图的时间为耗时较长的人的时间，问这个时间最小是多少

思路

先看数据范围可以猜出是状压 $\text{DP}$ ，然而他们虽然是两个人一起走，但没有任何限制，所以我们不妨将此题看为一个人走。否则设计状态就要三维，分别为1号人最后走到的地方 $i$ ，2号人最后走到的地方 $j$ ，和此时两人一共走过的集合 $S$ 。

（二进制状压），你悄悄算算就会发现一件很奇妙的事情： $\text{MLE}$ 。所以我们只能考虑记录一个 $i$ 和 $S$ ，所以得到的应该是对于这个图的每一种遍历过的点集 $S$ ，走到的末位置为 $i$ 的情况下的最少步数。考虑两个人无论谁走都是一样的，那么我们想要得到答案就应该是 $min{max(dp[s|1][i],dp[(2^n-1-s)|1][j])} (i,j\in V)$ ；（之所以要|1是因为1是出发点，其他点可以取反，但1不能）

所以是这样的吗？如果你照着这个思路用普通的状压 $\text{DP}$ 扩展你会发现你连样例都过不了。因为样例中两人还共同走了一段，而这一段是必须的。如何把这一段加进去呢？其实，跑最短路将连通图的每两个点的最短距离算出来即可，因为在运用最短路扩展时，计算 $dist$ 数组会加进一些必要经过的点，并且这些点是最优的。所以现在我们完善状态：一定会经过 $S$ 中的点，但经过的点不一定是 $S$（子集关系）因为有可能多经过其他点而更优。所以到这里状态转移方程才是正确的。建议用 $\text{Floyed}$ 求多源点最短路。

注意

$\text{DP}$ 时要注意了两人一起走的一段

代码

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;
const int maxn = (1 << 20);

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, m;
int mp[50][50];
int dp[maxn][50];

int main()
{
#ifndef Wepdekr
	freopen("transport.in", "r", stdin);
	freopen("transport.out", "w", stdout);
#endif
	n = read(), m = read();
	memset(mp, 63, sizeof(mp));
	for (ri i = 1; i <= m; i++)
	{
		int u = read(), v = read(), w = read();
		mp[u][v] = mp[v][u] = w;
	}
	for (ri i = 1; i <= n; i++)
		mp[i][i] = 0;
	for (ri k = 1; k <= n; k++)
		for (ri i = 1; i <= n; i++)
			for (ri j = 1; j <= n; j++)
				if (mp[i][k] + mp[k][j] < mp[i][j])
					mp[i][j] = mp[i][k] + mp[k][j];
	memset(dp, 63, sizeof(dp));
	dp[1][1] = 0;
	for (ri i = 1; i <= (1 << n) - 1; i++)
		for (ri j = 1; j <= n; j++)
			if ((1 << j - 1) & i)
				for (ri k = 1; k <= n ; k++)
					if (((1 << k - 1) & i) && (dp[i][j] > dp[i - (1 << j - 1)][k] + mp[k][j]) && i != j)
						dp[i][j] = dp[i - (1 << j - 1)][k] + mp[k][j];
	for (ri i = 1; i <= (1 << n) - 1; i++)
		for (ri j = 1; j <= n; j++)
			dp[i][0] = min(dp[i][0], dp[i][j]);
	int ans = inf;
	for (ri i = 1; i <= (1 << n) - 1; i++)
		ans = min(ans, max(dp[i | 1][0], dp[((1 << n) - 1 - i) | 1][0]));
	printf("%d", ans);
	return 0;
}
/*
6 6
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10

*/

总结

本次模拟赛整体上难度适中，但是由于动态规划做题的底力并不是很够，所以BC两题没有拿到分

  1. 多练习 $\text{DP}$ ，培养做题的感觉，看到 $\text{DP}$ 就没有思路瞎搞的话肯定会出事的
  2. 对与一些性质应当更敏感一些，有时在草稿纸上写出来会看的更清楚一些
0%