NOIp2017提高组题解

开始有时间改正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=0K=0

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

dp[1]=1dp[1]=1dp[v]=u,vEdp[u],d[v]=d[u]+wu,vdp[v]=\sum_{u,v\in E}dp[u],d[v]=d[u]+w_{u,v}

无0权边

因为K50K\le50,可以设计dp[u][k]dp[u][k]表示1>u1->udd多走了kk的路径数,则有

dp[u][k]={1u=n0un+u,vEdp[v][d[u]+k+wu,vd[v]]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]]

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

有0权边

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

然而这样复杂度并不对,DP可能是O(NMK)\mathcal O(NMK)的。需要反向最短路rdrd,当d[u]+k+wu,v+rd[v]>d+Kd[u]+k+w_{u,v}+rd[v]>d+K时剪枝。这样时间复杂度应该为O(MlogM+MK)\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]dist[u][v]u>vu->v的边权,dp[i][S],iSdp[i][S],i\in S表示以ii为根节点,可到达的点集为SS的最小花费,d[i][S][u],iSd[i][S][u],i\in S表示在最小花费下i>ui->u边数,则有

dp[i][{i}]=0dp[i][\{i\}]=0dp[i][S+v]=dp[i][S]+(d[i][S][u]+1)×dist[u][v],uS,u,vEdp[i][S+v]=dp[i][S]+(d[i][S][u]+1)\times dist[u][v],u\in S,u,v\in E

其中dd可以在DP转移时同时O(n)\mathcal O(n)转移。时间复杂度O(2nn4)\mathcal O(2^n n^4),比我知道的最优的O(2nn3)\mathcal O(2^n n^3)差一点,但也不错了。空间复杂度O(2nn)\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

正确但很慢的状压

暂时不引入,较为复杂,复杂度可达O(3n)\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)

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

时间复杂度O(qlog(n+q))\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完工。