NOIP 2012 整理

Day 1

Vigenère 密码

描述

16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法 —— Vigenère 密
码。Vigenère 密码的加密解密算法简单易用,且破译难度比较高,曾在美国南北战争中为南军所广泛使用。
在密码学中,我们称需要加密的信息为明文,用 $M$ 表示;称加密后的信息为密文,用
$C$ 表示;而密钥是一种参数,是将明文转换为密文或将密文转换为明文的算法中输入的数据,记为 $k$。 在 Vigenère

密码中,密钥 $k$ 是一个字母串,$k=k_{1} k_{2} \cdots k_{n}$ 。当明文 $M=m_{1}m_{2} \cdots m_{n}$ 时,得到的密文 $C=c_{1} c_{2} \cdots c_{n}$ ,其中 $c_{i} =m_{i} ®k_{i}$ 运算 ® 的规则如,下表所示:

Vigenère 加密在操作时需要注意:

  1. ® 运算忽略参与运算的字母的大小写,并保持字母在明文 $M$ 中的大小写形式。
  2. 当明文 $M$ 的长度大于密钥 $k$ 的长度时,将密钥 $k$ 重复使用。

输入的密匙长度不超过 $100$,输入的密文的长度不超过 $1000$,且都仅包含英文字母。

分析

当我看到这个图的时候,我的内心是拒绝的,然后我很认真的找了一下规律。

我们令横坐标表示明文,纵坐标为密钥。

那么

然后根据 ACSII 表的特点,在 $\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
//  Created by ZJYelizaveta on Friday, October 20, 2017 PM03:31: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 = 100 + 3; // key
const int MAX_M = 1000 + 3; // secret string
char str1[MAX_N], str2[MAX_M];
int len1, len2;

int main()
{

scanf("%s", str1); scanf("%s", str2);
len1 = strlen(str1), len2 = strlen(str2);

for (int i = 0; i < len1; ++i) str1[i] = toupper(str1[i]);

for (int i = 0; i < len2; ++i) {
int num = (toupper(str2[i]) - str1[i % len1] + 26) % 26;

if (isupper(str2[i])) putchar('A' + num);
else putchar('a' + num);
}

return 0;
}

国王游戏

描述

恰逢 H 国国庆,国王邀请 $n​$ 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 $n​$ 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

$1 \leq n \leq 1000, 1 \leq a, b \leq 10000$

分析

想不到正解,然后贪心拿了 60 分。

有两个人 $i, j$ , $i$ 在 $j$ 前面更优一些,当且仅当 $sum \times \frac{q[i].a}{q[j].b} < sum \times \frac{q[j].a}{q[i].b}$ ,即 $ \frac{q[i].a}{q[j].b} < \frac{q[j].a}{q[i].b}$,以这样的方式排序,我们可以拿到 60 分。

那么剩下的 40 分为什么拿不到呢qwq,因为 $a, b \leq 10^{4}$,而最极端的情况下会有 $1000$ 个 $10^{4}$ 相乘,这种情况下肯定是要用高精度来解决的。

那么代码剩下的部分就是在于手写高精度啦,就当 NOIP 之前复习一下高精度啦,写的差点吐了。

代码

$60 \%$ 骗分大法好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
//  Created by ZJYelizaveta on Friday, October 20, 2017 PM03:52: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 = 1000 + 3;
const int INF = 0x3f3f3f3f;
int n;
struct Person {
int a, b;
bool operator < (const Person &rhs) const {
return a / rhs.b < rhs.a / b;
}
}q[MAX_N];
int ans[MAX_N], res;

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

for (int i = 1; i <= n; ++i) {
ans[i] = 1;
for (int j = 0; j < i; ++j) ans[i] *= q[j].a;
ans[i] /= q[i].b;
}

res = -INF;
for (int i = 1; i <= n; ++i) res = max(res, ans[i]);

printf("%d\n", res);
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
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
//  Created by ZJYelizaveta on Thursday, October 26, 2017 AM08:45: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 = 1000 + 3;
const int INF = 0x3f3f3f3f;
int n;
struct Person {
int a, b;
bool operator < (const Person &rhs) const {
return a * b < rhs.a * rhs.b;
}
}q[MAX_N];

struct BigInt {
vector<int> v;
static const int BASE = 10;

BigInt(ll x) {
do {
v.push_back(x % 10);
} while (x /= 10);
}

BigInt(const string &str) {
v.reserve(str.length());

for (int i = str.length() - 1; i >= 0; --i) {
v.push_back(str[i] - '0');
}
}

BigInt() {}

void removePreZero() {
while (v.size() >= 1 && v.back() == 0) v.pop_back();
}

bool operator<(const BigInt &a) const {
if (v.size() != a.v.size()) {
return v.size() < a.v.size();
}

for (int i = v.size() - 1; i >= 0; --i) {
if (v[i] != a.v[i]) {
return v[i] < a.v[i];
}
}
return false; // equal
}

bool operator>(const BigInt &a) const { return a < *this; }
bool operator<=(const BigInt &a) const { return !(a < *this); }
bool operator>=(const BigInt &a) const { return !(a > *this); }
bool operator!=(const BigInt &a) const { return a < *this || a > *this; }
bool operator==(const BigInt &a) const { return !(a < *this) && !(a > *this); }

BigInt operator+(const BigInt &a) const {
BigInt res;
int sum = 0;

for (int i = 0; i < max(v.size(), a.v.size()); ++i) {
if (i < a.v.size()) sum += a.v[i];
if (i < v.size()) sum += v[i];

res.v.push_back(sum % BASE);
sum /= BASE;
}

if (sum) res.v.push_back(sum);
res.removePreZero();

return res;
}

BigInt operator-(const BigInt &a) const {
BigInt res;
int dif = 0;

for (int i = 0; i < max(v.size(), a.v.size()); ++i) {
if (i < v.size()) dif += v[i];
if (i < a.v.size()) dif -= a.v[i];

if (dif >= 0) {
res.v.push_back(dif);
dif = 0;
}
else {
res.v.push_back((dif + BASE) % BASE);
dif = -1;
}
}

res.removePreZero();
return res;
}

BigInt operator*(const BigInt &a) const {
BigInt res;

res.v.resize(v.size() + a.v.size(), 0); //
for (int i = 0; i < v.size(); ++i) {
for (int j = 0; j < a.v.size(); ++j) {
res.v[i + j] += v[i] * a.v[j];
res.v[i + j + 1] += res.v[i + j] / BASE;
res.v[i + j] %= BASE;
}
}

res.removePreZero();
return res;
}

BigInt operator/(const BigInt &a) const {
BigInt res, ret(0);

res.v.resize(v.size(), 0);
ret = 0;

for (int i = v.size() - 1; i >= 0; --i) {
ret = ret * 10 + v[i];

while (ret >= a) {
ret = ret - a;
res.v[i]++;
}
}

res.removePreZero();
return res;
}
};

istream& operator>>(istream &in, BigInt &x) {
string str;
in >> str;

x = BigInt(str);

return in;
}

ostream& operator<<(ostream &out, const BigInt &x) {
for (int i = x.v.size() - 1; i >= 0; --i) {
cout << x.v[i];
}

return out;
}

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

BigInt ans = 0, sum = 1;
for (int i = 0; i < n; ++i) sum = sum * q[i].a;

ans = sum / q[n].b;
ans = ans <= 1 ? 1 : ans;

cout << ans << endl;
return 0;
}

开车旅行

描述

小 A 和小 B 决定利用假期外出旅行,他们将想去的城市从 $1$ 到 $N$ 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 $i$ 的海拔高度为 $H_{i}$ ,城市 $i$ 和城市 $j$ 之间的距离 $d[i,j]$ 恰好是这两个城市海拔高度之差的绝对值,即 $d[i, j] = \left |H_{i} − H_{j} \right |$。
旅行过程中,小 A 和小 B 轮流开车,第一天小 A 开车,之后每天轮换一次。他们计划选择一个城市 $S$ 作为起点,一直向东行驶,并且最多行驶 $X$ 公里就结束旅行。小 A 和小 B 的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 $X$ 公里,他们就会结束旅行。
在启程之前,小 A 想知道两个问题:

  • 对于一个给定的 $X=X_{0}$ ,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B 的行驶路程为 $0$ ,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。
  • 对任意给定的 $X=X_{i}$ 和出发城市 $S_{i}$ ,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

$1≤N≤100000,1≤M≤10000,-1000000000≤H_{i} ≤1000000000,0≤X_{0}≤1000000000,1≤S_{i} ≤N,0≤X_{i} ≤1000000000$ ,数据保证 $H_{i}$ 互不相同

分析

题目描述很恶心,但是出题人的部分分还是给的比较良心的,首先 $\Theta(n^{2})$ 预处理从每个点出发的最小值和次小值和到达的点,然后第一问枚举每一个点模拟,第二问一样模拟,这样可以拿到 70 分。时间复杂度约为 $\Theta(n^{2} + n^{2} + nm)$ 。

考虑正解。

$\Theta(n^{2})$ 预处理的代价太大了,考虑降低时间复杂度。因为这里我们只需要求出每一个点与后面的点中的距离最小值与次小值,所以要考虑用链表 $\Theta(n)$ 维护每一个点的前驱和后继,然后求出最小值和次小值。当然也可以考虑用平衡树 $\Theta(nlogn)$ 维护前驱和后继,这里可以不用写 Splay 直接用 STL 中的 set 来维护。

同样第一问我们暴力模拟的时间复杂度接近 $\Theta(n^{2})$ 暴力模拟第二问的时间复杂度也接近 $\Theta(nm)$ ,所以考虑优化。

这里应该是一个套路,我们可以像求 LCA 一样,我们用倍增来求,每一轮让 A, B 各跳一次。

$fa[i][j]$ 为从 $i$ 出发跳 $2^{j}$ 轮之后到达的位置。(一轮为 A, B 各跳一次)。

$disA[i][j]$ 为从 $i$ 出发跳 $2^{j}$ 次后走的距离。$disB[i][j]$ 为从 $i$ 出发条 $2^{j}$ 次后走的距离。

用双向链表预处理是我没有想到的,虽然最后还是用 set 水过去的,但是不可否认这道题目的思维含量还是不错的,需要注意许多小细节,免得不小心翻车 qwq

总时间复杂度 $\Theta(2nlogn + mlogn)$ 。真 $\cdot$ 调了一上午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
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
//  Created by ZJYelizaveta on Monday, October 30, 2017 AM09:06:03 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 = 10000 + 3;
const int INF = INT_MAX;
const double inf = 0x7fffffff;
int n, m;
int h[MAX_N];
int X0;
int s[MAX_M], x[MAX_M];
struct Node {
int to, dist;
}a[MAX_N], b[MAX_N];

inline void prepare() {
for (int i = 1; i <= n; ++i) a[i].dist = b[i].dist = INF;
for (int i = 1; i <= n; ++i) a[i].to = b[i].to = 0;

for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
int temp = abs(h[i] - h[j]);
if (!b[i].to || temp < b[i].dist || (temp == b[i].dist && h[j] < h[b[i].to])) {
a[i] = b[i];
b[i].to = j; b[i].dist = temp;
}
else if (!a[i].to || temp < a[i].dist || (temp == a[i].dist && h[j] < h[a[i].to])) {
a[i].to = j; a[i].dist = temp;
}
}
}
/*
for (int i = 1; i <= n; ++i) {
printf("%d %d\n", a[i].to, a[i].dist);
printf("%d %d\n", b[i].to, b[i].dist);
printf("\n");
}
*/
}

inline void solve1() {
int X = X0, res = 1;
double ans = inf, temp;
for (int i = 1; i <= n; ++i) {
int dist = 0, op = 0, pos = i, sumA = 0, sumB = 0;
while (1) {
if (op == 0) { // A drive the car
if (dist + a[pos].dist > X || a[pos].to == 0) break;
dist += a[pos].dist;
sumA += a[pos].dist;
pos = a[pos].to;

}
else {
if (dist + b[pos].dist > X || b[pos].to == 0) break;
dist += b[pos].dist;
sumB += b[pos].dist;
pos = b[pos].to;
}
op ^= 1;
}
if (sumB == 0) temp = inf;
else temp = (double)sumA / (double)sumB;
if (temp < ans || (temp == ans && h[i] > h[res])) {
ans = temp;
res = i;
}
}
// printf("%.3f\n", ans);
printf("%d\n", res);
}

inline void solve2(int pos, int X) {
int dist = 0, op = 0, sumA = 0, sumB = 0;
while (1) {
if (op == 0) { // A drive the car
if (dist + a[pos].dist > X || a[pos].to == 0) break;
dist += a[pos].dist;
sumA += a[pos].dist;
pos = a[pos].to;

}
else {
if (dist + b[pos].dist > X || b[pos].to == 0) break;
dist += b[pos].dist;
sumB += b[pos].dist;
pos = b[pos].to;
}
op ^= 1;
}
printf("%d %d\n", sumA, sumB);
}


int main()
{
n = readIn<int>();
for (int i = 1; i <= n; ++i) h[i] = readIn<int>();
// for (int i = 1; i <= n; ++i) printf("%d ", h[i]); printf("\n");

X0 = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= m; ++i) s[i] = readIn<int>(), x[i] = readIn<int>();

prepare();
solve1();
for (int i = 1; i <= m; ++i) {
solve2(s[i], x[i]);
}

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
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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), fa(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') fa = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * fa;
}
const int MAX_N = 1000000 + 3;
const int MAX_LOG_N = 17 + 3;
const int INF = INT_MAX;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
const double inf = 0x7fffffff;
int n, m;
int X0;
int S[MAX_N], X[MAX_N];
struct City {
int high, pos;
bool operator < (const City &rhs) const {
return high < rhs.high;
}
}a[MAX_N];
set <City> s;
struct temp {
int pos, diff;
bool operator < (const temp &rhs) const {
if (diff != rhs.diff) return diff < rhs.diff;
return a[pos].high < a[rhs.pos].high;
}
}q[5];
int nextA[MAX_N], nextB[MAX_N], fa[MAX_N][MAX_LOG_N];
long long disA[MAX_N][MAX_LOG_N], disB[MAX_N][MAX_LOG_N];

inline void find(int i) {
set<City>::iterator it = s.find(a[i]);

int add = 0;
if (it != s.begin()) {
--it;
q[++add] = (temp){it -> pos, abs(it -> high - a[i].high)};
if (it != s.begin()) {
--it;
q[++add] = (temp){it -> pos, abs(it -> high - a[i].high)};
++it;
}
++it;
}

if ((++it) != s.end()) {
q[++add] = (temp){it -> pos, abs(it -> high - a[i].high)};
if ((++it) != s.end()) {
q[++add] = (temp){it -> pos, abs(it -> high - a[i].high)};
}
}
sort(q + 1, q + add + 1);
/*
printf("\n");
for (int j = 1; j <= add; ++j) printf("%d %d\n", q[j].pos, q[j].diff);
*/
nextB[i] = q[1].pos;
if (add == 1) return;
nextA[i] = q[2].pos;
}

inline void prepare() {
for (int i = n; i >= 1; --i) {
s.insert(a[i]);
if (i ^ n) find(i); // i ^ n means when i = 1 ~ n - 1 we can find the minDis and second minDis;
}
/*
printf("\n");
for (int i = 1; i <= n; ++i) printf("%d %d\n", nextA[i], nextB[i]);
printf("\n");
*/
for (int i = 1; i <= n; ++ i) {
int pos1 = nextA[i], pos2 = nextB[nextA[i]];
fa[i][0] = pos2; //
disA[i][0] = pos1 ? abs(a[pos1].high - a[i].high) : 0;
disB[i][0] = pos2 ? abs(a[pos2].high - a[pos1].high) : 0;
}

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]; //
disA[i][j] = disA[i][j - 1] + disA[fa[i][j - 1]][j - 1];
disB[i][j] = disB[i][j - 1] + disB[fa[i][j - 1]][j - 1]; // printf("%d %lld %lld\n", fa[i][j], disA[i][j], disB[i][j]);
}
// printf("\n");
}
}

inline void query(int x, int lim, long long &sumA, long long &sumB) {
for (int i = 19; ~i; -- i) if (fa[x][i] && disA[x][i] + disB[x][i] <= lim) {
sumA += disA[x][i]; sumB += disB[x][i];
lim -= disA[x][i] + disB[x][i]; x = fa[x][i];
}
int posA = nextA[x]; if (!posA) return;
int dis = abs(a[posA].high - a[x].high); if (dis <= lim) sumA += dis; //
}

inline void solve1() {
int pos = 0;
long long ansA = 1e15, ansB = 0ll;
for (int i = 1; i <= n; ++ i) {
long long sumA = 0ll, sumB = 0ll; query(i, X0, sumA, sumB);
if (sumB && (!pos || ansA * sumB > ansB * sumA)) {
ansA = sumA; ansB = sumB;
pos = i;
}
}
printf("%d\n", pos);
}

int main()
{
n = readIn<int>();
for (int i = 1; i <= n; ++ i) {
a[i].high = readIn<int>(), a[i].pos = i;
}
X0 = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= m; ++i) S[i] = readIn<int>(), X[i] = readIn<int>();

prepare();
solve1();

for (int i = 1; i <= m; ++i) {
ll sumA = 0ll, sumB = 0ll;
query(S[i], X[i], sumA, sumB);
printf("%lld %lld\n", sumA, sumB);
}

return 0;
}

Day 2

同余方程

描述

关于 $x$ 的同余方程 $ax \equiv 1 \pmod b$ 的最小正整数解。

$2 \leq a, b, \leq 2 \times 10^{9}$

分析

求 $ax \equiv 1 \pmod b$ 的最小正整数解,不妨将式子变一下形:

那么我们需要求得就是满足 $ax - by = 1$ 最小的 $x$ 的值。

这里我们用到扩展欧几里德来求解,稍微回忆一下 exgcd 吧!

求满足 $ax + by = gcd(a, b)$ 的一组解 $x, y$ 。

因为在欧几里得定理中 $b \neq 0 \Rightarrow gcd(a, b) = gcd(b, a \pmod b)$

又因为 $bx’ + (a \pmod b)y’ = gcd(b, a \pmod b)$

所以 $ax + by = bx’ + (a \pmod b)y’ = bx’ + (a - b \left \lfloor \frac{a}{b} \right \rfloor )y’$

将式子变形:

$ax + by = ay’ + b(x’ - \left \lfloor \frac{a}{b} \right \rfloor y’)$

很明显有一组通解: $x = y’, y = x’ - \left \lfloor \frac{a}{b} \right \rfloor y’ $

然后我们可以递归求得 $x, y$ ,注意:当 $b = 0$ 时, $x = 1, y = 0$ 。

其实当 $gcd \nmid 1$ ,方程此时无解,但是这里保证方程有解就不用判断这种情况了。

我们用 exgcd 求出的解并不一定是最小解,所以输出的时候要对 $b$ 取模。如果出现负数解,先加一个 $b$,再对 $b$ 取模即可。

代码

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
//  Created by ZJYelizaveta on Wednesday, October 25, 2017 PM12: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;
}
ll a, b;

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

int main()
{
a = readIn<ll>(), b = readIn<ll>();

ll x = 0, y = 0;
exgcd(a, b, x, y);

printf("%lld\n", (x + b) % b);
return 0;
}

借教室

描述

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。
面对海量租借教室的信息,我们自然希望编程解决这个问题。
我们需要处理接下来 $n$ 天的借教室信息,其中第 $i$ 天学校有 $r_{i}$ 个教室可供租借。共有 $m$ 份订单,每份订单用三个正整数描述,分别为 $d_{j} , s_{j} , t_{j}$ ,表示某租借者需要从第 $s_{j}$ 天到第 $t_{j}$ 天租借教室(包括第 $s_{j}$ 天和第 $t_{j}$ 天),每天需要租借 $d_{j}$ 个教室。
我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供$d_{j}$ 个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。
借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第 $s_{j}$ 天到第 $t_{j}$ 天中有至少一天剩余的教室数量不足 $d_{j}$ 个
现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。

$1 \leq n, m \leq 10^{6} , 0 \leq r_{i} , d_{j} \leq 10^{9} , 1 \leq s_{j} \leq t_{j} \leq n$

分析

暴力模拟 40 分。

很明显的区间修改和区间查询,开始准备 树状数组 + 差分 来解决,结果发现最差的时间复杂度为 $\Theta(mnlogn)$ ,不会进一步优化,遂放弃以这种思路刚正解。

换一个思路吧!“借教室的原则是先到先得” 也就是说, $m$ 个人借教室这个序列是有序的,有序的我们就可以二分来解决。

二分,我们 check 的时间复杂度为 $\Theta(nm)$ ,需要优化。想到前面 NOIP 2011 聪明的质监员,我们可以用前缀和来优化,从而优化掉一个 $n$ ,由 $\Theta(nm) \rightarrow \Theta(m)$ 。

这里我们不只是简单的前缀和优化,因为我们需要支持区间修改和区间 check ,因此我们需要把前缀和差分一下,使得做完前缀和之后每一位表示的是这一天需要借出的教室总数。

具体操作如图所示:

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

代码

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
//  Created by ZJYelizaveta on Thursday, October 26, 2017 AM11:17:07 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;
int n, m;
int r[MAX_N];
struct Note {
int d, s, t;
}a[MAX_N];
int sum[MAX_N];

inline bool check(int x) {
memset(sum, 0, sizeof sum);
for (int i = 1; i <= x; ++i) {
sum[a[i].s] += a[i].d; sum[a[i].t + 1] -= a[i].d;
}

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

for (int i = 1; i <= n; ++i) if (sum[i] > r[i]) return true;
return false;
}

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

if (r == m) printf("0\n");
else printf("-1\n%d\n", ans);
}

int main()
{
n = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= n; ++i) r[i] = readIn<int>();
for (int i = 1; i <= m; ++i) a[i].d = readIn<int>(), a[i].s = readIn<int>(), a[i].t = readIn<int>();

solve();

return 0;
}

疫情控制

描述

H 国有 $n$ 个城市,这 $n$ 个城市用 $n-1$ 条双向道路相互连通构成一棵树,$1$ 号城市是首都,也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。
现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。
请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。

$2 \leq m \leq n \leq 50,000,0<w <10^{9}$

分析

首先我们有一个贪心的结论:选择的检查点肯定越靠近根越优,因为这样可以尽可能多的覆盖到一些节点。

这样一来我们就要贪心让军队尽可能往根节点走。

又因为 “不同的军队可以同时移动” ,也就是说我们所求的是所有的军队到达相应地点中耗时最长的军队花费的时间,而我们要最小化这个时间。也就是我们要最小化时间的最大值,这是一个二分的套路,所以我们可以每次二分一个人时间 $mid$ 然后 check 一下。

现在问题在于如何以比较优的时间复杂度实现 check 这个函数。

我们让军队往根节点跳,根据套路,可以用倍增来优化。

军队往上跳最后有两种情况:

  • 军队到达不了根节点,那么就在这支军队能到达的最靠近的根节点位置的节点上打一个标记。
  • 如果这只军队能够到达根节点,那么记录一下它的编号以及它到达根节点后还可以走的时间 $last_{i}$ 以及这只军队的起始节点所属根节点的哪棵子树 $a_{i}$ 。

军队跳完以后,查找所有根节点到其的路径中没有设置检查点的子树(如果一个结点 $u$ 设置了观察节点就意味着节点 $u$ 及其在所有的子树都设立了观察结点)。这个部分我们可以用树形动规求出来。

现在找出了所有没有设立观察节点的子树,但是现在就 check 完了吗,没有呀!我们还有到达根节点后仍然可以移动的军队,现在是这些军队做贡献的时候了。

将记录了的可以到达根节点的军队按照 $last_{i}$ 从大到小排序,将刚刚找出未设立观察点的子树按照子树到根节点的距离从大到小排序。一次处理每一棵子树需要那一支军队来管辖。

这里我们仍然需要运用贪心的思想:这里离根节点距离最远的子树用 $last_{i}$ 最大的来管辖这是一个比较直接的想法。但是若这棵子树 $u$ 原本有一支可以到达根节点但是不够走回军队起始点的军队(即存在根节点的子树 $x$ 中且 $last_{i}$ 最小的结点),那么我们不妨就将这支军队放在结点 $u$ ,这样一来就不用浪费更大的 $last_{i}$ 了。若不存在这样的军队,那么还是用一开始最直接的贪心想法来判断。

NOIP 2012 Day2 居然考了两次二分;两天考了两次倍增预处理???

这样一来我们的总时间复杂度为 $\Theta(logn(mlogn))$ 。

代码

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
//  Created by ZJYelizaveta on Tuesday, October 31, 2017 AM08:59: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 = 50000 + 3;
const int INF = INT_MAX;
const int MAX_LOG_N = 15 + 3;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
int n, m;
struct Edge {
int to, next; ll w;
}edge[MAX_N << 1];
int head[MAX_N], cnt = 0;
int army[MAX_N];

inline void addEdge(int from, int to, ll 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;
}

int fa[MAX_N][MAX_LOG_N];
ll dis[MAX_N][MAX_LOG_N];
inline void dfs(int u, int f, ll w) {
fa[u][0] = f; dis[u][0] = w;
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v == f) continue;
dfs(v, u, edge[i].w);
}
}

inline void prepare() {
dfs(1, 0, 0);

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];
}
}
/*
for (int j = 0; j < MAX_LOG_N; ++j) {
for (int i = 1; i <= n; ++i) {
printf("%d %d %d %lld\n", i, j, fa[i][j], dis[i][j]);
}
printf("\n");
}
*/
}

int vis[MAX_N], used[MAX_N], pos[MAX_N];
ll restMin[MAX_N];
struct Military {
int id; ll rest;
bool operator < (const Military &rhs) const {
return rest > rhs.rest;
}
}a[MAX_N], b[MAX_N]; // a -> the military that can reach the root, the tree that cannot be covered
int numA, numB;

inline int find(int u , int f) { // check the tree can be covered or not
bool flag1 = true, flag2 = false;
if (vis[u]) return 1;
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v == f) continue;
flag2 = true;

if (!find(edge[i].to, u)) {
flag1 = false;
if (u == 1) b[++numB].id = edge[i].to, b[numB].rest = edge[i].w;
else return 0;
}
}

if (!flag2) return 0;
return flag1;
}

inline bool check(ll lim) {
numA = 0, numB = 0;
memset(vis, 0, sizeof vis);
memset(pos, 0, sizeof pos);
memset(used, 0, sizeof used);

for (int i = 1; i <= m; ++i) {
// printf("%lld\n", lim);
int x = army[i]; ll depth = 0;
for (int j = MAX_LOG_N - 1; j >= 0; --j) {
if (fa[x][j] > 1 && depth + dis[x][j] <= lim) {
depth += dis[x][j]; x = fa[x][j];
}
}

// printf("%d %lld %lld\n", fa[x][0], lim - depth - dis[x][0], lim);

if (fa[x][0] == 1 && depth + dis[x][0] <= lim) { // can reach the root
a[++numA].id = i; a[numA].rest = lim - depth - dis[x][0];
// printf("%d %lld\n", a[numA].id, a[numA].rest);
if (!pos[x] || a[numA].rest < restMin[x]) {
pos[x] = i; restMin[x] = a[numA].rest;
}
}

else vis[x] = true; // cannot reach the root
}

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

if (find(1, 0)) return true; // already cover the tree, make r = mid, trie to narrow the range

sort(a + 1, a + numA + 1);
sort(b + 1, b + numB + 1);
/*
for (int i = 1; i <= numA; ++i) printf("%d %lld\n", a[i].id, a[i].rest);
for (int i = 1; i <= numB; ++i) printf("%d %lld\n", b[i].id, b[i].rest);
*/
// printf("%d %d\n", numA, numB);

used[0] = 1;
int cur = 1;
for (int i = 1; i <= numB; ++i) {
if (!used[pos[b[i].id]]) {
used[pos[b[i].id]] = 1; continue;
}

while (cur <= numA && (used[a[cur].id] || a[cur].rest < b[i].rest)) ++cur;
if (cur > numA) return false; // nothing can cover this tree

used[a[cur].id] = 1;
}

return true;
}

inline void solve() {
ll l = 0, r = INF, ans = -1;
/*
if (check(2)) printf("qwq\n");
else printf("Naive\n");
*/

while (l <= r) {
ll mid = (l + r) >> 1;
// printf("%lld\n", mid);
if (check(mid)) r = mid - 1, ans = mid; // return true;
else l = mid + 1;
}
printf("%lld\n", ans);
}

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

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

prepare();
solve();

return 0;
}
Compartir