Codeforces Round 1014 (Div.2) 题解

A

题意

给定一个数组,可以选择两个数 \(x,y\),给他们分别加上任意整数 \(d (d\ge 0)\),求最大可能的 \(\gcd(x+d,y+d)\)

题解

gcd 的一个性质是,\(\gcd(a,b)\mid (ax+by)\),且 \(\gcd(x,y) = \gcd(x,y-x)\)。因为如果 \(a\mid b, a\mid c\),有 \(a\mid (nb + mc)\),因此 \(\gcd(x+d,y+d) = \gcd(x+d, y -x)\),由于差值固定为 \(k = y - x\),我们需要最大化 \(\gcd(x+d, k)\),选择 \(d\) 使得 \(x + d\)\(k\) 的倍数,那么 \(\gcd(x+d, k) = k\),即差值不会超过 \(k\),因此答案就是 \(y - x\)。取最大值减去最小值即可。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a.begin() + 1, a.end());
int x = a[1], y = a[n];
cout << y - x << "\n";
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}

B

题意

给定两个 01 串 \(a,b\),可以将 \(a_{i+1}\)\(b_i\) 交换,或者 \(b_{i+1}\)\(a_i\) 交换,求能否把 \(a\)​ 变成全是 0 。

题解

观察到 \(b\) 的奇数位的数字一定能转移到 \(a\) 的偶数位,判断 \(a,b\) 的奇偶性不同的位置 0 之和是否满足要求即可。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
int n;
cin >> n;
string s, t;
cin >> s >> t;
s = " " + s, t = " " + t;
int cnt0 = 0, cnt1 = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == '1') {
if (i & 1) {
cnt1++;
} else {
cnt0++;
}
}
}
for (int i = 1; i <= n; i++) {
if (t[i] == '0') {
if (i & 1) {
cnt0--;
} else {
cnt1--;
}
}
}
if (cnt1 <= 0 && cnt0 <= 0) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}

C

题意

给定一个数组,进行任意次操作:选择两个元素,如果他们的和为奇数,就可以让一个数减一,另一个数加一,求操作后数组中的最大元素。

题解

注意到一旦两个数和为奇数(奇 + 偶),那么操作后仍然满足条件,因此 \(a,b\) 最终可以变为 \(a+b, 0\)\(a+b-1, 1\)。由于奇数加偶数还是奇数,所以所有偶数都能与奇数合并,再考虑奇数怎么处理:奇数可以跟偶数合并后,自身保留 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
46
47
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
int n;
cin >> n;
vector<int> odd, even;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x % 2) {
odd.push_back(x);
} else {
even.push_back(x);
}
}
if (odd.empty()) {
cout << *max_element(even.begin(), even.end()) << "\n";
return;
}
if (even.empty()) {
cout << *max_element(odd.begin(), odd.end()) << "\n";
return;
}
sort(odd.begin(), odd.end(), greater());
sort(even.begin(), even.end(), greater());
i64 ans = accumulate(odd.begin(), odd.end(), 0ll) - odd.size() + 1;
ans += accumulate(even.begin(), even.end(), 0ll);
// ans += accumulate(odd.begin)
cout << ans << "\n";
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}

D

题意

给定一个长度为 \(n\) 的字符串 \(s\),只含有“L”,“I”,“T”。你可以选择一个位置 \(i\),满足 \(s_i \ne s_{i+1}\),插入另一个与两个位置都不相同的字符,最终使得在最多 \(2n\) 次操作中,每个字符的出现次数相等,给出操作次数和操作位置。不可能的话输出 -1。

题解

注意到所有字符都相同的话一定不能进行操作,输出-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
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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
int n;
cin >> n;
string s;
cin >> s;
s = " " + s;
if (count(s.begin() + 1, s.end(), s[1]) == n) {
cout << -1 << '\n';
return;
}
map<char, int> cnt;
for (int i = 1; i <= n; i++) {
cnt[s[i]]++;
}
string t = "TIL";
vector<int> ans;
while (cnt['T'] != cnt['I'] || cnt['T'] != cnt['L'] ||
cnt['I'] != cnt['L']) {
vector<pair<int, char>> a;
for (int i = 0; i < 3; i++) {
a.push_back({cnt[t[i]], t[i]});
}
sort(a.begin(), a.end());
int pos[] = {-1, -1, -1};
for (int i = 1; i < n; i++) {
if (s[i] != s[i + 1]) {
for (int j = 0; j < 2; j++) {
char ch = a[j].second;
if (ch != s[i] && ch != s[i + 1]) {
pos[j] = i;
}
}
}
}
if (pos[0] != -1) {
s.insert(pos[0] + 1, 1, a[0].second);
ans.push_back(pos[0]);
cnt[a[0].second]++;
} else {
s.insert(pos[1] + 1, 1, a[1].second);
ans.push_back(pos[1]);
cnt[a[1].second]++;
}
// cerr << "s = " << s << endl;
n++;
}
cout << ans.size() << "\n";
for (auto x : ans) {
cout << x << "\n";
}
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}

数组处理:

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
int n;
cin >> n;
string s;
cin >> s;
s = " " + s;
if (count(s.begin() + 1, s.end(), s[1]) == n) {
cout << -1 << "\n";
return;
}
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
a[i] = s[i] == 'T' ? 0 : (s[i] == 'L' ? 1 : 2);
}
int cnt[3]{};
for (int i = 1; i <= n; i++) {
cnt[a[i]]++;
}
vector<int> ans;
while (cnt[0] != cnt[1] || cnt[0] != cnt[2] || cnt[1] != cnt[2]) {
vector<array<int, 2>> p;
for (int i = 0; i < 3; i++) {
p.push_back({cnt[i], i});
}
sort(p.begin(), p.end());
int pos[3] = {-1, -1, -1};
for (int i = 1; i < n; i++) {
if (a[i] != a[i + 1]) {
pos[3 - a[i] - a[i + 1]] = i;
}
}
for (int j = 0; j < 2; j++) {
auto [_, x] = p[j];
if (pos[x] != -1) {
auto insert = [&](int pos, int x) {
vector<int> b(a.begin(), a.begin() + pos + 1);
b.push_back(x);
b.insert(b.end(), a.begin() + pos + 1, a.end());
a = b;
};
insert(pos[x], x);
ans.push_back(pos[x]);
cnt[x]++;
n++;
break;
}
}
}
cout << ans.size() << "\n";
for (auto x : ans) {
cout << x << "\n";
}
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}

E

题意

给定一个 \(n\times m\) 的矩阵,选定 \(k\) 个格子具有初始颜色,然后你可以任意给剩下格子涂色,求相邻不同色格子对数为偶数的总方案数,模 \(10^9 + 7\)

题解

注意一个点在顶点或是中间时,由于它周围有偶数个顶点,改变它自己的颜色并不会改变它与周围四个(或两个)格子形成对数的奇偶性(本来是 1 + 3的话,反转后变成 3 + 1,其他同理),因此我们只需要考虑在边上的点,只要保证了边上的点能形成偶数对,其他点可以任意取。

不妨假设初始都是白色,再考虑边上的点,如果边上所有格子都被涂色了,那么如果被涂成黑色的格子为偶数个的话,就一定可行,因为一个黑色贡献奇数个数量,答案为 \(2^{n+m-k}\),否则就不行,答案为 0 。

否则,边上会有至少一个格子空出来未涂色,如果边上黑色格子数目是奇数,这个格子就必须涂黑,否则必须涂白,无论怎样,有一个格子的颜色是确定的,总数量为 \(2^{n+m-k-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
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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template <int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(i64 x) : x{norm(x % getMod())} {}

static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) { Mod = Mod_; }
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const { return x; }
explicit constexpr operator int() const { return x; }
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template <>
int MInt<0>::Mod = 998244353;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;
using Z = MInt<P>; // 静态模数,题目给定模数
using D = MInt<0>; // 动态模数,可以 D::setMod(x) 改变

void solve() {
i64 n, m, k;
cin >> n >> m >> k;
int cnt = 0, sum = 0;
for (int i = 1; i <= k; i++) {
int x, y, v;
cin >> x >> y >> v;
if ((x == 1) ^ (x == n) ^ (y == 1) ^ (y == m)) {
cnt++, sum += v;
}
}
if (cnt == (n + m - 4) * 2) {
if (sum % 2 == 0) {
cout << power(Z(2), n * m - k) << "\n";
} else {
cout << 0 << "\n";
}
} else {
cout << power(Z(2), n * m - k - 1) << "\n";
}
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}