NOIp2017提高组题解

发表于 更新于 阅读次数： 本文字数： 8.2k 阅读时长 ≈ 7 分钟

开始有时间改正NOIp2017的题目了，在这篇文章中，简单写一下题解。题意和我在比赛时的原始代码见游记。

小凯的疑惑(math)

没什么可说的了，以后再证明吧。

math.cpp
1
2
3
4
5
6
7
8
9
10
11
#include <fstream>
using namespace std;
ifstream fin("math.in");
ofstream fout("math.out");
int main()
{
	int a, b;
	fin >> a >> b;
	fout << 1ll * a * b - a - b << endl;
	return 0;
}

时间复杂度(complexity)

参见游记。

逛公园(park)

很多人都会做这题，然而我并不会，参考了洛谷的题解。这就是day1的DP，不过比较简单。对于SSSP，我偏好Dijkstra而不是SPFA，因为我出过卡SPFA的题。不过这题并不卡SPFA。

$K=0$

$K=0$时就是$1->N$的最短路计数，与最优化问题DP计数一样。设$d[u]$为$1->u$的最短路，$dp[u]$表示$1->u$的最短路数，则有

$$dp[1]=1$$

$$dp[v]=\sum_{u,v\in E}dp[u],d[v]=d[u]+w_{u,v}$$

无0权边

因为$K\le50$，可以设计$dp[u][k]$表示$1->u$比$d$多走了$k$的路径数，则有

$$dp[u][k]=\begin{cases}1 & u=n \ 0&u\ne n\end{cases}+\sum_{u,v\in E}dp[v][d[u]+k+w_{u,v}-d[v]]$$

注意到达$N$后可能可以绕一圈再回去。

有0权边

显然，如果在$d+K$内经过一个0权环，就有无穷多条路径，只要在DP时发现有重复直接返回即可。

然而这样复杂度并不对，DP可能是$\mathcal O(NMK)$的。需要反向最短路$rd$，当$d[u]+k+w_{u,v}+rd[v]>d+K$时剪枝。这样时间复杂度应该为$\mathcal O(M\log M+MK)$。

park.cpp
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
#include <fstream>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
ifstream fin("park.in");
ofstream fout("park.out");
const int N = 100005, M = 200005, K = 51, INF = 0x3f3f3f3f;
int n, m, k, mod, f[N][K];
typedef pair<int, int> state;
struct graph
{
	int head[N], v[M], w[M], nxt[M], e, d[N];
	bool vis[N];
	void reset()
	{
		fill(head + 1, head + n + 1, 0);
		e = 0;
	}
	void insert(int u, int v, int w)
	{
		graph::v[++e] = v;
		graph::w[e] = w;
		nxt[e] = head[u];
		head[u] = e;
	}
	void dijkstra(int s)
	{
		fill(vis + 1, vis + n + 1, false);
		fill(d + 1, d + n + 1, INF);
		d[s] = 0;
		priority_queue<state, vector<state>, greater<state> > Q;
		Q.push(make_pair(0, s));
		while (!Q.empty())
		{
			state k = Q.top();
			Q.pop();
			if (vis[k.second])
				continue;
			vis[k.second] = true;
			for (int i = head[k.second]; i; i = nxt[i])
				if (d[k.second] + w[i] < d[v[i]])
					Q.push(make_pair(d[v[i]] = d[k.second] + w[i], v[i]));
		}
	}
} mat, rmat;
bool vis[N][K];
int dp(int u, int k)
{
	if (vis[u][k])
		return INF;
	if (~f[u][k])
		return f[u][k];
	vis[u][k] = true;
	f[u][k] = u == n;
	for (int i = mat.head[u]; i; i = mat.nxt[i])
	{
		int nk = mat.d[u] + k + mat.w[i] - mat.d[mat.v[i]];
		if (nk <= ::k && mat.d[u] + k + mat.w[i] + rmat.d[mat.v[i]] <= mat.d[n] + ::k)
		{
			int ret = dp(mat.v[i], nk);
			if (ret == INF)
				return INF;
			(f[u][k] += ret) %= mod;
		}
	}
	vis[u][k] = false;
	return f[u][k];
}
int main()
{
	int t;
	fin >> t;
	while (t--)
	{
		fin >> n >> m >> k >> mod;
		mat.reset();
		rmat.reset();
		while (m--)
		{
			int u, v, w;
			fin >> u >> v >> w;
			mat.insert(u, v, w);
			rmat.insert(v, u, w);
		}
		mat.dijkstra(1);
		rmat.dijkstra(n);
		fill_n(&f[0][0], sizeof(f) / sizeof(int), -1);
		fill_n(&vis[0][0], sizeof(vis) / sizeof(bool), false);
		int ans = dp(1, 0);
		if (ans == INF)
			fout << -1 << endl;
		else
			fout << ans << endl;
	}
	return 0;
}

std::vector被卡常我也无语了，比赛尤其不要用STL。

奶酪(cheese)

修改了判断条件，可以通过原来的数据范围。

cheese.cpp
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
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("cheese.in");
ofstream fout("cheese.out");
const int N = 1005;
int x[N], y[N], z[N];
bool vis[N];
inline long long sqr(long long x)
{
	return x * x;
}
int main()
{
	int t;
	fin >> t;
	while (t--)
	{
		int n, h, r;
		fin >> n >> h >> r;
		queue<int> Q;
		for (int i = 1; i <= n; i++)
		{
			fin >> x[i] >> y[i] >> z[i];
			if (abs(z[i]) <= r)
			{
				vis[i] = true;
				Q.push(i);
			}
			else
				vis[i] = false;
		}
		while (!Q.empty())
		{
			int k = Q.front();
			Q.pop();
			for (int j = 1; j <= n; j++)
				if (!vis[j] && sqr(x[k] - x[j]) + sqr(y[k] - y[j]) <= 4 * sqr(r) - sqr(z[k] - z[j]))
				{
					vis[j] = true;
					Q.push(j);
				}
		}
		bool ans = false;
		for (int i = 1; i <= n; i++)
			if (vis[i] && abs(z[i] - h) <= r)
			{
				ans = true;
				break;
			}
		if (ans)
			fout << "Yes\n";
		else
			fout << "No\n";
	}
	return 0;
}

宝藏(treasure)

错误但好写的状压

突然发现比赛时的想法只要记忆化一下就可以变成状压DP了。原来的d[]数组其实就是二进制状态，转移时直接暴力复制就可以了。

具体的，令$dist[u][v]$为$u->v$的边权，$dp[i][S],i\in S$表示以$i$为根节点，可到达的点集为$S$的最小花费，$d[i][S][u],i\in S$表示在最小花费下$i->u$的边数，则有

$$dp[i][{i}]=0$$

$$dp[i][S+v]=dp[i][S]+(d[i][S][u]+1)\times dist[u][v],u\in S,u,v\in E$$

其中$d$可以在DP转移时同时$\mathcal O(n)$转移。时间复杂度$\mathcal O(2^n n^4)$，比我知道的最优的$\mathcal O(2^n n^3)$差一点，但也不错了。空间复杂度$\mathcal O(2^n n)$。

treasure.cpp
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
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("treasure.in");
ofstream fout("treasure.out");
const int N = 12, INF = 1e9;
int mat[N][N], f[1 << N], d[1 << N][N];
int main()
{
	int n, m;
	fin >> n >> m;
	while (m--)
	{
		int u, v, w;
		fin >> u >> v >> w;
		u--;
		v--;
		if (!mat[u][v] || w < mat[u][v])
			mat[u][v] = mat[v][u] = w;
	}
	int ans = INF;
	for (int i = 0; i < n; i++)
	{
		fill(f, f + (1 << n), INF);
		f[1 << i] = 0;
		for (int j = 0; j < n; j++)
			d[1 << i][j] = i == j ? 0 : INF;
		for (int j = 0; j < (1 << n) - 1; j++)
			for (int k = 0; k < n; k++)
				if (j & (1 << k))
					for (int v = 0; v < n; v++)
						if (mat[k][v] && d[j][v] == INF && f[j] + (d[j][k] + 1) * mat[k][v] < f[j | (1 << v)])
						{
							f[j | (1 << v)] = f[j] + (d[j][k] + 1) * mat[k][v];
							for (int u = 0; u < n; u++)
								d[j | (1 << v)][u] = u == v ? d[j][k] + 1 : d[j][u];
						}
		ans = min(ans, f[(1 << n) - 1]);
	}
	fout << ans << endl;
	return 0;
}

更新：但其实这样有问题。当dp的花费最优时，保存的距离d[]不一定最优，对拍已经发现反例了。然而比赛时的dfs是正确的，因为有回溯，事实上我就是用这个作为std的。可以看一下能不能卡掉一些人。

1
2
3
4
5
6
7
8
9
10
6 9
5 4 5
3 6 1
1 5 4
5 3 4
1 6 2
5 6 5
2 1 1
1 3 2
2 6 2
1
17

正确但很慢的状压

暂时不引入，较为复杂，复杂度可达$\mathcal O(3^n)$级别。

随机化

可以使用随机化水过，比较高端的是模拟退火，而低端的是直接random_shuffle然后贪心，足以水过没有针对性的数据。然而，上述数据依然被卡掉。而洛谷上可以找到优秀的模拟退火，而且不会被卡掉。

treasure_rand.cpp
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
#include <iostream>
#include <random>
#include <algorithm>
using namespace std;
const int N = 15, INF = 1e9;
int mat[N][N], p[N], d[N];
int main()
{
	minstd_rand gen(19260817);
	int n, m;
	cin >> n >> m;
	fill_n(&mat[0][0], sizeof(mat) / sizeof(int), INF);
	while (m--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		if (w < mat[u][v])
			mat[u][v] = mat[v][u] = w;
	}
	for (int i = 1; i <= n; i++)
		p[i] = i;
	int ans = INF;
	for (int t = 1; t <= 10000; t++)
	{
		shuffle(p + 1, p + n + 1, gen);
		d[p[1]] = 1;
		int now = 0;
		for (int i = 2; i <= n; i++)
		{
			int j = 0;
			for (int k = 1; k < i; k++)
				if (!j || mat[p[k]][p[i]] < mat[p[j]][p[i]])
					j = k;
			if (!j || mat[p[j]][p[i]] == INF)
			{
				now = INF;
				break;
			}
			now += mat[p[j]][p[i]] * d[p[j]];
			d[p[i]] = d[p[j]] + 1;
		}
		ans = min(ans, now);
	}
	cout << ans << endl;
	return 0;
}

搜索剪枝

其实也挺难写的……

队列(phalanx)

其实比赛时的思路已经很接近正解了，只是我懒得想也不敢写。$n$行都维护一颗线段树，还有最后一列。一个问题是空间，但只要动态开点线段树，单次操作空间复杂度就是$\log n$级别的，完全可以。另一个问题是初始的编号，这也是比赛时我认为不可做的主要原因，现在想起来其实只要根据坐标就可以算出初始编号，思想与50%的数据类似。接下来只剩下一些细节问题，我调了不少时间，代码可能比较繁杂。事实证明，线段树并不会被卡常，至少在本地和洛谷。

时间复杂度$\mathcal O(q\log (n+q))$，空间复杂度相同。

phalanx.cpp
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
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("phalanx.in");
ofstream fout("phalanx.out");
const int N = 300005, L = 12e6;
struct node
{
	int sum, ls, rs;
} tree[L];
int cc, root[N], last;
vector<long long> mat[N], ml;
int query(int id, int l, int r, int x)
{
	if (l == r)
		return l;
	int mid = (l + r) / 2;
	if (mid - tree[tree[id].ls].sum >= x)
		return query(tree[id].ls, l, mid, x);
	return query(tree[id].rs, mid + 1, r, x + tree[tree[id].ls].sum);
}
void modify(int &id, int l, int r, int x)
{
	if (!id)
		id = ++cc;
	if (l == r)
		tree[id].sum++;
	else
	{
		int mid = (l + r) / 2;
		if (x <= mid)
			modify(tree[id].ls, l, mid, x);
		else
			modify(tree[id].rs, mid + 1, r, x);
		tree[id].sum = tree[tree[id].ls].sum + tree[tree[id].rs].sum;
	}
}
int main()
{
	int n, m, q;
	fin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		mat[i].push_back(1ll * i * m);
	ml.push_back(1ll * n * m);
	int r = max(n, m) + q;
	while (q--)
	{
		int x, y;
		fin >> x >> y;
		long long tmp = query(last, 1, r, x);
		if (tmp <= n)
			tmp = 1ll * tmp * m;
		else
			tmp = ml[tmp - n];
		if (m + mat[x].size() - 1 - tree[root[x]].sum == m)
			modify(root[x], 1, r, m + mat[x].size() - 1);
		mat[x].push_back(tmp);
		long long num = query(root[x], 1, r, y);
		modify(root[x], 1, r, num);
		if (num <= m)
			num = 1ll * (x - 1) * m + num;
		else
			num = mat[x][num - m];
		modify(last, 1, r, query(last, 1, r, x));
		ml.push_back(num);
		fout << num << '\n';
	}
	return 0;
}

终于断断续续的写完了这篇文章，从12/2创建到12/26完工。