以后的题解按 Q&A 的形式写，这也是我赛时的思考方法 ~
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
set<int> a, b;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a.insert(x);
}
for (int i = 0; i < n; i++) {
int x;
cin >> x;
b.insert(x);
}
cout << (a.size() + b.size() >= 4 ? "YES" : "NO") << endl;
}
return 0;
}
|
卡 B 果断跳过，做完 C D 才回去写的 B。
Q1 条件好复杂，情况也很多，我怎么判断？
A1 情况很多就对了，说明这很灵活很自由。再读题，需要找第一个bi=i，那如果答案为 1，就说明要找一个b1=1，也即ai=1，这个条件很松。
Q2 还有其它限制呢，什么样的ai=1 满足题意？
A2 首先i>1（1 下标）。i 也不能太大，毕竟这是第一段，需要给后面留足空间，这不难推得是1<i⩽n−(k−2)。
Q3 如果找不到ai=1 怎么办？
A3 答案将>1，而且有很多ai=1。现在要找一个b2=2。
观察第三个样例，1<i⩽n−(k−2) 解得i=2,3，于是b1=a2=1,b2=a3=1=2 就找到了一个b2=2。
更进一步，只要解出来的i 的数量不止一个，那第二个i 就一定满足b2=ai=1=2。
这就需要进一步分类讨论n=k 和n=k。
Q4 如何实现？
A4 先分两种情况，n=k 和n=k。前者分段方法唯一，暴力算答案。后者进一步分为能否找到ai=1。
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
| #include <bits/stdc++.h>
using LL = long long;
using ll = long long;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
if (n == k) {
int mex = 1;
for (int i = 1; i < n; i += 2) {
if (a[i] != mex) {
break;
} else {
mex++;
}
}
cout << mex << endl;
} else {
bool flag = false;
for (int i = 1; i < n - (k - 2); i++) {
if (a[i] != 1) {
flag = true;
break;
}
}
cout << (2 - flag) << endl;
}
}
return 0;
}
|
Q1 这能做吗？
A1 请先检查有没有读错题：
最终留下的是后缀和，而不是前缀和；
除去长度为n 的后缀和，每个后缀和的长度互不相同；
最大化n 个后缀和（称为c 序列）的 mex；
ai⩾1。如果没有这一条，这或许是个 NP-hard 问题。
Q2 我没有读错题。这道题的突破口在哪里？
A2 关注ai⩾1。思考如果答案 mex>1，什么样的后缀和可能是 1？什么样的后缀和可能是 2？
Q3 请说具体点。
A3 我们总能清空一行，于是c 序列一定包含0。
如果 mex>1，说明c 序列至少有一个1。如果某个后缀和为 1，且每个元素ai⩾1，那这个后缀和只能有且仅有一个元素，且这个元素为 1，也就是 xxxxx1 的形式。
如果 mex>2，说明c 序列至少有一个1 和一个 2。如果某个后缀和为 2，可能是 xxxxx2，也可能是 xxxx11。由于c 序列包含1，所以已经存在长度为 1 的后缀和。按题意「每个后缀和的长度互不相同」，后缀和为 2 的序列只能是 xxxx11 的形式。
以此类推，后缀和为k 只能是 xxxx111…11 的形式。
记录后缀 1 的数量。每次只要能找到某个后缀长度⩾k，就说明c 序列可以出现这个元素。
时间复杂度O(n2+nlogn)
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
priority_queue<int, vector<int>, greater<>> Q;
for (int i = 0; i < n; i++) {
vector<int> a(n);
for (int j = 0; j < n; j++) {
cin >> a[j];
}
int j = n - 1;
while (j >= 0 && a[j] == 1) {
j--;
}
Q.push(n - 1 - j);
}
int mex = 0;
while (!Q.empty()) {
while (!Q.empty() && Q.top() < mex) {
Q.pop();
}
if (Q.empty()) {
break;
}
Q.pop();
mex++;
}
cout << mex << endl;
}
return 0;
}
|
Q1 什么时候结果将无限大？
A1 先讨论什么时候不是无限大，这说明在某一次操作之后，∣u1−u2∣ 总是为 0。也就是说，两张图 至少存在一组完全相同的边。否则，结果将无限大。
Q2 不考虑最小化结果，我如何判断能否走到一组点？
A2 BFS。由于每一对点(x,y) 只会经过一次，所以 BFS 的不同状态数只有O(n2)，可以接受。
Q3 现在有很多组完全相同的边，我如何判断找到了其中一组可能的点？
A3 一种方法是用 std::map 或 std::set 的 count 函数。也可以从终点倒着 BFS（我的写法），具体来说是把所有终点一并扔到 queue 里，这样起点唯一，就好判断了。
Q4 如何最小化结果？
A4 这个问题类似于求最短路，我们仿照 Dijkstra 的思想，用堆存所有可能值，每次取出最小代价的一对点，push 所有相邻的点对。时间复杂度多个log。
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 LL = long long;
using ll = long long;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int s1, s2;
cin >> s1 >> s2;
s1--, s2--;
int m;
cin >> m;
vector<pair<int, int>> edge1(m);
vector<vector<int>> E1(n);
for (auto& [u, v] : edge1) {
cin >> u >> v;
u--, v--;
E1[u].push_back(v);
E1[v].push_back(u);
}
cin >> m;
vector<pair<int, int>> edge2(m);
vector<vector<int>> E2(n);
for (auto& [u, v] : edge2) {
cin >> u >> v;
u--, v--;
E2[u].push_back(v);
E2[v].push_back(u);
}
priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> Q;
for (auto [u1, v1] : edge1) {
for (auto [u2, v2] : edge2) {
if (u1 == u2 && v1 == v2) {
Q.push({ 0, u1, u1 });
}
if (u1 == v2 && v1 == u2) {
Q.push({ 0, u1, u1 });
}
}
}
vector vis(n, vector<int>(n));
ll res = -1;
while (!Q.empty()) {
auto [d, u1, u2] = Q.top();
Q.pop();
if (vis[u1][u2]) continue;
vis[u1][u2] = true;
if (u1 == s1 && u2 == s2) {
res = d;
break;
}
d += abs(u1 - u2);
for (auto v1 : E1[u1]) {
for (auto v2 : E2[u2]) {
Q.push({ d, v1, v2 });
}
}
}
cout << res << endl;
}
return 0;
}
|
