NOIP 2015 整理

Day 1

神奇的幻方

描述

幻方是一种很神奇的 $N \times N$ 矩阵:它由数字 $1,2,3, \cdots , N \times N$ 构成,且每行、每列
及两条对角线上的数字之和都相同。

当 $N$ 为奇数时,我们可以通过以下方法构建一个幻方:
首先将 $1$ 写在第一行的中间。之后,按如下方式从小到大依次填写每个数 $K(K = 2,3, \cdots , N \times N)$ :

  1. 若 $(K − 1)$ 在第一行但不在最后一列,则将 $K$ 填在最后一行,$(K − 1)$ 所在列
    的右一列
  2. 若 $(K − 1)$ 在最后一列但不在第一行,则将 $K$ 填在第一列,$(K − 1)$ 所在行的上
    一行
  3. 若 $(K − 1)$ 在第一行最后一列,则将 $K$ 填在 $(K − 1)$ 的正下方
  4. 若 $(K − 1)$ 既不在第一行,也不在最后一列,如果 $(K − 1)$ 的右上方还未填数,则将 $K$ 填在 $(K − 1)$ 的右上方,否则将 $K$ 填在 $(K − 1)$ 的正下方。

现给定 $N$,请按上述方法构造 $N \times N$ 的幻方。

$ 1 \leq N \leq 39$ 且 $N$ 为奇数。

分析

记一下上一个数所在的位置 $(lastX, lastY)$ ,然后 $\Theta(n^{2})$ 扫一遍,模拟一下。

具体细节见代码。

代码

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
//  Created by ZJYelizaveta on Thursday, October 19, 2017 AM09:07:14 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 39 + 3;
const int INF = 0x3f3f3f3f;
int n;
int a[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N];

int main()
{
n = readIn<int>();

memset(vis, false, sizeof vis);
a[1][(n + 1) / 2] = 1, vis[1][(n + 1) / 2] = true;

int lastX = 1, lastY = (n + 1) / 2; // row, column
// printf("%d %d\n", lastX, lastY);
for (int i = 2; i <= n * n; ++i) {
if (lastX == 1 && lastY != n) {
lastX = n, lastY = lastY + 1;
a[lastX][lastY] = i; vis[lastX][lastY] = true;
}
else if (lastX != 1 && lastY == n) {
lastX = lastX - 1, lastY = 1;
a[lastX][lastY] = i; vis[lastX][lastY] = true;
}
else if (lastX == 1 && lastY == n) {
lastX = lastX + 1, lastY = lastY;
a[lastX][lastY] = i; vis[lastX][lastY] = true;
}
else {
// printf("%d\n", (int)vis[lastX - 1][lastY + 1]);
if (vis[lastX - 1][lastY + 1] == true) {
lastX = lastX + 1, lastY = lastY;
a[lastX][lastY] = i; vis[lastX][lastY] = true;
}
else {
lastX = lastX - 1, lastY = lastY + 1;
a[lastX][lastY] = i; vis[lastX][lastY] = true;
}
}
// printf("%d %d\n", lastX, lastY);
}

for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) printf("%d%c", a[i][j], j == n ? '\n' : ' ');
}
return 0;
}

信息传递

描述

有 $n$ 个同学(编号为 $1$ 到 $n$ )正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为 $i$ 的同学的信息传递对象是编号为 $T_{i}$ 的同学。
游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息, 但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自 己的生日时,游戏结束。请问该游戏一共可以进行几轮?

$n \leq 2 \times 10^{5}$

分析

模拟了很久发现是找一个有向图的最小环。

说实话,真没想到拓扑排序上面。由于没有智商,所以强行 Tarjan,时间复杂度为 $\Theta(n + m)$。

P.S. Blog 上面之前总结的 “ [关于图的连通性的三个Tarjan算法] “,有些地方有些小问题,找时间来改吧 !

代码

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
//  Created by ZJYelizaveta on Thursday, October 19, 2017 AM09:37:57 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 200000 + 3;
const int INF = 0x3f3f3f3f;
int n;
int pre[MAX_N], lowlink[MAX_N], sccno[MAX_N], scc_cnt, timeStamp;
vector<int> G[MAX_N];
stack<int> S;
int ans, size[MAX_N];

namespace SCC {
inline void dfs(int u) {
pre[u] = lowlink[u] = ++timeStamp;
S.push(u);

for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (!pre[v]) {
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else if (!sccno[v]) lowlink[u] = min(lowlink[u], pre[v]);
}
if (lowlink[u] == pre[u]) {
++scc_cnt;
while (1) {
int x = S.top(); S.pop();
sccno[x] = scc_cnt;
if (x == u) break;
}
}
}

inline void findSCC() {
memset(pre, 0, sizeof pre);
memset(lowlink, 0, sizeof lowlink);
memset(sccno, 0, sizeof sccno);
timeStamp = scc_cnt = 0;

for (int i = 0; i < n; ++i) if (!pre[i]) dfs(i);
}
}
using namespace SCC;

int main()
{
n = readIn<int>();

for (int i = 0; i <= n; ++i) G[i].clear();
for (int i = 1; i <= n; ++i) {
int u = i, v = readIn<int>();
--u; --v;
G[u].push_back(v);
}

findSCC();

ans = INF;
for (int i = 0; i < n; ++i) ++size[sccno[i]];
for (int i = 1; i <= scc_cnt; ++i) if (1 < size[i]) ans = min(ans, size[i]);

printf("%d\n", ans);
return 0;
}

斗地主

描述

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的 $A$ 到 $K$ 加上大小王的共 $54$ 张牌来进行的扑克牌游戏。在斗地主中,牌的大小关 系根据牌的数码表示如下: 3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由 nn 张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。
现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下:

$n \leq 23, testCase \leq 100$

分析

我练习的时候,还剩下 1.5h ,认真的思考了一下,好像并没有很清晰地思路,遂放弃刚正解。

于是我把特判的 30 分写了,然后还写挂了 $n = 4$ 的情况,我真是太菜啦qwq

思考正解。

一开始想到了搜索,但是并没有想到状压上面。那么这里就思考只用 dfs 怎么做吧!

首先要确定 dfs 的可行性,考虑现在有 23 张牌,那么在最坏的情况下,需要出 13 次牌。情况是这样的:1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 大王, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12。也就是说如果加上最优性剪枝,那么搜索的层数不会超过 13 层。

这里搜索的时候根据贪心的思想优先出三种顺子 : 单顺子,双顺子,三顺子 ; 然后出三带一,三带二 …… 总之将单牌留在最后出。出顺子的时候枚举一下顺子的首和尾,出三带几的时候先确定主体的牌再枚举带的牌。

具体细节看代码吧,由于思路比较暴力,这个算法过不了 UOJ #151. 【NOIP2015】斗地主“加强”版 ,后面有时间再考虑怎么优化一下吧,正解应该还是 状压 + 搜索。

然后还要注意这里的四带二带的是不同的单牌或者是不同的一对牌。

时间复杂度 $\Theta$ (玄学),这个时间复杂度我不会算有没有大佬能教一下,谢谢!

代码

特判写的太丑了,就不放上来了qwq

$100 \%$

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
//  Created by ZJYelizaveta on 2017年10月31日 星期二 22时47分13秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 23 + 3;
const int INF = 0x3f3f3f3f;
int testCase, n;
int cnt[MAX_N];
int ans;

inline void dfs(int depth) {
if (depth >= ans) return;
int res = depth;

int h1, t1, h2, t2, h3, t3;
h1 = t1 = 3, h2 = t2 = 3, h3 = t3 = 3;

for (int i = 3; i <= 15; ++i) {

if (cnt[i]) {
t1 = i;
if (t1 - h1 >= 4 && i < 15) { // 单顺子
for (int j = h1; j <= t1 - 4; ++j) { //
for (int k = j; k <= t1; ++k) --cnt[k]; //
dfs(depth + 1);
for (int k = j; k <= t1; ++k) ++cnt[k]; //
}
}
}
else h1 = i + 1;

if (cnt[i] >= 2) {
t2 = i;
if (t2 - h2 >= 2 && i < 15) {
for (int j = h2; j <= t2 - 2; ++j) {
for (int k = j; k <= t2; ++k) cnt[k] -= 2;
dfs(depth + 1);
for (int k = j; k <= t2; ++k) cnt[k] += 2;
}
}
}
else h2 = i + 1;

if (cnt[i] >= 3) {
t3 = i;

if (t3 - h3 >= 1 && i < 15) { // 三顺子
for (int j = h3; j <= t3 - 1; ++j) {
for (int k = j; k <= t3; ++k) cnt[k] -= 3;
dfs(depth + 1);
for (int k = j; k <= t3; ++k) cnt[k] += 3;
}
}

cnt[i] -= 3;

for (int j = 3; j <= 17; ++j) if (i != j && cnt[j] >= 1) { // 三带一
--cnt[j];
dfs(depth + 1);
++cnt[j];
}

for (int j = 3; j <= 15; ++j) if (i != j && cnt[j] >= 2) { // 三带二
cnt[j] -= 2;
dfs(depth + 1);
cnt[j] += 2;
}

cnt[i] += 3;
}
else h3 = i + 1;

if (cnt[i] >= 4) {
cnt[i] -= 4;

for (int j = 3; j <= 17; ++j) if (i != j && cnt[j] >= 1) { // 四带两张不同单牌
for (int k = 3; k <= 17; ++k) if (i != k && cnt[k] >= 1) {
--cnt[j]; --cnt[k];
dfs(depth + 1);
++cnt[j]; ++cnt[k];
}
}

for (int j = 3; j <= 15; ++j) if (i != j && cnt[j] >= 2) {
for (int k = 3; k <= 15; ++k) if (i != k && cnt[k] >= 2) { // 四带两对不同的单牌
cnt[j] -= 2; cnt[k] -= 2;
dfs(depth + 1);
cnt[j] += 2; cnt[k] += 2;
}
}

cnt[i] += 4;
}
}

if (cnt[16] >= 1 && cnt[17] >= 1) {
--cnt[16]; --cnt[17];
dfs(depth + 1);
++cnt[16]; ++cnt[17];
}

for (int i = 3; i <= 17; ++i) if (cnt[i]) ++res; // 单牌出完

ans = min(ans, res);
}


int main()
{
testCase = readIn<int>();
n = readIn<int>(); //

while (testCase--) {

memset(cnt, 0, sizeof cnt);
ans = 13;

for (int i = 1; i <= n; ++i) {
int a = readIn<int>(), b = readIn<int>();
if (a == 0) ++cnt[15 + b]; // king
else if (a == 1 || a == 2) ++cnt[13 + a]; // A and 2
else ++cnt[a];
}

dfs(0);
printf("%d\n", ans);
}
return 0;
}

Day 2

跳石头

描述

一年一度的"跳石头"比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 $N$ 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达
终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 $M$ 块岩石(不能移走起点和终点的岩石)。

$D \leq M \leq N \leq 50000, 1 \leq L \leq 10^{9}$

分析

上一次做这道题目的时候还是去年的 10 月,当时太 Naive,怎么都想不明白为什么最大化最小值要二分qwq

好了,首先很明显这是一个最大化最小值问题,我们可以通过二分答案来做。

首先在读入起点和终点之间的石头距离起点的距离后,将起点和终点也加入进去($d[0] = 0, d[N] = L$)。

令 $check(x)$ 为是否可以安排石头的位置使得相隔最近的两块石头之间的距离不小于 $x$。

那么我们需要求出最大的那个 $x$,我们用贪心的思想来判断,$pos$ 为上一个没有挪走的石块。

如果 $d[i] - d[pos] <d$ ,那么我们需要将第 $i$ 块石头拿走。

否则,更新 $pos$ 即可。

时间复杂度 $\Theta(nlogn)$ 。

这里提一下二分中的小技巧,如果是最大化最小值我们通常在左闭右开的区间中二分:

1
2
3
4
5
6
while (r - l > 1) { // [l, r)
int mid = (l + r) >> 1;
if (check(mid)) l = mid;
else r = mid;
}
ans = l;

反之,如果我们要最小化最大值,则通常在左开右闭的区间中二分:

1
2
3
4
5
6
while (r - l > 1) { // (l, r]
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid;
}
ans = r;

代码

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
//  Created by ZJYelizaveta on Friday, October 20, 2017 AM08:54:05 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 50000 + 3;
const int INF = 0x3f3f3f3f;
int L, N, M;
int d[MAX_N];

inline bool check(int x) {
int cnt = M, pos = 0;
for (int i = 1; i < N + 2; ++i) {
if (d[i] - d[pos] < x) --cnt;
else pos = i;
}
if (cnt >= 0) return true;
return false;
}

int main()
{
L = readIn<int>(), N = readIn<int>(), M = readIn<int>();
for (int i = 1; i <= N; ++i) d[i] = readIn<int>();
d[N + 1] = L; d[0] = 0;

int l = 1, r = L + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid;
else r = mid;
}
printf("%d\n", l);
return 0;
}

子串

描述

有两个仅包含小写英文字母的字符串 $A$ 和 $B$。现在要从字符串 $A$ 中取出 $k$ 个互不重
叠的非空子串,然后把这 $k$ 个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串 $B$ 相等?

注意:子串取出的位置不同也认为是不同的方案 。

$1 \leq n \leq 1000, 1 \leq m \leq 200, 1 \leq k \leq m$

分析

是一道思维难度很好的动态规划题目,动态规划一直都是我的弱项,要加强呀qwq

一开始看这道题目的时候很容易就想到动态规划,然后开始肝转移方程。

令 $dp[i][j][k]$ 为 A 串匹配到第 $i$ 个位置,B 串匹配到第 $j$ 个位置,已经用了 $k$ 个子串。

那么我们有转移方程:

好像很对的样子,恩,就是这样的。诶,好像有点点不对,如果我们不选择当前的字符怎么办,这个决策好像并没有被考虑进去。

上面的脑洞作废,重新开始,我们分情况来讨论。

我们令 $f[i][j][k]$ 为 A 串匹配到第 $i$ 个位置,B 串匹配到第 $j$ 个位置,已经用了 $k$ 个子串,一定会用 A 串的第 $i$ 个字符串方案数。

令 $g[i][j][k]$ 为 A 串匹配到第 $i$ 个位置,B 串匹配到第 $j$ 个位置,已经用了 $k$ 个子串的总方案数。

考虑转移方程先考虑 $f[i][j][k]$,当 $strA[i] = strB[j]$:

如果 A 串的第 $i$ 个字符自己成为一个子串那么 $f[i][j][k] = g[i - 1][j - 1][k - 1]$;
如果 A 串的第 $i$ 个字符和前面的字符串成为一串,那么 $f[i][j][k] = f[i - 1][j - 1][k]$。

这样一来有转移方程

反之,若 $strA[i] \neq strB[j]$,那么

考虑 $g[i][j][k]$,

可以理解为,$g[i][j][k]$ 等于上一阶段不用 $strA[i - 1]$ 做为子串的方案数,加上使用 $strA[i - 1]$ 做为子串的方案数。

综上所述,我们有转移方程:

然后,如果我们转移方程开三维的话,会 MLE 所以考虑将第一维滚动一下。

代码

$70 \%$

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
//  Created by ZJYelizaveta on Friday, October 20, 2017 AM09:28:35 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 1000 + 3;
const int MAX_M = 100 + 3;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int n, m, K;
char strA[MAX_N], strB[MAX_M];
int f[MAX_N][MAX_M][MAX_M], g[MAX_N][MAX_N][MAX_M];

inline void solve() {
g[0][0][0] = 1;
for (int i = 1; i <= n; ++i) {
g[i][0][0] = 1;
for (int j = 1; j <= m; ++j) {
if (strA[i] == strB[j]) {
for (int k = 1; k <= min(j, K); ++k) {
f[i][j][k] = (g[i - 1][j - 1][k - 1] + f[i - 1][j - 1][k]) % MOD;
g[i][j][k] = (g[i - 1][j][k] + f[i][j][k]) % MOD;
}
}
else {
for (int k = 1; k <= min(j, K); ++k) g[i][j][k] = g[i - 1][j][k];
}
}
}
printf("%d\n", (g[n][m][K] % MOD + MOD) % MOD);
}

int main()
{
n = readIn<int>(), m = readIn<int>(), K = readIn<int>();
scanf("%s", strA + 1); scanf("%s", strB + 1);

solve();

return 0;
}

$100 \%$

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
//  Created by ZJYelizaveta on Friday, October 20, 2017 PM02:48:04 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 1000 + 3;
const int MAX_M = 200 + 3;
const int MAX_K = 200 + 3;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int n, m, K;
char strA[MAX_N], strB[MAX_N];
int f[MAX_N][MAX_K], g[MAX_N][MAX_K];

inline void solve() {
g[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = m; j >= 1; --j) {
if (strA[i] == strB[j]) {
for (int k = min(j, K); k >= 1; --k) {
f[j][k] = (g[j - 1][k - 1] + f[j - 1][k]) % MOD;
g[j][k] = (g[j][k] + f[j][k]) % MOD;
}
}
else {
for (int k = min(j, K); k >= 1; --k) f[j][k] = 0;
}
}
}
printf("%d\n", (g[m][K] % MOD + MOD) % MOD);
}

int main()
{
n = readIn<int>(), m = readIn<int>(), K = readIn<int>();
scanf("%s", strA + 1); scanf("%s", strB + 1);

solve();

return 0;
}

运输计划

描述

公元 2044 年,人类进入了宇宙纪元。
​L 国有 $n$ 个星球,还有 $n - 1$ 条双向航道,每条航道建立在两个星球之间,这 $n - 1$ 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司, 该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 $u_{i}$ 号星球沿最快的宇航路径飞行到 $v_{i}$ 号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 $j$,任意飞船驶过它所花费的时间为 $t_{j}$,并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 $m$ 个运输计划。在虫洞建设完成后,这 $m$ 个运输计划会同时开始,所有飞船一起出发。当这 $m$ 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

$n , m \leq 300000$

分析

做这道题目的时候,我大概是一条没有梦想的咸鱼 qwq

部分分的话有 $\Theta(n^{2})$ 的 50 分和 $m = 1$ 的 10 分,也就是暴力有 60 分,总体来说暴力分还是美滋滋的 qwq

$\Theta(n^{2})$ 的就是枚举那一条边改为虫洞,至于 $m = 1$ 的部分就 $\Theta(n)$ 扫一遍即可。

考虑正解。

因为 “这 $m$ 个运输计划会同时开始,所有飞船一起出发” ,那么我们所求的其实就是最小化耗时最长的飞船的飞行时间,这是一个最小化最大值的问题,可以用二分来解决,那么每次二分一个时间 $mid$ 然后 check 一下。

还有一个套路就是在计算在 $u_{i}$ 和 $v_{i}$ 两点之间的耗费时间(距离)的时候,可以用 倍增 在 $\Theta(logn)$ 的时间内计算。

现在要考虑一个问题如何在树上比较高效的 check 将一条边的时间变为 $0$ 后,$m$ 条路径的最大时间最小小于 $mid$ 。

我们先倍增预处理 $fa[i][j]$ 即 $i$ 的第 $2^{j}$ 级祖先,以及 $dis[i][j]$ 为从 $i$ 出发向上条 $2^{j}$ 级的路径长度。那么如果两点$u, v$ 之间的路径长度小于等于 $mid$ 则忽略,否则考虑在 $u, v$ 之间的路径中选择一条边,将这条边的权值变为 $0$ 。

那么问题就变为:check 求出两点之间距离大于 $mid$ 的路径的交集中的边权最大的边,看去掉这条边之后,是否满足 $m$ 条路径的最大时间最小小于 $mid$ 。

考虑求路径交集中的最长路径,我们有两种方法:

方法一

路径 (a, c)(b, d) 之间的交集必定在 LCA(a, b)LCA(a, c)LCA(a, d)LCA(b, c)LCA(b, d)LCA(c, d) 这六个点之间。暴力模拟一下求交集的过程,由于思想比较暴力,UOJ 上的 hack 数据会 TLE,但是对于官方数据还是可行的。

方法二

我觉的方法二更妙一些 qwq

记 $total$ 为两点之间距离大于 $mid$ 的路径数量,而 $cnt_{i}$ 为这些路径中边 $e_{i}$ 被经过的次数。那么 $cnt_{i} = total$ 意味着边 $e_{i}$ 为这些路径的交集中的一条边。

每一轮二分都重新计算一次的时间复杂度为 $\Theta(n^{2})$ ,这显然是不现实的。我们需要一个时间复杂度更优的方法,来维护每一条边被经过的次数。

这里就要用到树上前缀和了。

那么,如果要将一条边权变为 $0$ 怎么能较为高效的做到呢?这个和 NOIP 2012 借教室 一题中,我们用前缀和差分的思想差不多。在线性序列上,如果要将 $[l, r]$ 的区间 +k ,需要进行如下的操作:

那么令 $sum_{i}$ 为前 $i$ 位的前缀和,那么 $sum_{i}$ 可以表示为 $sum_{i} = \sum_{j = 1}^{i}a_{i}$ ,如图所示:

那么如果在树上做前缀和呢?令 $sum[i]$ 为结点 $i$ 到 $i$ 的父亲这条边被经过的次数,$dis_{i}$ 为顶点 $i$ 到其父亲边上的权值。

树上两点 $u, v$ 之间的距离为 $dis[u] + dis[v] - dis[lca(u, v)]$ ,更新 $u, v$ 之间路径被经过的次数则进行操作 ++sum[u] , ++sum[v] , sum[lca(u, v)] - 2 ,树上前缀和则为 $sum_{i} = \sum_{k \in son(i)}sum_{k}$ 。

我们可以利用树的 dfs 序,在 $\Theta(n)$ 的时间复杂度内计算出 $sum_{i}$ 的前缀和。

总时间复杂度 $\Theta(nlogn + mlogn + 2logn(m + n))$ 。

代码

$60 \%$

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
//  Created by ZJYelizaveta on Wednesday, November 01, 2017 AM09:10:39 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100000 + 3;
const int MAX_M = 3000 + 3;
const int INF = 0x3f3f3f3f;
const int MAX_LOG_N = 15 + 3;
int n, m;
struct Edge {
int to; ll w;
Edge(int to, ll w) : to(to), w(w) {}
};
vector<Edge> G[MAX_N << 1];
int s[MAX_N], t[MAX_N]; // start , end;

inline void addEdge(int from, int to, ll cost) {
G[from].push_back(Edge(to, cost));
G[to].push_back(Edge(from, cost));
}

int depth[MAX_N], fa[MAX_N];
ll val[MAX_N];
inline void dfs(int u, int f) {
depth[u] = depth[f] + 1; fa[u] = f;
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.to == f) continue;
val[e.to] = e.w;
dfs(e.to, u);
}
}

inline void solve1(int u, int v) {
ll res = 0, mx = 0;
if (depth[u] < depth[v]) swap(u, v);

while (depth[u] > depth[v]) {
res += val[u];
mx = max(mx, val[u]);
u = fa[u];
}

while (u != v) {
res += val[u]; res += val[v];
mx = max(mx, max(val[u], val[v]));
u = fa[u], v = fa[v];
}

printf("%lld\n", res - mx);
}

int road[MAX_M][MAX_M];
inline ll calculate(int i, int u, int v) {
ll res = 0;
if (depth[u] < depth[v]) swap(u, v);

while (depth[u] > depth[v]) {
res += val[u];
road[u][i] = 1;
u = fa[u];
}

while (u != v) {
res += val[u]; res += val[v];
road[u][i] = 1; road[v][i] = 1;
u = fa[u]; v = fa[v];
}

return res;
}

ll ans[MAX_N];
inline void solve2() {
ll res = -1;
memset(road, 0, sizeof road);
for (int i = 1; i <= m; ++i) {
ans[i] = calculate(i, s[i], t[i]);
res = max(res, ans[i]);
}

for (int i = 1; i <= n; ++i) { //
ll temp = 0;
for (int j = 1; j <= m; ++j) {
temp = max(temp, (ll)ans[j] - val[i] * road[i][j]); //
}
if (res == -1 || res > temp) res = temp;
}
printf("%lld\n", res);
}

int main()
{
n = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= n - 1; ++i) {
int u = readIn<int>(), v = readIn<int>(), w = readIn<ll>();
addEdge(u, v, w);
}
for (int i = 1; i <= m; ++i) s[i] = readIn<int>(), t[i] = readIn<int>();

dfs(1, 0);

if (m == 1) solve1(s[1], t[1]);
else solve2();
return 0;
}

方法一:

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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
//  Created by ZJYelizaveta on Wednesday, November 01, 2017 PM02:10:47 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 300000 + 3;
const int MAX_LOG_N = 15 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
struct Edge {
int to, next, w;
}edge[MAX_N << 1];
int head[MAX_N], cnt = 0;
int s[MAX_N], t[MAX_N];
int depth[MAX_N], fa[MAX_N][MAX_LOG_N], dis[MAX_N][MAX_LOG_N], maxVal[MAX_N][MAX_LOG_N];

inline void addEdge(int from, int to, int w) {
edge[++cnt].to = to; edge[cnt].w = w; edge[cnt].next = head[from]; head[from] = cnt;
edge[++cnt].to = from; edge[cnt].w = w; edge[cnt].next = head[to]; head[to] = cnt;
}

inline void dfs(int u, int f) {
depth[u] = f == 0 ? 0 : depth[f] + 1; fa[u][0] = f;
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v == f) continue;

dis[v][0] = edge[i].w;
maxVal[v][0] = edge[i].w;
dfs(v, u);
}
}

int allCost, maxCost, lca;
inline void query(int u, int v) {
allCost = 0, maxCost = 0, lca = 0;

if (depth[u] < depth[v]) swap(u, v);

for (int i = MAX_LOG_N - 1; i >= 0; --i) {
if (depth[u] - (1 << i) >= depth[v]) {
allCost += dis[u][i];
maxCost = max(maxCost, maxVal[u][i]);

// printf("%d %d %d %d %d\n", u, i, fa[u][i], dis[u][i], maxVal[u][i]);
u = fa[u][i];
}
}

if (u == v) {
lca = u; return;
}

for (int i = MAX_LOG_N - 1; i >= 0; --i) {
if (depth[u] - (1 << i) >= 0 && fa[u][i] != fa[v][i]) {
allCost += dis[u][i]; allCost += dis[v][i];
maxCost = max(maxCost, max(maxVal[u][i], maxVal[v][i]));

// printf("%d %d %d %d %d\n", u, i, fa[u][i], dis[u][i], maxVal[u][i]);
// printf("%d %d %d %d %d\n", v, i, fa[v][i], dis[v][i], maxVal[v][i]);

u = fa[u][i]; v = fa[v][i];
}
}

allCost = allCost + dis[u][0] + dis[v][0];
maxCost = max(maxCost, max(maxVal[u][0], maxVal[v][0]));
lca = fa[u][0];
}

int sum[MAX_N];
inline void prepare() {
for (int j = 1; j < MAX_LOG_N; ++j) {
for (int i = 1; i <= n; ++i) {
fa[i][j] = fa[fa[i][j - 1]][j- 1];
dis[i][j] = dis[i][j - 1] + dis[fa[i][j - 1]][j - 1];
maxVal[i][j] = max(maxVal[i][j - 1], maxVal[fa[i][j - 1]][j - 1]);
}
}

/*
for (int j = 0; j < MAX_LOG_N; ++j) {
for (int i = 1; i <= n; ++i) {
printf("%d %d %d %d %d\n", i, j, fa[i][j], dis[i][j], maxVal[i][j]);
}
printf("\n");
}
*/

for (int i = 1; i <= m; ++i) {
query(s[i], t[i]);
sum[i] = allCost;
}

// for (int i = 1; i <= m; ++i) printf("%d %d\n", i, sum[i]);
}

inline int LCA(int u, int v) {
query(u, v);
return lca;
}

inline int length(int u, int v) {
query(u, v);
return allCost;
}

inline int maxLength(int u, int v) {
query(u, v);
return maxCost;
}

inline int inPath(int a, int b, int c, int d) {
int len1 = length(a, c), len2 = length(a, d), len3 = length(c, d);

if (len2 < len1) {
swap(c, d); len1 = len2;
}

int len4 = length(b, d);
return (len1 + len3 + len4 == length(a, b)) ? len3 : 0;
}

inline int getIntersection(int &a, int &b, int c, int d) {
int u = -1, v = -1, nowLength = 0;

vector<int> vec; // 为什么把 vector 放在外面会超时? 求教qwq
vec.push_back(LCA(a, b));
vec.push_back(LCA(a, c));
vec.push_back(LCA(a, d));
vec.push_back(LCA(b, c));
vec.push_back(LCA(b, d));
vec.push_back(LCA(c, d));
vec.erase(unique(vec.begin(), vec.end()), vec.end());

for (int i = 0; i < (int)vec.size(); ++i) {
for (int j = i + 1; j < (int)vec.size(); ++j) {
int len = inPath(a, b, vec[i], vec[j]);

if (len > nowLength && inPath(c, d, vec[i], vec[j])) {
u = vec[i]; v = vec[j]; nowLength = len;
}
}
}
a = u, b = v;
return nowLength;
}

inline bool check(int lim) {
int a = -1, b = -1;
for (int i = 1; i <= m; ++i) {
if (sum[i] <= lim) continue;
if (a == -1 && b == -1) a = s[i], b = t[i];
else if (getIntersection(a, b, s[i], t[i]) <= 0) return false;
}

int decrease = maxLength(a, b);
for (int i = 1; i <= m; ++i) {
if (sum[i] - decrease > lim) return false;
}
return true;
}

inline void solve() {
int l = -1, r = 300000000;

while (r - l > 1) {
int mid = (l + r) >> 1;
// printf("%d %d %d\n", l, r, mid);
if (check(mid)) r = mid;
else l = mid; //
}
printf("%d\n", r);
}

int main()
{
n = readIn<int>(), m = readIn<int>();
memset(head, -1, sizeof head);
for (int i = 1; i <= n - 1; ++i) {
int u = readIn<int>(), v = readIn<int>(), w = readIn<int>();
addEdge(u, v, w);
}
for (int i = 1; i <= m; ++i) s[i] = readIn<int>(), t[i] = readIn<int>();

dfs(1, 0);
prepare();
solve();

// fprintf(stderr, "Time used : %.3f\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}

好了,在 Lantern 的帮助下明白了为什么吧 vector 放在外面会 TLE。就是如果吧 vector 放在外面每一次求 (a, c) , (b, d) 线段的交的时候把他们和之前的 LCA 都累加了,求完线段交之后又没有清空 vector (因为 vector 此时是作为全局变量而言的),这样每次去重的效率就很低,自然而然就 TLE 了

$100 \%$

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
//  Created by ZJYelizaveta on 2017年11月02日 星期四 17时20分28秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 300000 + 3;
const int MAX_LOG_N = 17 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
struct Edge {
int to, w;
Edge (int to, int w) : to(to), w(w){}
};
vector<Edge> G[MAX_N << 1];
int s[MAX_N], t[MAX_N];
int depth[MAX_N], dis[MAX_N], val[MAX_N], fa[MAX_N][MAX_LOG_N];
int lca[MAX_N], cost[MAX_N];

inline void addEdge(int from, int to, int cost) {
G[from].push_back(Edge(to, cost));
G[to].push_back(Edge(from, cost));
}

int pos[MAX_N], timeStamp = 0;
inline void dfs(int u, int f) {
pos[++timeStamp] = u;
depth[u] = f == 0 ? 0 : depth[f] + 1; fa[u][0] = f;
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.to == f) continue;

val[e.to] = e.w;
dis[e.to] = dis[u] + e.w;
dfs(e.to, u);
}
}

inline int LCA(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);

for (int i = MAX_LOG_N - 1; i >= 0; --i) {
if (depth[a] - (1 << i) >= depth[b]) {
a = fa[a][i];
}
}

if (a == b) return a;

for (int i = MAX_LOG_N - 1; i >= 0; --i) {
if (depth[a] - (1 << i) >= 0 && fa[a][i] != fa[b][i]) {
a = fa[a][i], b = fa[b][i];
}
}

return fa[a][0];
}

inline void prepare() {
// for (int i = 1; i <= n; ++i) printf("%d ", pos[i]); printf("\n");
// for (int i = 1; i <= n; ++i) printf("%d fa = %d depth = %d val = %d dis = %d\n", i, fa[i][0], depth[i], val[i], dis[i]);

for (int j = 1; j < MAX_LOG_N; ++j) {
for (int i = 1; i <= n; ++i) {
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}

for (int i = 1; i <= m; ++i) {
lca[i] = LCA(s[i], t[i]);
cost[i] = dis[s[i]] + dis[t[i]] - 2 * dis[lca[i]];
}
// for (int i = 1; i <= m; ++i) printf("%d %d %d\n", i, lca[i], cost[i]);
}

int sum[MAX_N];
inline bool check(int lim) {
int cnt = 0;
memset(sum, 0, sizeof sum);

for (int i = 1; i <= m; ++i) {
if (cost[i] <= lim) continue;
++cnt;
++sum[s[i]], ++sum[t[i]], sum[lca[i]] -= 2;
}

if (cnt == 0) return true;
for (int i = n; i >= 1; --i) {
sum[fa[pos[i]][0]] += sum[pos[i]];
}

int dec = 0; // max decrease
for (int i = 1; i <= n; ++i) {
if (sum[i] == cnt) dec = max(dec, val[i]);
}

for (int i = 1; i <= m; ++i) {
if (cost[i] - dec > lim) return false;
}
return true;
}

inline void solve() {
int l = -1, r = INF;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid;
}
printf("%d\n", r);
}

int main()
{
// freopen("test.in", "r", stdin);

n = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= n - 1; ++i) {
int u = readIn<int>(), v = readIn<int>(), w = readIn<int>();
addEdge(u, v, w);
}
for (int i = 1; i <= m; ++i) s[i] = readIn<int>(), t[i] = readIn<int>();

dfs(1, 0);
prepare();
solve();

return 0;
}

写完这个树上前缀和这个方法后,美滋滋的去 UOJ 上交,以为可以过 Extra test,结果还是 97 分qwq,不是 TLE 但是 WA 了。内心比较崩溃,很仔细的看了好几遍程序,没问题呀,绝望之下改了一下 MAX_LOG_N 的大小,再交,然后 A 了qwq。可是 $ln(3 \times 10^{5}) = 13$ 不是吗,$ln$ 的底数可是自然数 $e$ 呀,[关爱智障的眼神].jpg

Share