# Codeforces Round 669 (CF1407) 题解
# Problem A - Ahahahahahahahaha (opens new window)
# 题目描述
长度为(为偶数)的串,要求删去至多个数,使得剩下的数满足交错和。
# 题解
因为至多删去个数,所以我们总可以删除和中出现次数较少的那一种。出现次数相同时我们选择留下,因为的交错和总为。
但要特别注意,如果留下的是,需要检查一下总个数是否为偶数,如果不是,还需要进行调整。
时间复杂度。
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int n;
read(n);
vector<int> a(n);
int z = 0;
for (int i = 0; i < n; ++i)
read(a[i]), z += (a[i] == 0);
int k = z, d = 0;
if (z < n - z) {
d = 1;
k = n - z;
if (k % 2 == 1)
k--;
}
printf("%d\n", k);
vector<int> ans(k, d);
for (int i : ans)
printf("%d ", i);
printf("\n");
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
# Problem B - Big Vova (opens new window)
# 题目描述
要求将数组重新排序,使得所构成的序列字典序最大。
# 题解
每次贪心地从剩下元素中找出能使得其与当前最大公约数的最大公约数最大的元素即可。如果存在多个,选择其中任何一个都行,因为剩下几个在接下来的轮次里也一定会被选到。
时间复杂度,其中是数组中的最大元素。
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
class Solution {
public:
void solve() {
int n;
read(n);
vector<int> a(n);
for (int i = 0; i < n; ++i)
read(a[i]);
vector<bool> vis(n);
vector<int> ans(n);
int g = 0;
for (int i = 0; i < n; ++i) {
int hi = -1, hidx = -1;
for (int j = 0; j < n; ++j) {
if (vis[j])
continue;
int gj = gcd(g, a[j]);
if (gj > hi) {
hi = gj;
hidx = j;
}
}
ans[i] = a[hidx];
vis[hidx] = true;
g = hi;
}
for (int i : ans)
printf("%d ", i);
printf("\n");
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
# Problem C - Chocolate Bunny (opens new window)
# 题目描述
交互题。给定到的一个排列,每次可以询问两个位置和,系统会告诉你。要求用不超过次询问确定。
# 题解
考虑任意两个不相等的数,则必有。也就是说,两个数正反各询问一次,就可以确定较小那个数的值。
所以我们从和开始,每次确定小的数,保留大的数的位次,继续向后询问。经过次询问后,我们可以确定所有小于的数,那么此时的最大位次对应的数即为。
时间复杂度。
参考代码(C++)
#include <iostream>
#include <vector>
using namespace std;
class Solution {
vector<int> ans;
vector<vector<pair<int, int>>> adj;
int query(int i, int j) {
int k;
cout << "? " << i << " " << j << endl;
cin >> k;
return k;
}
public:
void solve() {
int n;
cin >> n;
if (n == 1) {
cout << "! 1" << endl;
return;
}
ans = vector<int>(n + 1);
int a = query(1, 2), b = query(2, 1);
int m;
if (a > b) {
m = 2;
ans[1] = a;
} else {
m = 1;
ans[2] = b;
}
for (int i = 3; i <= n; ++i) {
int a = query(m, i), b = query(i, m);
if (a > b) {
ans[m] = a;
m = i;
} else {
ans[i] = b;
}
}
ans[m] = n;
cout << "! ";
for (int i = 1; i <= n; ++i)
cout << ans[i] << " ";
cout << endl;
}
};
int main() {
Solution solution = Solution();
solution.solve();
}
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
# Problem D - Discrete Centrifugal Jumps (opens new window)
# 题目描述
给定一系列高度,规定可以从移动到(),当且仅当满足下列条件中的一种:
求从到的最少移动次数。
# 题解
不难发现,合法的移动只有:
- 是右边第一个不小于的
- 是右边第一个不大于的
- 是左边第一个不小于的
- 是左边第一个不大于的
注意一定包含在上面的情况中,不需要单独讨论。
因此跑四次单调栈获取上述信息后,进行BFS即可。
时间复杂度。
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
vector<set<int>> adj;
public:
void solve() {
int n;
read(n);
vector<int> h(n);
for (int i = 0; i < n; ++i)
read(h[i]);
adj = vector<set<int>>(n);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && h[i] <= h[st.top()]) {
adj[st.top()].insert(i);
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = 0; i < n; ++i) {
while (!st.empty() && h[i] >= h[st.top()]) {
adj[st.top()].insert(i);
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && h[i] <= h[st.top()]) {
adj[i].insert(st.top());
st.pop();
}
st.push(i);
}
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && h[i] >= h[st.top()]) {
adj[i].insert(st.top());
st.pop();
}
st.push(i);
}
queue<int> q;
q.push(0);
vector<int> dist(n, -1);
dist[0] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == n - 1) {
printf("%d", dist[u]);
return;
}
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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
# Problem E - Egor in the Republic of Dagestan (opens new window)
# 题目描述
有一个个节点条边的有向图。每条边有黑白两种颜色(黑色为,白色为)。现在要给每个节点染色,染色之后所有不同颜色的出边都失效。找出一种染色方案,使得到不连通,或最短距离尽可能大。
# 题解
逆向思考,贪心染色。
所有边都存在处。从开始进行BFS。对于当前访问到的节点,考虑边。如果当前已经被设为颜色,则不可能阻断这条边,将入队;否则,将设为的相反颜色,从而阻断这条边。这样的染色方法一定是最优的,因为后访问到的节点对应更长的距离,所以一定应该优先解决先访问到的节点。
如果最后无法访问到,则说明存在使得到不连通的染色方案;否则到的距离即为所要求的最大最短距离。染色方案在BFS过程中已经确定。没有访问到的点可以染成任意一种颜色。
参考代码(C++)
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}
class Solution {
public:
void solve() {
int n, m;
read(n), read(m);
vector<vector<pair<int, int>>> in(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, t;
read(u), read(v), read(t);
if (u == v)
continue;
t++;
in[v].emplace_back(u, t);
}
queue<pair<int, int>> q;
q.emplace(n, 0);
vector<int> close(n + 1);
vector<int> dist(n + 1);
vector<bool> vis(n + 1);
vis[n] = true;
while (!q.empty()) {
auto [v, d] = q.front();
dist[v] = d;
q.pop();
for (auto [u, t] : in[v]) {
if (vis[u])
continue;
if ((t == 1 && close[u] == 2) || (t == 2 && close[u] == 1)) {
vis[u] = true;
q.emplace(u, d + 1);
} else
close[u] = t;
}
}
if (!vis[1])
printf("-1\n");
else
printf("%d\n", dist[1]);
for (int i = 1; i <= n; ++i)
printf("%d", min(1, 2 - close[i]));
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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