NOIP 2011 整理

Day 1

铺地毯

描述

为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标
系的第一象限)铺上一些矩形地毯。一共有 $n$ 张地毯,编号从 $1$ 到 $n$。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。

注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

$0 \leq n \leq 1000, 0 \leq a, b, g, k \leq 10^{5}$

分析

题目较为简单,是 NOIP Day1 T1 的水准。

$\Theta(n)$ 的扫一遍,如果这个点包含在某一张地毯中则更新答案。

代码

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 2017年09月02日 星期六 09时13分58秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

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

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int 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 INF = 0x3f3f3f3f;
int n;
struct Carpet {
int a, b, g, k;
}c[MAX_N];
int fx, fy;
int ans;

int main()
{
n = readIn();
for (int i = 0; i < n; ++i) {
c[i].a = readIn(), c[i].b = readIn(), c[i].g = readIn(), c[i].k = readIn();
}
fx = readIn(), fy = readIn();//final x and final y
ans = -1;
for (int i = 0; i < n; ++i) {
int x = c[i].a + c[i].g;
int y = c[i].b + c[i].k;
if (c[i].a <= fx && fx <= x && c[i].b <= fy && fy <= y) ans = i + 1;
}
printf("%d\n", ans);
return 0;
}

选择客栈

描述

丽江河边有 $n$ 家很有特色的客栈,客栈按照其位置顺序从 $1$ 到 $n$ 编号。每家客栈都按照某一种色调进行装饰(总共 $k$ 种,用整数 $0 \sim k-1$ 表示),且每家客栈都设有一家咖啡店,每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈,因此决定分别住在色调相同的两家客栈中。晚上,他们打算选择一家咖啡店喝咖啡,要求咖啡店位于两人住的两家客栈之间(包括他们住的客栈),且咖啡店的最低消费不超过 $p$。
他们想知道总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过 $p$ 元的咖啡店小聚。

$2 \leq n \leq 200000, 0 < k \leq 50, 0 \leq p \leq 100, 0 \leq$ 最低消费 $\leq 100$

分析

$\Theta(n^{2})$ 枚举可以拿到 60 分,我也不知道为什么是 60 呢!竟然没有越界qwq

$\Theta(n^{2})$ 这样的时间复杂度肯定是不行的,考虑优化时间复杂度到 $\Theta(n)$ 或 $\Theta(nlogn)$,同样也可以考虑关于关于颜色 $k$ 的时间复杂度哒。

像这种有关区间的计数,可以考虑固定其中一个端点,然后扫一下区间。

如果 $q[i].b \leq p$,令 $pos = i$ 则计算:

$sum[]$ 表示 $pos$ 以左颜色 $q[i].a$ 的颜色个数。

$cnt[]$ 表示当前颜色 $q[i].a$ 的个数。

$lastPos[]$ 表示颜色 $q[i].a$ 上一次出现的位置。

计算之后,更新 $cnt[], lastPos[]$ 即可。

代码

$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
//  Created by ZJYelizaveta on Thursday, October 19, 2017 AM08:49:42 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 INF = 0x3f3f3f3f;
int n, k, p;
struct Hotel {
int c, p;
}a[MAX_N];
int ans;

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

ans = 0;
for (int i = 1; i <= n; ++i) {
int color = a[i].c;
for (int j = i + 1; j <= n; ++j) if (a[j].c == color) {
// printf("%d %d\n", i, j);
for (int k = i; k <= j; ++k) {
if (a[k].p <= p) {
++ans; break;
}
}
}
}
printf("%d\n", ans);
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
//  Created by ZJYelizaveta on Thursday, October 19, 2017 PM03:37:49 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 MAX_K = 50 + 3;
const int MAX_P = 100 + 3;
const int INF = 0x3f3f3f3f;
int n, m, p;
struct Hotel {
int a, b;
}q[MAX_N];
int sum[MAX_K], cnt[MAX_K], lastPos[MAX_K];

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

for (int i = 1; i <= n; ++i) q[i].a = readIn<int>(), q[i].b = readIn<int>();

int pos = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
if (q[i].b <= p) pos = i; //

if (pos >= lastPos[q[i].a]) sum[q[i].a] = cnt[q[i].a];

ans += sum[q[i].a];
++cnt[q[i].a]; lastPos[q[i].a] = i;
}

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

mayan 游戏

描述

Mayan puzzle 是最近流行起来的一个游戏。游戏界面是一个 $7$ 行 $5$ 列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下:

  • 每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方

块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出样例说明中的图 6 到图 7);如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落(直到不悬空,参见下面图 1 和图 2);

  • 任一时刻,如果在一横行或者竖列上有连续三个或者三个以上相同颜色的方块,则

它们将立即被消除(参见图 1 到图 3)。

注意:

a) 如果同时有多组方块满足消除条件,几组方块会同时被消除(例如下面图 4,三个颜色为 $1$ 的方块和三个颜色为 $2$ 的方块会同时被消除,后剩下一个颜色为 $2$ 的方块)。

b) 当出现行和列都满足消除条件且行列共享某个方块时,行和列上满足消除条件的所有方块会被同时消除(例如下面图 5 所示的情形,$5$ 个方块会同时被消除)。

  • 方块消除之后,消除位置之上的方块将掉落,掉落后可能会引起新的方块消除。注意:掉落的过程中将不会有方块的消除。

    上面图 1 到图 3 给出了在棋盘上移动一块方块之后棋盘的变化。棋盘的左下角方块的坐标为 $(0, 0)$ 将位于 $(3, 3)$ 的方块向左移动之后,游戏界面从图 1 变成图 2 所示的状态,此时在一竖列上有连续三块颜色为 $4$ 的方块,满足消除条件,消除连续 $3$ 块颜色为 $4$ 的方块后,上方的颜色为 $3$ 的方块掉落,形成图 3 所示的局面。

分析

模拟的时候就是连暴力都不想写了,然后改题目的时候由于代码能力较差 写 + 调试 用了一上午,Sign

思路很简洁,因为已经限制了步数,那么我们用 dfs 就可以求解了,至于下落和消除就是模拟。

但是单纯的 dfs 回溯是不够的,我们需要一些剪枝和优化:

  • 因为我们要求方案的字典序最小,所以我们在平移的时候遵从一下几点

    • 在中间的时候向右交换(左边那个向右边移动字典序更小)
    • 当左边没有格的时候向左移动
    • 当右边的格子和自己相同时跳过
  • 最优化剪枝:不移动相同的色块

  • 可行性剪枝:若某种颜色的方块数量小于 $3$ 则无解

然后就是模拟 + 爆搜了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
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
//  Created by ZJYelizaveta on Monday, October 23, 2017 AM09:11:19 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
#pragma GCC optimize(3)
#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 = 7 + 3;
const int INF = 0x3f3f3f3f;
int n;
int color[MAX_N][MAX_N];
int cnt[MAX_N + 3];
struct Node {
int x, y, flag;
}ans[MAX_N];

inline bool empty() {
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 7; ++j) if (color[i][j]) return false; //
}
return true;
}

int num[10][10];
inline void drop() {
memset(num, -1, sizeof num);
for (int i = 0; i < 5; ++i) {
int k = 0;
for (int j = 0; j < 7; ++j) {
if (color[i][j]) num[i][k++] = j;
}
}
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 7; ++j) {
color[i][j] = num[i][j] == -1 ? 0 : color[i][num[i][j]]; // drop the square which in the middle of the row without another square beneath it
}
}
/*
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 7; ++j) printf("%d ", color[i][j]);
printf("\n");
}
*/
return; //
}

bool clear() {
bool flag = 0;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 7; ++j) if (color[i][j]) {

int k;
for (k = i; k + 1 < 5 && color[k + 1][j] == color[i][j]; ++k);

if (k - i >= 2) {
for (int l = i; l <= k; l++) {
int up = j, down = j;
while (up + 1 < 7 && color[l][up + 1] == color[i][j]) up++;
while (down - 1 >= 0 && color[l][down - 1] == color[i][j]) down--;
if (up - down >= 2) {
for (int h = down; h <= up; ++h) color[l][h] = 0;
}
}
for (int l = i; l <= k; ++l) color[l][j] = 0;
flag = true;
}
}
}

for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) if (color[i][j]) {

int k;
for (k = j; k + 1 < 7 && color[i][k + 1] == color[i][j]; k++);

if (k - j >= 2) {
for (int h = j; h <= k; ++h) {
int lft = i,rht = i;
while (lft - 1 >= 0 && color[lft - 1][h] == color[i][j]) lft--;
while (rht + 1 < 7 && color[rht + 1][h] == color[i][j]) rht++;
if (rht - lft >= 2) {
for (int l = lft; l <= rht; ++l) color[l][h] = 0;
}
}
for (int h = j; h <= k; h++) color[i][h] = 0;
flag = 1;
}
}
}
if (flag) return true;
else return false;
}


void dfs(int step) {
if (step > n) {
if (empty()) {
for (int i = 1; i <= n; ++i) {
if (ans[i].flag) {
printf("%d %d %d\n", ans[i].x + 1, ans[i].y, -1); // move the square which on [i, j]'s right to the left
}
else {
printf("%d %d %d\n", ans[i].x, ans[i].y, 1);
}
}
exit(0);
}
return;
}

int cnt[12];
memset(cnt, 0, sizeof cnt); // caculate
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 7; ++j) ++cnt[color[i][j]];
}

for (int i = 1; i <= 10; ++i) // if there is a color which its quantity is less than 3, it means that in this situation we have no solution
if (cnt[i] != 0 && cnt[i] < 3) return;

for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 7; ++j) if (color[i][j] != color[i + 1][j]) { // if the color between [i, j] and [i + 1, j] are the same, we don't need to swap them
ans[step].x = i; ans[step].y = j;
ans[step].flag = (!color[i][j]);

int temp[10][10];
memcpy(temp, color, sizeof temp);
swap(color[i][j], color[i + 1][j]);

drop();
while (clear()) drop();

dfs(step + 1);
ans[step].x = 0; ans[step].y = 0, ans[step].flag = 0;
memcpy(color, temp, sizeof color);
}
}
}


int main()
{
n = readIn<int>();
for (int i = 0; i < 5; ++i) {
for (int j = 0; ; ++j) {
color[i][j] = readIn<int>();
if (color[i][j] == 0) break;
// printf("%d ", color[i][j]);
}
// printf("\n");
}

dfs(1);
printf("-1\n");

return 0;
}

Day 2

计算系数

描述

给定一个多项式 $( ax + by )^{k}$ ,请求出多项式展开后 $x^{n} y^{m}$ 项的系数。

$0 \leq k \leq 1000, 0 \leq n, m \leq k$,且 $n + m = k, 0 \leq a, b \leq 10^{6}$

分析

就是二项式定理呀 qwq

对于不带系数的形式,我们有如下的形式:

那么对于有系数的形式呢?

这样一来,对于 $x^{n}y^{m}$ 这一项的系数我们可以将其表示为:

处理组合数的时候我们可以将其分为阶层 $fac[]$ 和逆元 $inv[]$ 来处理,其中我们可以 $\Theta(n)$ 预处理处阶层,并在 $\Theta(n + logn)$ 的时间复杂度内预处理处逆元。

代码

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
//  Created by ZJYelizaveta on Monday, September 04, 2017 AM09:19:33 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

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

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0; int 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 INF = 0x3f3f3f3f;
const int MOD = 10007;
int k, n, m;
int fac[MAX_N], inv[MAX_N];
ll ans;

inline void exgcd(int a, int b, int &x, int &y){
if(b == 0) {x = 1, y = 0;}
else{
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
}

inline int calculate(int a, int b){
int x = 0, y = 0;
exgcd(a, b, x, y);
return (x % b + b) % b;
}

inline void prepare(){
fac[0] = 1;
for(int i = 1; i <= k; ++i) fac[i] = fac[i - 1] * i % MOD;
// for(int i = 1; i <= n; ++i) printf("f[%d] = %lld\n", i, fac[i]);

inv[k] = calculate(fac[k], MOD);
for(int i = k - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
// for(int i = 1; i <= n; ++i) printf("inv[%d] = %lld\n", i, inv[i]);
}

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

inline void solve(int a, int b) {
ans = (ll)quickPow(a, n) * quickPow(b, m) % MOD;
// printf("%lld\n", ans);
ans = (ll)ans * fac[k] % MOD * inv[n] % MOD * inv[m] % MOD;
printf("%lld\n", ans);
}

int main()
{
int a = readIn(), b = readIn(); k = readIn(), n = readIn(), m = readIn();
prepare();
ans = 0;
if (n == 0) {
ans = quickPow(b, k);
printf("%lld\n", (ans % MOD + MOD) % MOD);
}
else if (m == 0) {
ans = quickPow(a, k);
printf("%lld\n", (ans % MOD + MOD) % MOD);
}
else solve(a, b);
return 0;
}

聪明的质监员

描述

小 T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 $n$ 个矿石,从 $1$ 到 $n$ 逐一编号,每个矿石都有自己的重量 $w_{i}$ 以及价值 $v_{i}$ 。检验矿产的流程是:

  1. 给定 $m$ 个区间 $[L_{i} ,R_{i}]$。
  2. 选出一个参数 $W$。
  3. 对于一个区间 $[L_{i} ,R_{i} ]$,计算矿石在这个区间上的检验值 $Y_{i}$:

这批矿产的检验结果 $Y$ 为各个区间的检验值之和。即:$Y = \sum_{i = 1}^{m}Y_{i}$
若这批矿产的检验结果与所给标准值 $S$ 相差太多,就需要再去检验另一批矿产。小 T
不想费时间去检验另一批矿产,所以他想通过调整参数 $W$ 的值,让检验结果尽可能的靠近标准值 $S$,即使得 $S-Y$ 的绝对值最小。请你帮忙求出这个最小值。

$1 \leq n, m \leq 2 \times 10^{5}, 0 < w_{i}, v_{i} \leq 10^{6}, 0 < S \leq 10^{12}, 1 \leq L_{i} \leq R_{i} \leq n$

分析

我们需要最小化 $S - Y$ 的绝对值,因为 $S$ 是定值,那么我们要最小化 $Y$ 的值。

最极端的我们可以枚举 $W$ 的所有可能值 $0 \sim max(w[i])$ ,然后 $\Theta(n^{3})$ 计算。

这应该是我们暴力的思路,但是作为正解而言时间复杂度太高了,考虑如何优化时间复杂度。

因为 $W$ 的取值是线性的,所以考虑 $\Theta(logn)$ 二分 $W$,然后 $\Theta(n^{2})$ 来计算和判断。

我们把枚举 $W$ 的时间复杂度由 $\Theta(n)$ 降到了 $\Theta(logn)$ 但是由于计算和判断的时间复杂度很大,所以我们仍然只能拿到 50 分,考虑优化计算和判断的时间复杂度。

用 $cnt[i]$ 表示前 $i$ 个矿石中满足条件的个数, $sum[i]$ 表示前 $i$ 个满足条件的矿石的价值之和。这样一来我们将计算和判断的时间复杂度优化至 $\Theta(n)$。

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

P.S. 在进行二维求和计算的时候,可以考虑用前缀和来优化,使得计算的时候时间复杂度下降一个 $n$(由 $\Theta(n^{2})$ 到 $\Theta(n)$)。

代码

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
//  Created by ZJYelizaveta on Monday, September 04, 2017 AM10:17:46 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

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

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int 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;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
int n, m; ll S;
int w[MAX_N], v[MAX_N];
int l[MAX_N], r[MAX_N];
ll cnt[MAX_N], sum[MAX_N];
ll ans;

inline bool check(int W) {
memset(cnt, 0, sizeof cnt); memset(sum, 0, sizeof sum);
ll res = 0; // 前缀和优化
for (int i = 1; i <= n; ++i) {
cnt[i] = cnt[i - 1], sum[i] = sum[i - 1];
if (w[i] >= W) {
++cnt[i]; sum[i] += v[i];
}
}

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

for (int i = 1; i <= m; ++i) {
res += (ll)(cnt[r[i]] - cnt[l[i] - 1]) * (sum[r[i]] - sum[l[i] - 1]);
}
ans = min(ans, abs(S - res));
if (res < S) return false;
return true;
}

int main()
{
n = readIn(), m = readIn(); scanf("%lld", &S);
// printf("%lld\n", S);
int MAX = -INF;
for (int i = 1; i <= n; ++i) {
w[i] = readIn(), v[i] = readIn();
MAX = max(MAX, w[i]);
}
for (int i = 1; i <= m; ++i) l[i] = readIn(), r[i] = readIn();

ans = INFLL;
int l = 0, r = MAX + 1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid;
else r = mid;
}
printf("%lld\n", ans);
// fprintf(stderr, "Time used : %.3f\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}

观光公交

描述

风景迷人的小城 Y 市,拥有 $n$ 个美丽的景点。由于慕名而来的游客越来越多,Y 市特意安排了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第 $0$ 分钟出现在 $1$ 号景点,随后依次前往 $2,3,4, \cdots , n$ 号景点。从第 $i$ 号景点开到第 $i+1$ 号景点需要 $D_{i}$ 分钟。
任意时刻,公交车只能往前开,或在景点处等待。
设共有 $m$ 个游客,每位游客需要乘车 $1$ 次从一个景点到达另一个景点,第 $i$ 位游客在
$T_{i}$ 分钟来到景点 $A_{i}$ ,希望乘车前往景点 $B_{i} (A_{i} <B_{i} )$。为了使所有乘客都能顺利到达目的地,公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。
假设乘客上下车不需要时间。
一个乘客的旅行时间,等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一
辆观光车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 $k$ 个氮气加速器,每使用一个加速器,可以使其中一个 $D_{i}$ 减 $1$。对于同一个 $D_{i}$ 可以重复使用加速器,但是必须保证使用后 $D_{i}$ 大于等于 $0$。
那么 ZZ 该如何安排使用加速器,才能使所有乘客的旅行时间总和最小?

$1 \leq n \leq 1000, 1 \leq m \leq 10000, 0 \leq k \leq 100000, 0 \leq D_{i} \leq 100, 0 \leq T_{i} \leq 100000$

分析

模拟的时候没有什么思路,好像有点费用流的感觉(一定是我的错觉),但是还是只写了特判的 30 分,Sign

原来是 贪心 + 模拟 qwq

首先,我们可以先预处理出结点 $i$ 最晚出发的人的出发时间 $last[i]$ ,以及结点 $i$ 在不使用氮气加速的时候公交到达的时间 $arv[i]$ ,还有在第 $i$ 站下车的人数(对答案有贡献)。

这样我们可以计算出,在不使用氮气加速的时候,所有旅客的旅行时间之和:

因为 $t[i]$ 是不会改变的,如果我们想令 $ans$ 最小,那么我们需要最小化 $arv[b[i]]$ 。

如何可以最大化的最小化 $arv[b[i]]$ 呢?我们要使被影响的结点尽可能多,那么我们每一次 $\Theta(n)$ 线性扫一次。

考虑对于结点 $i$ ,如果有 $arv[i + 1] > last[i + 1]$ ,那么在这个时候我们在 $i$ 处使用氮气不仅对 $i + 1$ 这个结点有贡献还有可能对之后的结点也有贡献。

若 $arv[i + 1] \leq last[i + 1]$ ,那么如果在 $i$ 处使用氮气,那么只会对 $i + 1$ 处产生贡献,因为在景点停靠等待使得后面的景点的到达时间依然没有改变。

因此,我们在 $i$ 处使用加速器对别的景点的贡献是可以递推出来的。

求出了在 $i$ 处使用加速器可以影响的最远的点,那么影响的总时间就等于在每个被影响的点下车的人数之和乘以使用加速器的数量,然后记得更新。

最后的答案为

代码

特判

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
//  Created by ZJYelizaveta on Monday, September 04, 2017 AM11:10:09 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

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

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int 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 = 10000 + 3;
const int MAX_K = 100000 + 3;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
int n, m, k;
int d[MAX_N];
int t[MAX_M], a[MAX_M], b[MAX_M];
int arv[MAX_N], st[MAX_N];
int ans;

inline void solve1() {
ans = 0;
memset(arv, 0, sizeof arv); memset(st, 0, sizeof st);
for (int i = 1; i <= m; ++i) st[a[i]] = max(st[a[i]], t[i]);
arv[1] = st[1];
for (int i = 2; i <= n; ++i) {
arv[i] = max(arv[i - 1], st[i - 1]) + d[i - 1];
}
// for (int i = 1; i <= n; ++i) printf("%d ", st[i]); printf("\n");
// for (int i = 1; i <= n; ++i) printf("%d ", arv[i]); printf("\n");
for (int i = 1; i <= m; ++i) ans += arv[b[i]] - t[i];
printf("%d\n", ans);
}

inline void calculate(int x) {
int res = 0;
for (int i = 2; i <= x; ++i) {
arv[i] = max(arv[i - 1], st[i - 1]) + d[i - 1];
}
arv[x + 1] = max(arv[x], st[x]) + d[x] - 1;
for(int i = x + 2; i <= n; ++i) {
arv[i] = max(arv[i - 1], st[i - 1]) + d[i - 1];
}
for (int i = 1; i <= m; ++i) res += arv[b[i]] - t[i];
// printf("%d\n", res);
ans = min(ans, res);
}

inline void solve2() {
memset(arv, 0, sizeof arv); memset(st, 0, sizeof st);
arv[1] = 0;
for (int i = 1; i <= m; ++i) st[a[i]] = max(st[a[i]], t[i]);
arv[1] = st[1]; ans = INF;
for (int i = 1; i <= n - 1; ++i) calculate(i);
printf("%d\n", ans);
}

int main()
{
n = readIn(), m = readIn(), k = readIn();
for (int i = 1; i <= n - 1; ++i) d[i] = readIn();
for (int i = 1; i <= m; ++i) t[i] = readIn(), a[i] = readIn(), b[i] = readIn();
if (k == 0) solve1();
else if (k == 1) solve2();
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
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
#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 = 10000 + 3;
const int MAX_K = 100000 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
ll n, m, k;
ll d[MAX_N];
ll t[MAX_M], a[MAX_M], b[MAX_M];
ll last[MAX_N], arv[MAX_N], sum[MAX_N];
ll cntPerson, numK, from, to;
ll ans;

inline void prepare() {
for (int i = 2; i <= n; i++)
arv[i] = max(arv[i - 1], last[i - 1]) + d[i - 1];
for (int i = 2; i <= n; i++) sum[i] += sum[i - 1];
for (int i = 1; i <= m; i++) ans += arv[b[i]] - t[i];

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

inline bool find() {
ll curK = INF, pos = n;
cntPerson = 0, numK = INF;
for (int i = n - 1; i >= 1; --i) {
if (arv[i + 1] > last[i + 1]) curK = min(curK, arv[i + 1] - last[i + 1]);
else {
curK = arv[i + 1]; // the max number we can decrease
pos = i + 1;
}

if (d[i] && sum[pos] - sum[i] > cntPerson) {
cntPerson = sum[pos] - sum[i];
from = i; to = pos;
numK = min(k, min(curK, d[i]));
}
}
return numK;
}

inline void calculate() {
for (int i = from + 1; i <= to; ++i) arv[i] -= numK;
k -= numK;
d[from] -= numK;
ans -= cntPerson * numK;
}

inline void solve() {
while (find()) calculate();
printf("%lld\n", ans);
}

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

n = readIn<ll>(), m = readIn<ll>(), k = readIn<ll>();
for (int i = 1; i <= n - 1; ++i) d[i] = readIn<ll>();
for (int i = 1; i <= m; ++i) {
t[i] = readIn<ll>(), a[i] = readIn<ll>(), b[i] = readIn<ll>();
++sum[b[i]];
last[a[i]] = max(last[a[i]], t[i]);
}

prepare();
solve();

return 0;
}
Partager