Theme NexT works best with JavaScript enabled

2019 牛客暑期多校训练营第三场题解

本文包括 2019 牛客暑期多校训练营第三场的题面与题解。

A - Graph Games

题目描述

You are given an undirected graph with $ N $ vertices and $ M $ edges. The edges are numbered from $ 1 $ to $ M $ . Denote the set $ S(x) $ as: All the vertices we can reach from vertex $ x $ by exactly one edge.

You are supposed to deal with $ Q $ operations of the following two types:

  • $ (1,l,r) $ — reverse the status of edges numbered between $ l $ to $ r $ $ (1 \leq l \leq r \leq M) $ . i.e. Delete the edge if it is in the graph, otherwise add it to the graph.
  • $ (2,u,v) $ — ask whether $ S(u) $ and $ S(v) $ are exactly the same $ (1 \leq u \leq v \leq N) $ .

Note that all the $ M $ edges are in the graph at the beginning.

输入描述

The input contains multiple cases. The first line of the input contains a single positive integer $ T $ , the number of cases.

For each case, the first line contains two integers $ N\ (1 \leq N \leq 100000) $ and $ M\ (1 \leq M \leq 200000) $ , the number of vertices and edges in the graph. In the following $ M $ lines, the $ i $ -th line contains two integers $ u_i,v_i \ (1 \le u_i,v_i \le N) $ , describing the the $ i $ -th edge $ (u_i,v_i) $ . Each edge appears in the input at most once. The $ (M+2) $ -th line contains a integer $ Q\ (1 \leq Q \leq 200000) $ , the number of operations. In the following $ Q $ lines, each line contains three integers, describing an operation.

The total sum of $ N $ over all cases does not exceed $ 150000 $ .

The total sum of $ M $ over all cases does not exceed $ 800000 $ .

The total sum of $ Q $ over all cases does not exceed $ 600000 $ .

输出描述

For each case, print a string in a line. The length of the string should equal the number of operations of type $ 2 $ . If the answer is yes, the $ i $ -th character of the string should be 1, otherwise it should be 0. Check the samples for more details.

示例1

输入

1
2
3
4
5
6
7
8
9
10
1
5 4
1 2
1 3
4 2
4 3
3
2 1 4
1 1 1
2 1 2

输出

1
10

题解

题意

给定一张图,有两种操作:

  • 1 l r 将读入的边的序列的区间 $ [l,r] $ 内的边反转状态(有/无),初始为全有
  • 2 x y 询问 $ x $ 和 $ y $ 两个点所直连的点构成的两个点集是否相同

解法

判断点集是否相同,可以对这n个点随机赋值,取一个集合的值为该集合内所以元素的值的异或和。

那么判断的时间复杂度降到 $ \mathcal{O}(1) $ 。

对于反转状态,可以采用分块的做法,对于点集大小小于 $ \sqrt{m} $ 的我们称作轻点,否则称为重点。

  • 对于轻点,边数不超过 $ \sqrt{m} $ ,直接暴力判断是否翻转。
  • 对于重点,只有 $ \sqrt{m} $ 种。对边序列分块,维护每一个块如果整体翻转对某个重点集的贡献。在进行区间操作的时候,在块间打翻转标记,在两侧暴力翻转。如果翻转的边的端点是重点,就直接计算一次贡献。询问时查询所有块的整体翻转情况,如果整体是翻转的,则再计算一次贡献。这样每次询问复杂度 $ \mathcal{O}(\sqrt{m}) $ 。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define Pii pair<int, int>
#define MPii make_pair
#define uint unsigned int
const int maxn = 200010;
ll val[maxn], now[maxn];
ll f[510][1010];
bool flip[510], v[maxn];
bool is_big[maxn];
vector<Pii> G[maxn];
int pos[maxn], L[maxn], R[maxn], mp[maxn], tot;
random_device rd;
mt19937 Random(rd());
struct edge {
int u, v;
} e[maxn];
ll Getrand(ll mod) { return ((__int128)Random() * Random()) % mod; }
void change(int l, int r) {
int p = pos[l], q = pos[r];
if (p == q) {
for (int i = l; i <= r; i++) {
v[i] ^= 1;
if (is_big[e[i].u]) now[e[i].u] ^= val[e[i].v];
if (is_big[e[i].v]) now[e[i].v] ^= val[e[i].u];
}
} else {
for (int i = p + 1; i < q; i++) flip[i] ^= 1;
for (int i = L[q]; i <= r; i++) {
v[i] ^= 1;
if (is_big[e[i].u]) now[e[i].u] ^= val[e[i].v];
if (is_big[e[i].v]) now[e[i].v] ^= val[e[i].u];
}
for (int i = l; i <= R[p]; i++) {
v[i] ^= 1;
if (is_big[e[i].u]) now[e[i].u] ^= val[e[i].v];
if (is_big[e[i].v]) now[e[i].v] ^= val[e[i].u];
}
}
}
int T1, kind, x, y, n, m, T2;
int main() {
srand(time(0));
scanf("%d", &T1);
while (T1--) {
tot = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
val[i] = Getrand(1e18);
G[i].clear();
now[i] = 0;
flip[i] = 0;
}
for (int i = 1; i <= m; i++) {
scanf("%d%d", &e[i].u, &e[i].v);
G[e[i].u].push_back(MPii(e[i].v, i));
G[e[i].v].push_back(MPii(e[i].u, i));
now[e[i].v] ^= val[e[i].u];
now[e[i].u] ^= val[e[i].v];
}
int t = sqrt(m);
uint block = t;
for (int i = 1; i <= t; i++) {
L[i] = (i - 1) * block + 1;
R[i] = i * block;
}
if (R[t] < m) {
R[++t] = m;
L[t] = R[t - 1] + 1;
}
for (int i = 1; i <= n; i++) {
if (G[i].size() >= block) {
is_big[i] = 1;
mp[i] = ++tot;
} else {
is_big[i] = 0;
mp[i] = 0;
}
}
assert(tot <= 1000);
assert(t <= 500);
for (int i = 1; i <= t; i++) {
for (int j = 1; j <= tot; j++) f[i][j] = 0;
for (int j = L[i]; j <= R[i]; j++) {
pos[j] = i;
v[j] = 0;
}
}
for (int i = 1; i <= t; i++) {
for (int j = L[i]; j <= R[i]; j++) {
if (is_big[e[j].u]) {
f[i][mp[e[j].u]] ^= val[e[j].v];
}
if (is_big[e[j].v]) {
f[i][mp[e[j].v]] ^= val[e[j].u];
}
}
}
scanf("%d", &T2);
while (T2--) {
scanf("%d%d%d", &kind, &x, &y);
if (kind == 1) {
change(x, y);
} else {
ll ans1 = now[x], ans2 = now[y];
if (is_big[x]) {
for (int i = 1; i <= t; i++) {
if (flip[i]) ans1 ^= f[i][mp[x]];
}
} else {
for (uint i = 0; i < G[x].size(); i++) {
Pii tmp = G[x][i];
if (v[tmp.second] ^ flip[pos[tmp.second]])
ans1 ^= val[tmp.first];
}
}
if (is_big[y]) {
for (int i = 1; i <= t; i++) {
if (flip[i]) ans2 ^= f[i][mp[y]];
}
} else {
for (uint i = 0; i < G[y].size(); i++) {
Pii tmp = G[y][i];
if (v[tmp.second] ^ flip[pos[tmp.second]])
ans2 ^= val[tmp.first];
}
}
printf("%d", ans1 == ans2);
}
}
printf("\n");
}
return 0;
}

B - Crazy Binary String

题目描述

ZYB loves binary strings (strings that only contains 0 and 1). And he loves equal binary strings\textit{equal binary strings}equal binary strings more, where the number of 0 and the number of 1 in the string are equal.

ZYB wants to choose a substring from an original string $ T $ so that it is an $ \text{equal binary string} $ with the longest length possible. He also wants to choose a subsequence of $ T $ which meets the same requirements.

A string $ v $ is a substring of a string $ w $ if $ v $ is empty, or there are two integers $ l $ and $ r \ (1 \le l \le r \le |w|) $ such that $ v=w_lw_{l+1}\cdots w_r $ . A string $ v $ is a subsequence of a string $ w $ if it can be derived from $ w $ by deleting any number (including zero) of characters without changing the order of the remaining characters.

For simplicity, you only need to output the maximum possible length. Note that the empty string is both a substring and a subsequence of any string.

输入描述

The first line of the input contains a single integer $ N \ (1 \le N \leq 100000) $ , the length of the original string $ T $ . The second line contains a binary string with exactly $ N $ characters, the original string $ T $ .

输出描述

Print two integers $ A $ and $ B $ , denoting the answer for substring and subsequence respectively.

示例1

输入

1
2
8
01001001

输出

1
4 6

题解

题意

给定一个长度为 $ n $ 的01字符串,询问01个数相同的最长的子串与子序列的长度。

解法

  • 子串

    • 令 $ f_{i} $ 表示前 $ i $ 个字符中01的数量差,那么答案为相距最远且值相同的一对 $ f_i $ 与 $ f_j $ 的距离,即 $ \max(i-j|f_i=f_j) $
    • 对于每一个差值,记录它在 $ f $ 数组中第一次出现的下标,每次遇到出现过的 $ f_i $ ,把它与答案比对即可。
  • 子序列

    • 子序列可以任取,因此01里面数量最少的那个对答案有限制。令字符串中01的数量分别为 $ n_{0} $ 和 $ n_{1} $ ,答案为 $ 2 \times \min(n_0,n_1) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
char a[100010];
map<int, int> mp;
int n, num, ans;
int main() {
scanf("%d%s", &n, a + 1);
for (int i = 1; i <= n; i++) {
if (a[i] == '1') num++;
if (mp[i - 2 * num] || i == 2 * num)
ans = max(ans, i - mp[i - 2 * num]);
else
mp[i - 2 * num] = i;
}
printf("%d %d\n", ans, 2 * min(n - num, num));
return 0;
}

C - Guessing ETT

题目描述

ZYB is a smart guy.

One day he learns a new method for representing trees: Euler tour technique (ETT).

You can find more details about ETT on this web page:

https://en.wikipedia.org/wiki/Euler_tour_technique.

https://blog.nowcoder.net/n/7afe88dc36ef4649b4de941f08abf576

If we use vertices rather than edges in ETT, then any tree with $ N $ vertices corresponds to a sequence of length $ 2N-1 $ , let’s call it the vertex-ETT sequence.

In the beginning, ZYB generates a tree (the root of that tree is always 1) and writes down its vertex-ETT sequence.

However, he spilt ink onto the paper by mistake and some numbers were covered in ink.

Can you help him to restore the sequence?

输入描述

There are multiple test cases. The first line of the input contains an integer $ T $ , indicating the number of test cases.

For each test case, the first line contains a integer $ N $ ( $ 1 \leq N \leq 2.5 \times 10^5 $ ) , while the second line contains an integer sequence $ a $ ( $ 1 \leq a_i \leq N $ or $ a_i=-1 $ ) , which means this number was covered by the ink) of length $ 2N-1 $ , the vertex-ETT sequence.

it is guaranteed that at least one valid sequence exists.

It’s guaranteed that the sum of $ N $ of all test cases will not exceed $ 500000 $ .

Due to the large size of the input, it’s recommended to use a fast way to read the input.

输出描述

For each case, print $ 2N-1 $ space-separated integers, the recovered sequence.
If there are multiple solutions, print any of them.

示例1

输入

1
2
3
4
5
2
3
1 2 1 -1 1
3
-1 2 3 -1 1

输出

1
2
1 2 1 3 1
1 2 3 2 1

D - Big Integer

题目描述

For little pupils, a very large number usually means an integer with many many digits. Let’s define a class of big integers which consists only of the digit one $ (11 \cdots 1) $ . The first few integers in this class are $ 1, 11, 111, 1111 \cdots $ . Denote $ A(n) $ as the $ n $ -th smallest integer in this class. To make it even larger, we consider integers in the form of $ A(a^b) $ . Now, given a prime number $ p $ , how many pairs $ (i, j) $ are there such that $ 1 \leq i \leq n,\ 1 \leq j \leq m,\ A(i^j) \equiv 0(mod \ p) $ .

输入描述

The input contains multiple cases. The first line of the input contains a single integer $ T \ (1 \le T \le 100) $ , the number of cases.
For each case, the input consists of a single line, which contains $ 3 $ positive integers $ p, n, m \ (p, n, m \leq 10^9) $ .

输出描述

Print the answer, a single integer, in one separate line for each case.

示例1

输入

1
2
3
2
11 8 1
7 6 2

输出

1
2
4
2

题解

题意

定义 $ A(n) $ 为 $ n $ 个 $ 1 $ 表示的十进制数,例如 $ A(3)=111 $

询问对于 $ 1≤i≤n,1≤j≤m $ 问有多少对 $ (i , j) $ 满足 $ A(i^j) \equiv 0( \mod p) $

解法

$ 11⋯111=10n−19≡0(\mod p) $ 等价于 $ 10n≡1(\mod 9p) $

当 $ p=2,5 $ 时,显然答案为 $ 0 $ (因为 $ 11 \dots 111 $ 模 $ 2 $ 或 $ 5 $ 肯定不为 $ 0 $ )

当 $ p≠2,5 $ 时,有 $ gcd(10,9p)=1 $ ,即 $ 10ϕ(9p)≡1(\mod 9p) $

$ ϕ(9p) $ 是欧拉函数,这个式子由欧拉定理可知

所以只需要找 $ 10i \mod 9p $ 的最小循环节 $ d $ ,显然 $ d|ϕ(9p) $ ,所以只需要暴力找 $ ϕ(9p) $ 的因子,找到最小的符合条件的即可

”显然成立“部分证明:

设 $ d $ 不是 $ n=ϕ(9p) $ 的因子,那么 $ n=kd+r $ , 又 $ 10n≡1(\mod 9p) $ , $ 10d≡1(\mod9p) $ ,所以有 $ 10r≡1(\mod 9p) $ , $ r $ 比 $ d $ 小,与 $ d $ 最小矛盾

接下来只需要找有多少对 $ (i , j) $ ,满足 $ d|i^j $

把 $ d $ 质因数分解 $ d = p_{1}^{k_{1}} \times p_{2}^{k_{2}} \times \dots \times p_{l}^{k{l}} $ , 要使得 $ (i,j) $ 是 $ d $ 的倍数,那么在 $ (i,j) $ 的质因数分解中 $ p1,p2 \dots pl $ 的指数中都要比 $ d $ 中的大,所以我们考虑 $ j $ 固定的时候,有多少个 $ i $ 可以满足条件

不难想到, $ i $ 必须是 $ g = p_{1}^{\dfrac{k_1}{j}} \times p_{2}^{\dfrac{k_2}{j}} \dots p_{l}^{\dfrac{k_l}{j}} $ 的倍数(至于为什么上取整,可以想一想,因为要求最小的 $ x $ , 有 $ x∗j>=k1 $ ,且 $ x∗(j−1)<k1 $ ),因此一共有 $ \dfrac{n}{g} $ 个合法的 $ i $ 。

取 $ mx=max(k_1,k_2 \dots k+l) $ 那么 我们只需要依次计算 $ j(j∈[1,mx]) $ 就可以了。而对于 $ j>mx $ 的部分,合法的 $ i $ 的个数都是一样的。不妨带入上式看一看。

同时代码中会遇到这样一些问题:

计算 $ ϕ(9p) $ 后,枚举因数找循环节时,快速幂会爆long long,所以要用快速乘(因为 $ p $ 最大 $ 1e9 $ )

另一种方法是,因为欧拉函数是积性函数,所以如果 $ 9 $ 和 $ p $ 互质,那么 $ ϕ(9p)=phi(9)∗(p−1) $ ,对 $ p=3 $ 的情况进行特判,而对于其他情况只需要枚举ϕ(p)ϕ(p)的因子即可。

因为当 $ 9 $ 和 $ p $ 互质时,若有 $ n $ 对 $ 10n≡1(\mod 9p) $ 成立,那么一定有 $ 10n≡1(\mod p) $ 成立

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
int n, m, p;
int q[N], c[N], tot;
ll mul(ll a, ll b, ll p) {
ll ret = 0;
while (b) {
if (b & 1) ret = (ret + a) % p;
b /= 2;
a = (a + a) % p;
}
return ret;
}
ll ksm(ll a, ll b, ll mod) {
ll res = 1;
for (; b; b >>= 1) {
if (b & 1) res = mul(res, a, mod);
a = mul(a, a, mod);
}
return res;
}
ll getphi(ll x) {
ll res = x;
for (ll i = 2; i * i <= x; i++) {
if (x % i == 0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &p, &n, &m);
if (p == 2 || p == 5) {
puts("0");
continue;
}
ll phi = getphi(9ll * p);
ll fac = 1e18;
for (ll i = 2; i * i <= phi; i++) {
if (phi % i == 0) {
if (ksm(10, i, p * 9ll) == 1) fac = min(fac, i);
if (ksm(10, phi / i, p * 9ll) == 1) fac = min(fac, phi / i);
}
}
tot = 0;
for (int i = 2; i * i <= fac; i++) {
if (fac % i == 0) {
q[++tot] = i;
c[tot] = 0;
while (fac % i == 0) fac /= i, c[tot]++;
}
}
if (fac > 1) q[++tot] = fac, c[tot] = 1;
ll res = 0;
int mx = 0;
for (int i = 1; i <= tot; i++) mx = max(mx, c[i]);
for (int j = 1; j <= mx && j <= m; j++) {
int now = 1;
for (int i = 1; i <= tot; i++) {
int k = c[i] / j + (c[i] % j != 0);
for (int o = 1; o <= k; o++) now *= q[i];
}
res += n / now;
}
if (m > mx) {
int now = 1;
for (int i = 1; i <= tot; i++) now *= q[i];
res += 1ll * (m - mx) * (n / now);
}
printf("%lld\n", res);
}
return 0;
}

E - Trees in the Pocket II

题目描述

DreamGrid has just found two trees, both consisting of n vertices, in his right pocket. Each edge in each tree has its own weight. The i-th edge in the first tree has a weight of $ a_{i} $ , while the i-th edge in the second tree has a pair of weight, denoted by $ (b_i, c_i) $ .

Let $ {}^1u $ be the $ u $ -th vertex in the first tree, and $ {}^2u $ be the $ u $ -th vertex in the second tree. Let $ \mathbb{E}_1({}^1u, {}^1v) $ be the set containing the indices of all the edges on the path between the $ u $ -th and the $ v $ -th vertex in the first tree. Similarly, let $ \mathbb{E}_2({}^2u, {}^2v) $ be the set containing the indices of all the edges on the path between the $ u $ -th and the $ v $ -th vertex in the second tree. Define the following values:

$ A_{\min}({}^1u, {}^1v) = \min\{a_k | k \in \mathbb{E}_1({}^1u, {}^1v)\} $

$ B_{\max}({}^2u, {}^2v) = \max\{b_k | k \in \mathbb{E}_2({}^2u, {}^2v)\} $

$ C_{\max}({}^2u, {}^2v) = \max\{c_k | k \in \mathbb{E}_2({}^2u, {}^2v)\} $

As DreamGrid is bored, he decides to count the number of good indices. DreamGrid considers an index $ i (1 \le i \le n) $ is good, if for all $ 1 \le j \le n $ and $ j \ne i $ , $ A_{\min}({}^1i, {}^1j) \ge \min(B_{\max}({}^2i, {}^2j), C_{\max}({}^2i, {}^2j)) $ . Please help DreamGrid figure out all the valid indices.

You may have seen this problem before, but this time we need you to have an $ O(N \log N) $ solution, or it may not pass.

输入描述

There are multiple test cases. The first line contains an integer $ T $ , indicating the number of test cases. For each test case:

The first line contains an integer $ n (2 \le n \le 10^5) $ indicating the number of vertices in both trees.

For the following $ (n-1) $ lines, the $ i $ -th line contains three integers $ {}^1u_i $ , $ {}^1v_i $ and $ a_i (1 \le {}^1u_i, {}^1v_i $ , $ 1 \le a_i \le 10^9) $ , indicating that there is an edge, whose weight is $ a_i $ , connecting vertex $ u_i $ and $ v_i $ in the first tree.

For the following $ (n-1) $ lines,the $ i $ -th line contains four integers $ {}^2u_i $ , $ {}^2v_i $ , $ b_i $ and $ c_i $ ( $ 1 \le {}^2u_i, {}^2v_i \le n $ , $ 1 \le b^2_i, c^2_i \le 10^9 $ ), indicating that there is an edge, whose weight is $ (b_i, c_i) $ , connecting vertex $ u_i $ and $ v_i $ in the second tree.

It’s guaranteed that the sum of $ n $ of all test cases does not exceed $ 2 \times 10^5 $ .

输出描述

For each test case output $ k $ integers ( $ k $ is the number of valid indices) in one line separated by a space in increasing order, indicating the indices of the valid vertices.

Note that if there is no valid vertex, you should print -1 instead.

示例1

输入

1
2
3
4
5
6
7
8
9
10
11
2
2
1 2 1
1 2 2 3
4
1 2 7
1 3 8
1 4 12
1 2 8 8
2 3 9 7
2 4 6 4

输出

1
2
-1
3 4

F - Planting Trees

题目描述

The semester is finally over and the summer holiday is coming. However, as part of your university’s graduation requirement, you have to take part in some social service during the holiday. Eventually, you decided to join a volunteer group which will plant trees in a mountain.

To simplify the problem, let’s represent the mountain where trees are to be planted with an $ N \times N $ grid. Let’s number the rows $ 1 $ to $ N $ from top to bottom, and number the columns $ 1 $ to $ N $ from left to right. The elevation of the cell in the $ i $ -th row and $ j $ -th column is denoted by $ a_{i,j} $ . Your leader decides that trees should be planted in a rectangular area within the mountain and that the maximum difference in elevation among the cells in that rectangle should not exceed M. In other words, if the coordinates of the top-left and the bottom-right corners of the rectangle are $ (x_1,y_1) $ and $ (x_2,y_2) $ , then the condition $ |a_{i,j} - a_{k,l}| \le M $ must hold for $ x_1 \le i,k \le x_2, \ y_1 \le j,l \le y_2 $ . Please help your leader calculate the maximum possible number of cells in such a rectangle so that he’ll know how many trees will be planted.

输入描述

The input contains multiple cases. The first line of the input contains a single integer $ T \ (1 \le T \le 1000) $ , the number of cases.

For each case, the first line of the input contains two integers $ N\ (1 \le N \le 500) $ and $ M\ (0 \le M \le 10^5) $ . The following $ N $ lines each contain $ N $ integers, where the $ j $ -th integer in the $ i $ -th line denotes $ a_{i,j} \ (1 \le a_{i,j} \le 10^5) $ .

It is guaranteed that the sum of $ N^3 $ over all cases does not exceed $ 25 \cdot 10^7 $ .

输出描述

For each case, print a single integer, the maximum number of cells in a valid rectangle.

示例1

输入

1
2
3
4
5
6
7
8
2
2 0
1 2
2 1
3 1
1 3 2
2 3 1
3 2 1

输出

1
2
1
4

题解

题意

给定一个 $ n \times n $ 的矩阵,求它的最大子矩阵,满足矩阵中最大值与最小值之差不超过 $ m $ 。

解法

根据题意所给条件,可以知道是 $ \mathcal{O}(n^3) $ 的算法。

枚举上下边界,用两个单调队列分别维护最大值与最小值,从左向右扫过去。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define N 501
#define inf 2147483647
int a[N][N], maxn[N], minn[N], q[N][2];
int main() {
int T, n, m;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) maxn[j] = -inf, minn[j] = inf;
for (int j = i; j <= n; j++) {
for (int k = 1; k <= n; k++) {
maxn[k] = max(maxn[k], a[j][k]);
minn[k] = min(minn[k], a[j][k]);
}
int l = 1, h0 = 0, t0 = 1, h1 = 0, t1 = 1;
for (int r = 1; r <= n; r++) {
while (t0 <= h0 && maxn[r] >= maxn[q[h0][0]]) h0--;
while (t1 <= h1 && minn[r] <= minn[q[h1][1]]) h1--;
q[++h0][0] = r;
q[++h1][1] = r;
while (l <= r && maxn[q[t0][0]] - minn[q[t1][1]] > m) {
l++;
if (q[t0][0] < l) t0++;
if (q[t1][1] < l) t1++;
}
ans = max(ans, (r - l + 1) * (j - i + 1));
}
}
}
printf("%d\n", ans);
}

return 0;
}

G - Removing Stones

题目描述

Summer vacation is coming and Mark has returned home from his university having successfully survived the exam week. Today, he is very bored. So his friend Alice challenges him to play a game with stones which is invented by her. Alice gives Mark $ N $ piles of stones numbered from $ 1 $ to $ N $ , and there are $ a_i $ stones in the $ i $ -th pile. The rules of the game are simple: Mark will try to remove all stones. In each move, Mark chooses two different non-empty piles and removes one stone from each of those two piles. Mark can perform any number of moves. If all the piles are empty after some number of moves, Mark wins the game. If he can’t make a valid move but not all piles are empty, he loses the game. Obviously, if the total number of stones is odd, then Mark is not able to win the game. So there is an additional rule: if initially, the total number of stones is odd, then Mark removes a single stone from the pile with the fewest stones before starting the game. If there are multiple piles with the smallest number of stones, Mark chooses one among them to remove a stone.

Mark found the optimal strategy for Alice’s game very quickly and gets bored again. Also, he noticed that for some configuration of stones there is no way to win. So he challenges you to solve this problem: count the number of integer pairs $ (l,r) \ (1 \le l < r \le N) $ such that it is possible for Mark to win the game if the game is played using only the piles numbered from $ l $ to $ r $ .

输入描述

The input contains multiple cases. The first line of the input contains a single positive integer $ T $ , the number of cases.

The first line of each case contains a single integer $ N \ (2 \le N \le 300000) $ , the number of piles. The following line contains $ N $ space-separated integers, where the $ i $ -th integer denotes $ a_i \ (1 \le a_i \le 10^9) $ , the number of stones in the $ i $ -th pile.

It is guaranteed that the sum of $ N $ over all cases does not exceed $ 1000000 $ .

输出描述

For each case, print a single integer on a single line, the number of pairs satisfying the required property.

示例1

输入

1
2
3
4
5
2
3
1 1 1
4
1 2 3 4

输出

1
2
3
3

题解

题意

给定一个序列,询问有多少个长度不小于2的连续子序列,使得其中最大元素不超过所有元素和的1/2.。

解法

枚举以每个数为最大值的区间,采用笛卡尔树的结构分治解决。

左右区间中每次选择短的那个遍历,另外一个 $ \mathcal{O}(\log n) $ 查询。

总时间复杂度为 $ \mathcal{O}(n \log^2 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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 300010
int a[N], x, ls[N], rs[N];
int Stack[N];
bool vis[N];
ll s[N];
void dfs(int x, int l, int r, ll &ans) {
if (l >= r) return;
if (x - l < r - x) {
for (int i = l; i <= x; i++) {
int k = lower_bound(s + x, s + r + 1, s[i - 1] + 2ll * a[x]) - s;
if (k == i) k++;
if (k == r + 1) continue;
ans += (ll)(r - k + 1);
}
} else {
for (int i = x; i <= r; i++) {
int k = upper_bound(s + l, s + x + 1, s[i] - 2ll * a[x]) - s;
if (s[i] - s[k - 1] >= 2 * a[x]) k++;
k = min(k, x + 1);
ans += max(0, k - l);
}
}
dfs(ls[x], l, x - 1, ans);
dfs(rs[x], x + 1, r, ans);
}
int main() {
int T, n;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + (ll)a[i];
}
int top = 0;
for (int i = 1; i <= n; i++) ls[i] = rs[i] = vis[i] = 0;
for (int i = 1; i <= n; i++) {
int lson = -1;
while (top && a[Stack[top]] < a[i]) lson = Stack[top], top--;
if (top) rs[Stack[top]] = i;
if (~lson) ls[i] = lson;
Stack[++top] = i;
}
for (int i = 1; i <= n; i++) vis[ls[i]] = vis[rs[i]] = true;
int add = 0;
for (int i = 1; i <= n; i++)
if (!vis[i]) {
add = i;
break;
}
ll ans = 0;
dfs(add, 1, n, ans);
printf("%lld\n", ans);
}
return 0;
}

H - Magic Line

题目描述

There are always some problems that seem simple but is difficult to solve.

ZYB got $ N $ distinct points on a two-dimensional plane. He wants to draw a magic line so that the points will be divided into two parts, and the number of points in each part is the same. There is also a restriction: this line can not pass through any of the points.

Help him draw this magic line.

输入描述

There are multiple cases. The first line of the input contains a single integer $ T \ (1 \leq T \leq 10000) $ , indicating the number of cases.

For each case, the first line of the input contains a single even integer $ N \ (2 \leq N \leq 1000) $ , the number of points. The following $ N $ lines each contains two integers $ x_i, y_i \ (|x_i, y_i| \leq 1000) $ , denoting the x-coordinate and the y-coordinate of the $ i $ -th point.

It is guaranteed that the sum of $ N $ over all cases does not exceed $ 2 \times 10^5 $ .

输出描述

For each case, print four integers $ x_1, y_1, x_2, y_2 $ in a line, representing a line passing through $ (x_1, y_1) $ and $ (x_2, y_2) $ . Obviously the output must satisfy $ (x_1,y_1) \ne (x_2,y_2) $ .

The absolute value of each coordinate must not exceed $ 10^9 $ . It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.

示例1

输入

1
2
3
4
5
6
1
4
0 1
-1 0
1 0
0 -1

输出

1
-1 999000000 1 -999000001

题解

题意

给定平面上 $ n $ 个点(保证 $ n $ 为偶数)求一直线将平面上的点分为数量相等的两部分,直线上不能有点。输出线上两个点确定该直线。

解法

将这 $ n $ 个数按照横坐标第一关键字,纵坐标第二关键字排序,找到排名最中间的那个点,在它下面画一条斜率极大的直线即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define Pii pair<int, int>
#define N 1001
#define S 10000
Pii p[N];
int main() {
int n, m, T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].first, &p[i].second);
sort(p + 1, p + n + 1);
int m = n / 2;
int x1 = p[m].first - 1, x2 = p[m].first + 1;
int y1 = p[m].second + S, y2 = p[m].second - S + 1;
printf("%d %d %d %d\n", x1, y1, x2, y2);
}
return 0;
}

I - Median

题目描述

JSB has an integer sequence $ a_1, a_2, \dots, a_n $ . He wants to play a game with SHB.

For each $ 1 \le i \le n-2 $ , JSB calculates the median of $ \{a_i, a_{i+1}, a_{i+2}\} $ , denoted by $ b_i $ . SHB is given the sequence $ b_1, b_2, \dots, b_{n-2} $ . Can you help him restore the sequence $ a $ ?

Recall that the median of three numbers is the second largest one of them.

输入描述

There are multiple cases. The first line of the input contains a single positive integer $ T $ , indicating the number of cases.

For each case, the first line of the input contains a single integer $ n\ (3 \le n \le 10^5) $ , the length of the sequence $ a $ . The second line contains $ n-2 $ integers $ b_1, b_2, \dots, b_{n-2}\ (0 \le b_i \le 10^9) $ .

It’s guaranteed that the sum of $ n $ over all cases does not exceed $ 10^6 $ .

输出描述

For each case print one line containing $ n $ integers, indicating the sequence $ a_1, a_2, \dots, a_n $ . Your output must satisfy $ 0 \le a_i \le 10^9 $ for each $ 1 \le i \le n $ .

If there are multiple valid answers, you may print any of them. If there is no valid answer, print”-1” (without quotes) instead.

示例1

输入

1
2
3
4
5
6
7
8
9
4
5
1 2 3
6
1 2 3 4
6
1 2 4 3
6
1 3 4 2

输出

1
2
3
4
1 1 3 2 3
1 2 1 4 3 4
1 1 4 2 4 3
-1

题解

题意

给定一个序列 $ b $ ,要求构造一个序列 $ a $ ,使得 $ b_i $ 为 $ a_{i},a_{i+1},a_{i+2} $ 三个数的中位数。

解法

令 $ f_{i,j,k} $ 表示在前 $ i $ 个数中,第 $ i $ 个数取了第 $ j $ 个中位数,第 $ i-1 $ 个数取了第 $ k $ 个中位数的方案是否可行。

那么可以从 $ f_{i-1,k,l} $ 转移到 $ f_{i,j,k} $

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
int vec[N][3], pre[N][3][3], b[N], n;
bool f[N][3][3];
bool check(int ti, int j, int k, int l) {
int s[4] = {vec[ti][j], vec[ti - 1][k], vec[ti - 2][l], 0};
sort(s, s + 3);
return (s[1] == b[ti - 1]);
}
void print(int t, int j, int k) {
if (t == 1)
printf("%d ", vec[t][j]);
else {
print(t - 1, k, pre[t][j][k]);
printf("%d%c", vec[t][j], t == n ? '\n' : ' ');
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 2; i < n; i++) scanf("%d", &b[i]);
for (int i = 1; i <= n; i++)
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++) f[i][j][k] = false;
b[n + 1] = b[n] = b[n - 1];
b[0] = b[1] = b[2];
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) vec[i][j] = b[i + j - 1];
sort(vec[i], vec[i] + 3);
}
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) f[1][i][j] = f[2][i][j] = true;
for (int i = 3; i <= n; i++)
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++)
for (int l = 0; l < 3; l++)
if (f[i - 1][k][l] && check(i, j, k, l))
f[i][j][k] = true, pre[i][j][k] = l;
bool flag = true;
for (int j = 0; j < 3 && flag; j++)
for (int k = 0; k < 3 && flag; k++)
if (f[n][j][k]) {
flag = false;
print(n, j, k);
}
if (flag) puts("-1");
}
return 0;
}

J - LRU management

题目描述

ZYB has finished his computer course recently. He is very interested in the LRU algorithm for cache management.

To simplify the problem, assume that a block contains a name (which is a string) and a set of data (which is a number). ZYB wants to implement the LRU algorithm with an array.

His array can hold at most $ M $ elements at any time. In the beginning, the array is empty. In each operation, the CPU may access a block $ s $ . ZYB will search for it in his array by brute force. If this block is present in his array (which means he can find a block with the same name), he takes it out of the array and puts it back at the end of the array. Otherwise, he simply adds it to the end of the array. If at any time, the size of the array exceeds the capacity, he will remove the first block in his array (the block at the front of the array).

Seems boring? Well, sometimes ZYB may ask the data of a block in, before or after a certain block. Could you help him to write a program to achieve his goal?

输入描述

There are multiple cases. The first line of the input contains a single positive integer $ T $ , indicating the number of cases.

For each case, the first line of the input contains two integers $ Q $ and $ M\ (1 \leq Q, \ M \leq 500000) $ , denoting the number of operations and the capacity of the array. The following $ Q $ lines each contain an integer $ opt \ (0 \le opt \le 1) $ , a string $ s \ (1 \leq |s| \leq 10) $ and an integer $ v $ , separated by single spaces, describing an operation.

If $ opt = 0 $ , then $ |v| < 10 $ , and the operation is that the CPU wants to access a block. If this access misses (which means you can’t find a block in the array with the name $ S $ ), add a block at the end of the array with the name $ S $ and the data $ V $ , and the result of the operation is $ V $ . If this access hits, the result of the operation is the data of the block you found (ignore $ V $ in this case). Don’t forget to move that block to the end of the array.

If $ opt = 1 $ , then $ v $ will be $ -1,0 $ or $ 1 $ , and the operation is that you should answer ZYB’s question. Let $ k $ be the index of the block with the name $ s $ in the array. Then the result of this operation is the data of the block with the index $ k+v $ in the array. If such block doesn’t exist, please output “Invalid’’ (without quotation marks) instead.

Note that ZYB’s questions (operations of type $ 1 $ ) don’t count as access and don’t cause the array to be updated.

It is guaranteed that the sum of $ Q $ over all cases does not exceed $ 1000000 $ , and that $ s $ only contains digits (i.e. 0 - 9).

输出描述

For each case, print the result of each operation in a line as defined in the input section of the statement.

示例1

输入

1
2
3
4
5
6
7
8
9
10
1
8 3
0 0101010 1
0 0101011 2
1 0101010 1
0 1100000 3
0 0101011 -1
0 1111111 4
1 0101011 -1
1 0101010 0

输出

1
2
3
4
5
6
7
8
1
2
2
3
2
4
3
Invalid

题解

题意

要求模拟出计算机组成原理里的cache的LRU管理算法

解法

根据这个数据结构的特点,也就是计算机组成原理里的cache的LRU管理算法,每次访问都会在cache中查询一页,查询成功则调用该页的值并将该页移动到删除队列的尾部。否则直接加载该页在删除队列的尾部,当队列满时弹出队首。另一种操作是查询到某页后调用其、或其前一页、或其后一页,失败均返回Invalid。

那么一个可以删除中间元素的队列,明显用链表实现,而且要其前一页、后一页,那就双向链表。因为链表的瓶颈在于查询,而这道题的特点可以使用其他数据结构加速查询的过程。这里都是短的字符串,可以用unordermap或者trie来维护“字符串对应的链表节点”。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000005
struct node {
int key, pre, nxt;
} cash[N << 1];
unordered_map<ll, int> ft;
unordered_set<int> st;
int stl, total, head, tail;
void ins(int add) {
st.insert(add);
int preadd = cash[tail].pre;
cash[preadd].nxt = add;
cash[add].pre = preadd;
cash[add].nxt = tail;
cash[tail].pre = add;
}
void del(int add) {
st.erase(add);
cash[cash[add].pre].nxt = cash[add].nxt;
cash[cash[add].nxt].pre = cash[add].pre;
}
int n, m;
int main() {
int T;
cin >> T;
while (T--) {
ft.clear();
st.clear();
stl = 0, total = 2, head = 0, tail = 1;
cash[head].nxt = tail;
cash[tail].pre = head;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int opt, v;
char s[20];
scanf("%d%s%d", &opt, s, &v);
ll ladd = 0;
for (int j = 0; j < strlen(s); j++)
ladd = 10 * ladd + s[j] - '0' + 1;
if (opt == 0) {
if (ft.find(ladd) == ft.end()) ft[ladd] = total++;
int add = ft[ladd];
if (st.find(add) == st.end()) {
cash[add].key = v;
ins(add);
if (++stl > m) {
del(cash[head].nxt);
stl--;
}
} else {
del(add);
ins(add);
}
printf("%d\n", cash[add].key);
} else {
if (ft.find(ladd) == ft.end()) {
puts("Invalid");
continue;
}
int add = ft[ladd];
if (st.find(add) == st.end()) {
puts("Invalid");
continue;
}
int ad = add;
if (v == 1)
ad = cash[ad].nxt;
else if (v == -1)
ad = cash[ad].pre;
if (ad == head || ad == tail)
puts("Invalid");
else
printf("%d\n", cash[ad].key);
}
}
}
return 0;
}