NOIP 2013 整理

Day 1

转圈游戏

描述

$n$ 个小伙伴围成一个圈(编号从 $0 \sim 1$),按照顺时针方向给 $n$ 个位置标号,每次每个人向后移动 $m$ 个位置,问操作 $10^{k}$ 次的时候,第 $x$ 号小伙伴走到了第几号位置?
$1 < n < 10^{6}, 0 < m < n, 1 \leq x \leq n, 0 < k < 10^{9}$

分析

我们可以用式子表示出 $x$ 号小朋友最后的位置:

我们可以将式子恒等变形一下,变成一个比较容易求的形式:

这样一来式子的关键就变成了做快速幂的时候顺便取模。

mdzz,第一次好把快速幂写错了qwq

代码

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
//  Created by ZJYelizaveta on Tuesday, October 17, 2017 AM08:58:17 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 = 1000000 + 3;
const int INF = 0x3f3f3f3f;
ll n, m, k, x;

inline ll quickPow(ll a, ll b) {
ll res = 1; //
while (b) {
if (b & 1) (res *= a) %= n;
(a *= a) %= n;
b >>= 1;
}
return res;
}


int main()
{
n = readIn<ll>(), m = readIn<ll>(), k = readIn<ll>(), x = readIn<ll>();

ll temp = quickPow(10, k);

x = (x + m * quickPow(10, k) % n + n) % n;
printf("%lld\n", x);
return 0;
}

火柴排队

描述

有两个长为 $n$ 的序列 $a, b$,定义两个序列的距离为
每个序列中相邻两个位置的数可以交换,问最少需要交换多少次,可以最小化这个式子?
答案对 $99999997$ 取模。
$1 \leq n \leq 10^{5}, 0 \leq $ 火柴高度 $\leq 2^{31} - 1$

分析

我们需要最小化 $\sum_{i = 1}^{n}(a_{i} - b_{i})^{2}$,相当于要最小化 $(a_{i} - b_{i})$,也就是说 $a$ 序列第 $k$ 大的元素必须和序列 $b$ 中第 $k$ 大的元素($k \in [1, n]$)的位置必须一样。

可以这样来理解:
$A$ : $1$ $998$ $2$ $87$ $3$ $3$
$B$ : $1$ $6$ $2$ $5$ $3$ $4$

那么我们我们可以把 $a, b$ 先离散化,那么问题将转化为 $b$ 序列要交换几次可以令其等于 $a$,但是我们还是没有一个具体成形的算法。

好了,这道题目的精华在于对于新建序列!假设我们现在有离散化后的序列 $a = \{4, 3, 1, 2\}$,$b = \{1, 3, 2, 4\}$。

我们令 $q[a[i]] = b[i]$,相当于以 $a[i]$ 为关键字对序列 $b[i]$ 排序。

若序列 $a$ 与序列 $b$ 相等,那么此时 $q[a[i]]$ 应该等于 $a[i]$ 的,也就是 $q[i] = i$。

那么也就是说如果我们想让序列 $a$ 与序列 $b$ 相等,那么我们需要让 $q$ 升序排列。

问题就变为,将原本乱的 $q$ 序列升序排列的最少交换次数。

诶,这不就是逆序对吗?

于是,用树状数组求之即可。

代码

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
//  Created by ZJYelizaveta on Tuesday, October 17, 2017 AM09:22:55 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 MOD = 99999997;
const int INF = 0x3f3f3f3f;
int n;
int a[MAX_N], b[MAX_N];
int c[MAX_N], d[MAX_N];
int q[MAX_N];
int ans;

namespace fenwickTree {
int vec[MAX_N];

inline int lowbit(int x) {
return x & (-x);
}

inline void modify(int id, int x) {
while (id <= n) {
vec[id] += x;
id += lowbit(id);
}
}

inline int query(int id) {
int res = 0;
while (id >= 1) {
res += vec[id];
id -= lowbit(id);
}
return res;
}
}
using namespace fenwickTree;

// 60%
/*
inline void solve() {
ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) if (i < j && q[i] > q[j]) {
swap(q[i], q[j]);
++ans;
}
}
printf("%d\n", (ans % MOD + MOD) % MOD);
}
*/

// 100%
inline void solve() {
ans = 0;
for (int i = n; i >= 1; --i) {
// printf("%d %d\n", q[i], query(q[i] - 1));
ans += query(q[i] - 1);
modify(q[i], 1);
if (ans >= MOD) ans -= MOD;
}

printf("%d\n", (ans % MOD + MOD) % MOD);
}

inline bool cmp1(int i, int j) {
return a[i] < a[j];
}

inline bool cmp2(int i, int j) {
return b[i] < b[j];
}

int main()
{
n = readIn<int>();
for (int i = 1; i <= n; ++i) a[i] = readIn<int>(), c[i] = i;
for (int i = 1; i <= n; ++i) b[i] = readIn<int>(), d[i] = i;

sort(c + 1, c + n + 1, cmp1); sort(d + 1, d + n + 1, cmp2);

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

memset(q, 0, sizeof q);
for (int i = 1; i <= n; ++i) q[c[i]] = d[i];
// for (int i = 1; i <= n; ++i) printf("%d ", q[i]); printf("\n");

solve();
return 0;
}

货车运输

描述

A 国有 $n$ 座城市编号,从 $1$ 到 $n$,城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 $q$ 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

$0 < n < 10^{4}, 0 < m < 5 \times 10^{4}, 0 < q < 3 \times 10^{4}, 0 \leq z \leq 10^{5}$

分析

模拟的时候做到这道题目之剩下 1.5h,有点慌,看到这道题目的时候,诶,不就是最大生成树重构图,然后在树上询问吗qwq

这道题目实际上是最大化两点之间的最小瓶颈路,而这种路径一定存在于最大生成树中。考试的时候没有仔细想,这里简要证明一下。

证明

这里我们简称最大化最小瓶颈路为最大瓶颈路。

假设两点 $u, v$ 之间的最大瓶颈路不在最大生成树中。

那么我们将这条路径加入最大生成树中,此时的树中必定存在一个环,我们可以删除环上权值最小的一条边使之又成为一棵树,那么现在的生成树的权值一定大于之前的最大生成树的权值,这与我们之前定义的矛盾。

故,任意两点之间的最大瓶颈路在最大生成树中,证毕。

我们用 Kruskal 重构图,在 $\Theta(n + mlogm)$ 的时间内建出这个图的最大生成树。

然后我们可以在树上询问,但是如果每次询问都 dfs,这样的时间复杂度是平方级别的。怎样来优化时间复杂度呢?

考虑先预处理处每一个点的 depth[],任意两点之间的 minVal[][] ,fa[][],然后在求两点 LCA 倍增往上跳的时候顺便计算一下两点之间的最小权值即为答案。

P.S. 在求两地之间的 LCA 并计算两点之间的最小权值,注意一定要先取最小值再往上跳,因为这里的意义是 以这个点 $u, v$ 向上跳 $2^{i}$ 的最小值,如果先跳的话当然会 WA 呀qwq

在这里调了 20 多分钟的 zz

代码

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
//  Created by ZJYelizaveta on 2017年10月18日 星期三 18时19分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 = 10000 + 3;
const int MAX_M = 50000 + 3;
const int MAX_LOG_N = 12 + 3;
const int MAX_Q = 30000 + 3;
const int INF = 0x3f3f3f3f;
int n, m, q;

struct Edge {
int to, cost;
Edge (int to, int cost) : to(to), cost(cost){} //
};
vector<Edge> G[MAX_N << 1];
int depth[MAX_N];
int fa[MAX_N][MAX_LOG_N], minVal[MAX_N][MAX_LOG_N];
int p[MAX_N], c[MAX_N]; // each point's father, and it father's cost
namespace LCA {
inline void addEdge(int from, int to, int cost) {
G[from].push_back(Edge(to, cost));
G[to].push_back(Edge(from, cost));
}

inline void dfs(int u, int par) {
depth[u] = depth[par] + 1;
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.to == par) continue;
p[e.to] = u;
c[e.to] = e.cost;
// printf("%d %d %d\n", u, e.to, e.cost);
dfs(e.to, u);
}

}

inline void prepare() {
for (int i = 1; i <= n; ++i) {
fa[i][0] = p[i], minVal[i][0] = c[i];
// printf("%d %d %d\n", i, p[i], c[i]);
for (int j = 1; (1 << j) <= n; ++j) fa[i][j] = -1;
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i <= n; ++i) {
if (fa[i][j - 1] != -1) {
fa[i][j] = fa[fa[i][j - 1]][j - 1];
minVal[i][j] = min(minVal[i][j - 1], minVal[fa[i][j - 1]][j - 1]);
// printf("%d %d %d %d\n", i, j, fa[i][j], minVal[i][j]);
}
}
}

}

inline int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b); // a must be deeper than b
int lim;
for (lim = 1; (1 << lim) <= n; ++lim); --lim;

int ans = INF;
for (int i = lim; i >= 0; --i) {
if (depth[a] - (1 << i) >= depth[b]) {
ans = min(ans, minVal[a][i]);
a = fa[a][i];
// printf("%d %d %d %d %d\n", i, a, b, minVal[a][i], ans);
}
}

if (a == b) return ans;

for (int i = lim; i >= 0; --i) {
if (fa[a][i] != -1 && fa[a][i] != fa[b][i]) {
ans = min(ans, min(minVal[a][i], minVal[b][i])); //
a = fa[a][i], b = fa[b][i]; //
}
}
ans = min(ans, min(c[a], c[b]));
return ans;
}
}
using namespace LCA;

struct Tree {
int u, v, w;
bool operator < (const Tree &rhs) const {
return w > rhs.w;
}
}t[MAX_M];
int f[MAX_N];
namespace Kruskal {
inline int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}

inline void kruskal() {
sort(t + 1, t + m + 1);
// for (int i = 1; i <= m; ++i) printf("%d %d %d\n", t[i].u, t[i].v, t[i].w);

for (int i = 1; i <= n; ++i) f[i] = i;

for (int i = 1; i <= m; ++i) {
int x = find(t[i].u), y = find(t[i].v);

// printf("%d %d %d %d\n", t[i].u, t[i].v, x, y);
if (x != y) {
f[y] = x; //
// printf("%d %d %d\n", t[i].u, t[i].v, t[i].w);
addEdge(t[i].u, t[i].v, t[i].w);
}
}
}
}
using namespace Kruskal;

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

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

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

q = readIn<int>();
while (q--) {
int a = readIn<int>(), b = readIn<int>();
int x = find(a), y = find(b);
if (x != y) printf("-1\n");
else printf("%d\n", lca(a, b));
}
return 0;
}

Day 2

积木大赛

描述

今年比赛的内容是搭建一座宽度为 $n$ 的大厦,大厦可以看成由 $n$ 块宽度为 $1$ 的积木组成,第 $i$ 块积木的最终高度需要是 $h_{i} 。每次可以选择一个区间 $[L, R]$ 将区间内积木的高度都增加 $1$。问最少需要操作多少次,可以搭建出这座大厦?

$1 \leq n \leq 10^{5}, 0 \leq h_{i} \leq 10^{5}$

分析

整体来说这道题目还是比较简单的,并且解法也很多,可以用递归,线段树,贪心,动态规划等来解决。

这里我用的是比较容易理解的递归区间的方法,具体细节见代码。

代码

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
//  Created by ZJYelizaveta on Tuesday, October 17, 2017 PM02:10:00 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 INF = 0x3f3f3f3f;
int n;
int a[MAX_N];
int ans;

inline void dfs(int temp, int l, int r) {
if (l > r) return;

int val = INF, pos = 0;
for (int i = l; i <= r; ++i) {
if (a[i] < val) {
val = a[i]; pos = i;
}
}
ans += val - temp;
dfs(val, l, pos - 1);
dfs(val, pos + 1, r);
}

inline void solve() {
dfs(0, 1, n);
printf("%d\n", ans);
}

int main()
{
n = readIn<int>();
for (int i = 1; i <= n; ++i) a[i] = readIn<int>();

solve();
return 0;
}

花匠

描述

栋栋的花的高度可以看成一列整数 $h_{1} , h_{2} , \cdots , h_{n}$ 。设当一部分花被移走后,剩下的花的高度依次为 $g_{1} , g_{2} , \cdots , g_{m}$ ,则栋栋希望下面两个条件中至少有一个满足 :

条件 A : 对于所有的 $i$,$g_{2i} > g_{2i−1}$ ,且 $g_{2i} > g_{2i+1}$

条件 B : 对于所有的 $i$,$g_{2i} < g_{2i−1}$ ,且 $g_{2i} < g_{2i+1}$

注意上面两个条件在 $m = 1$ 时同时满足,当 $m > 1$ 时最多有一个能满足。
请问,栋栋最多能将多少株花留在原地。

$1 \leq n \leq 10^{5}, 0 \leq h_{i} \leq 10^{6}$

分析

诶,序列,好像可以用动态规划来解决,然后就开始想如何用动态规划来解决

我们可以将方案 A 和方案 B 用 $\Lambda$ 和 $V$ 型来表示,每次考虑第 $i- 1$ 朵花和第 $i$ 朵花之间的高度关系。

令 $dp[i][0]$ 为前 $i$ 朵花最后一朵花为最高点的最长长度,$dp[i][1]$ 为前 $i$ 朵花为最低点的最长的长度。

那么我们有转移方程 :

这里我们实际上不需要真的将这个 $dp$ 数组建立出来,只需要用一个 bool 变量来表示当前这个点是最高点还是最低点即可。

具体细节见代码qwq

代码

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
//  Created by ZJYelizaveta on Tuesday, October 17, 2017 PM03:21:18 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 INF = 0x3f3f3f3f;
int n;
int h[MAX_N];
int ansA, ansB;
bool flag;
// if flag == true, then at this moment this point is the highest
// else if flag == false, then at this moment this point is the lowest

int main()
{
n = readIn<int>();
for (int i = 1; i <= n; ++i) h[i] = readIn<int>();

ansA = ansB = 1;

for (int i = 2; i <= n; ++i) {
if ((flag && h[i] < h[i - 1]) || (!flag && h[i] > h[i - 1])) {
++ansA; flag = !flag;
}
}

flag = false;
for (int i = 2; i <= n; ++i) {
if ((flag && h[i] > h[i - 1]) || (!flag && h[i] < h[i - 1])) {
++ansB; flag = !flag;
}
}

int ans = ansA < ansB ? ansB : ansA;
printf("%d\n", ans);
return 0;
}

华容道

描述

小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道 : 给定一种局面,华容道是否根本就无法完成,如果能完成,最少需要多少时间。
小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的 :

  1. 在一个 $n \times m$ 棋盘上有 $n \times m$ 个格子,其中有且只有一个格子是空白的,其余 $n \times m - 1$ 个格子上每个格子上有一个棋子,每个棋子的大小都是 $1 \times 1$ 的
  2. 有些棋子是固定的,有些棋子则是可以移动的
  3. 任何与空白的格子相邻 ( 有公共的边 ) 的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

给定一个棋盘,游戏可以玩 $q$ 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 $i$ 次玩的时候,空白的格子在第 $EX_{i}$ 行第 $EY_{i}$ 列,指定的可移动棋子的初始位置为第 $SX_{i}$ 行第 $SY_{i}$ 列,目标位置为第 $TX_{i}$ 行第 $TY_{i} 列。
假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。

$1 \leq n , m \leq 30, q \leq 500$

分析

对于 $70 \%$ 的数据 BFS 可以轻松做到,正解我还没有想到 / 想明白qwq

代码

$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
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
//  Created by ZJYelizaveta on Tuesday, October 17, 2017 PM03:31:50 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 = 30 + 3;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int n, m, testCase;
int a[MAX_N][MAX_N];
int exe, eye, sxs, sys, tx, ty;
struct Edge {
int ex, ey, sx, sy, d;
Edge (int ex, int ey, int sx, int sy, int d) : ex(ex), ey(ey), sx(sx), sy(sy), d(d){}
};
int vis[MAX_N][MAX_N][MAX_N][MAX_N];

inline int bfs() {
queue<Edge> q;
q.push(Edge(exe, eye, sxs, sys, 0)); // 空白块的位置, 目标格子的位置
vis[exe][eye][sxs][sys] = 1;

while(!q.empty()) {
int ex = q.front().ex, ey = q.front().ey, sx = q.front().sx, sy = q.front().sy, d = q.front().d;
q.pop();

for (int i = 0; i < 4; ++i) {
int lx = ex + dx[i], ly = ey + dy[i];

if (lx < 1 || lx > n || ly < 1 || ly > m || !a[lx][ly]) continue;

if (lx == sx && ly == sy) {
if (vis[lx][ly][ex][ey]) continue;
if (ex == tx && ey == ty) return d + 1;
else {
q.push(Edge(lx, ly, ex, ey, d + 1));
vis[lx][ly][ex][ey] = 1;
}
}
else {
if (vis[lx][ly][sx][sy]) continue;
q.push(Edge(lx, ly, sx, sy, d + 1));
vis[lx][ly][sx][sy] = 1;
}
}
}
return -1;
}

inline void solve() {
while (testCase--) {
exe = readIn<int>(), eye = readIn<int>(), sxs = readIn<int>(), sys = readIn<int>(); tx = readIn<int>(), ty = readIn<int>();

memset(vis, 0, sizeof vis);
// q.push((Edge){ex, ey, sx, sy, 0});

printf("%d\n", (sxs == tx && sys == ty) ? 0 : bfs());
}
}


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

for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) a[i][j] = readIn<int>();
}

if (n <= 30) solve();

return 0;
}
Compartir