Editorial for Codeforces Round #748 (Div.3)
1593A - Elections
解法：模拟
**时间复杂度 O(1), 空间复杂度 O(1)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 4E5 + 5;
void solve() {
int a, b, c;
int mx = 0;
cin >> a >> b >> c;
mx = max(max(a, b), c);
int f = (mx == a) + (mx == b) + (mx == c);
if (f > 1) {
mx += 1;
cout << mx - a << " " << mx - b << " " << mx - c << endl;
}else {
if (mx == a) {
cout << 0 << " ";
}else cout << mx - a + 1 << " ";
if (mx == b) {
cout << 0 << " ";
} else cout << mx - b + 1 << " ";
if (mx == c) {
cout << 0 << endl;
}else cout << mx - c + 1 << endl;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t --) {
solve();
}
return 0;
}
1593B - Make it Divisible by 25
解法：能够被25整除的数，其末尾分为00，25，50，75四种情况。分别考虑这四种情况，从后向前寻找对应字符，减去寻找过程中的无用字符即为答案，取min即可。
时间复杂度 O(N)，空间复杂度 O(N)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 4E5 + 5;
void solve() {
string s;
cin >> s;
int ret = 20;
int d = 0;
int n = s.size();
for (int i = s.size() - 1; i >= 0; -- i) {
if (s[i] != '0' && s[i] != '5') continue;
for (int j = i - 1; j >= 0; -- j) {
if (s[i] == '0') {
if (s[j] == '0' || s[j] == '5') {
ret = min(ret, i - j - 1 + n - i - 1);
break;
}
}
else {
if (s[j] == '2' || s[j] == '7') {
ret = min(ret, i - j - 1 + n - i - 1);
break;
}
}
}
}
cout << ret << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t --) {
solve();
}
return 0;
}
1593C - Save More Mice
解法：模拟 & 贪心，让离洞最近的老鼠先入洞
时间复杂度 O(N * log N)，空间复杂度 O(N)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 4E5 + 5;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a;
for (int i = 0; i < k; ++ i) {
int t;
cin >> t;
a.push_back(t);
}
sort(a.begin(), a.end(), [](int& x, int& y) {
return x > y;
});
int ret = 0;
int c = 0;
for (int i = 0; i < a.size(); ++ i) {
if (c >= a[i]) break;
if (a[i] == n)
++ ret;
else {
c += n - a[i];
++ ret;
}
}
cout << ret << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t --) {
solve();
}
return 0;
}
1593D1 - All are Same
解法：
1.若存在一个数 K 能使所有数通过相减而相等，则 k 必定是这个数列相邻两项不同的数的差值的因子，这里可以使用这个数列的 最大值 和 最小值 的差值 即 K | (max - min)。
2.存在数列 A1 A2 A3 ... An ,其差值为 A12 A23 ... A(n - 1)(n), 则 K 可表示为 K = gcd{A12, A23, ..., A(n - 1)(n)};
两种方法本质相同
第一种：时间复杂度 O(N * )，空间复杂度 O(N)
第二种：时间复杂度 O(N * log N), 空间复杂度 O(N)
// 第一种
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
void solve() {
int n;
cin >> n;
vector<int> a;
for (int i = 0; i < n; ++ i) {
int t;
cin >> t;
a.push_back(t);
}
sort(a.begin(), a.end());
vector<int> divs; // 记录 d 的所有因子
int d = a[n - 1] - a[0];
for (int i = 1; i * i <= d; ++ i) {
if (d % i == 0) {
divs.push_back(i);
if (i * i != d) {
divs.push_back(d / i);
}
}
}
int ret = -1;
for (int& x : divs) {
unordered_map<int, int> cnt;
for (int i = 0; i < n; ++ i) {
cnt[(a[i] % x + x) % x] ++; // 此操作为取 a[i] 的正模数
}
for (auto& p : cnt) {
if (p.second == n) ret = max(ret, x);
}
}
cout << ret << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
// 第二种
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
void solve() {
int n;
cin >> n;
vector<int> a;
for (int i = 0; i < n; ++ i) {
int t;
cin >> t;
a.push_back(t);
}
sort(a.begin(), a.end());
int d = 0;
for (int i = 1; i < n; ++ i) {
int x = a[i] - a[i - 1];
d = __gcd(d, x);
}
if (d) cout << d << endl;
else cout << -1 << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t -- ) {
solve();
}
return 0;
}
1593D2 - Half of Same
**解法：参照D1 题第一种方法，枚举一个可行方案 最大值 和 最小值 **
**时间复杂度 O(N * N * )，空间复杂度 O(N) **
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int solve(int i, int j, vector<int>& a) {
int d = a[j] - a[i];
int n = a.size();
vector<int> divs;
for (int i = 1; i * i <= d; ++ i) {
if (d % i == 0) {
divs.push_back(i);
if (i * i != d) {
divs.push_back(d / i);
}
}
}
int ret = -1;
for (int& x : divs) {
unordered_map<int, int> cnt;
for (int i = 0; i < n; ++ i) {
cnt[(a[i] % x + x) % x] ++;
}
for (auto& p : cnt) {
if (2 * p.second >= n) ret = max(ret, x);
}
}
return ret;
}
void solve() {
int n;
cin >> n;
vector<int> a;
unordered_map<int, int> cnt;
for (int i = 0; i < n; ++ i) {
int t;
cin >> t;
a.push_back(t);
cnt[t] ++;
}
sort(a.begin(), a.end());
for (int& x : a) {
if (cnt[x] >= n / 2) {
cout << -1 << endl;
return;
}
}
int ans = -1;
// 枚举可行方案的 最大值 和 最小值
// i 为最小值下标， j 为最大值下标
for (int i = 0; i <= n / 2; ++ i) {
for (int j = i + 1; j < n; ++ j) {
ans = max(ans, solve(i, j, a));
}
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t --) {
solve();
}
return 0;
}
1593E - Gardener and Tree
解法：建图后，TOP 序处理
时间复杂度 O(N)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1e6 + 5;
int h[N], e[N], ne[N], d[N], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int q[N];
void solve() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++ i) {
h[i] = -1;
}
for (int i = 1; i <= n; ++ i) {
d[i] = 0;
}
idx = 0;
for (int i = 0; i < n - 1; ++ i) {
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
d[a] ++;
d[b] ++;
}
int hh = 0, tt = -1;
for (int i = 1; i <= n; ++ i) {
if (d[i] == 1) {
q[++ tt] = i;
-- d[i];
}
}
int cnt = 0;
while (hh <= tt) {
int sz = tt - hh + 1;
for (int i = 0; i < sz; ++ i) {
int t = q[hh ++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] == 0) continue;
if (-- d[j] == 1) {
q[++ tt] = j;
}
}
}
if (++ cnt == k) break;
}
int ret = tt - hh + 1;
for (int i = 1; i <= n; ++ i) {
if (d[i] > 1) {
++ ret;
// cout << i << endl;
}
}
cout << ret << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t --) {
solve();
}
return 0;
}
1593F - Red-Black Number
解法：动态规划 或 记忆化搜索
记忆化搜索：可知对于一个数列的每一位要么是红，要么是黑，如果直接暴力搜索，一共 2 ^ 40 种情况
设 dfs(track, u, a, b, k) 为前 u - 1 个中，红色数 % A = a, 黑色数 % B = b, 已经选了 k 个红色位数
此时考虑第 u 位情况，若最终 a = b = 0，且 1 < k < n则合法，记录 abs(n - k - k) 最小的答案序列即可。
动态规划：设 dp[n][a][b][k],为前 n - 1 位，红色数 % A = a, 黑色数 % B = b, 已经选了 k 个红位数的情况
有 dp[n + 1][(a * 10 + s[n] - '0') % A][b][k + 1] = dp[n][a][b][k] | ((long long)1 << n);
dp[n + 1][a][(b * 10 + s[n] - '0') % B][k] = dp[n][a][b][k];
时间复杂度 O(N * A * B * N), 空间复杂度 O(N ^ 4)
// 记忆化搜索
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 100;
string s, ret;
int A, B;
int tmp;
bool vis[N][N][N][N];
bool dfs(string& track, int u, int a, int b, int k) {
if (track.size() == s.size()) {
if (a != 0 || b != 0 || k == 0 || k >= (int)s.size()) return false;
if (abs((int)s.size() - k - k) < tmp) {
ret = track;
tmp = abs((int)s.size() - k - k);
}
return true;
}
if (vis[u][a][b][k]) return false;
vis[u][a][b][k] = 1;
track += "R";
bool flag = dfs(track, u + 1, (a * 10 + (s[u] - '0')) % A, b, k + 1);
track.pop_back();
track += "B";
flag |= dfs(track, u + 1, a, (b * 10 + (s[u] - '0')) % B, k);
track.pop_back();
return flag;
}
void solve() {
memset(vis, 0, sizeof vis);
tmp = 1e9;
int n;
cin >> n >> A >> B;
cin >> s;
string u;
bool flag = dfs(u, 0, 0, 0, 0);
if (flag) cout << ret << endl;
else cout << -1 << endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t --) {
solve();
}
}
// 动态规划
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 50;
long long dp[N][N][N][N];
void solve() {
// dp[n][a][b][k]
string s;
int n, A, B;
cin >> n >> A >> B >> s;
memset(dp, -1, sizeof dp);
dp[0][0][0][0] = 0;
for (int i = 0; i < n; ++ i) {
for (int k = 0; k < n; ++ k) {
for (int a = 0; a < A; ++ a) {
for (int b = 0; b < B; ++ b){
if (dp[i][a][b][k] != -1) {
dp[i + 1][(a * 10 + (s[i] - '0')) % A][b][k + 1] = dp[i][a][b][k] | (1ll << i);
dp[i + 1][a][(b * 10 + (s[i] - '0')) % B][k] = dp[i][a][b][k];
}
}
}
}
}
int mi = 1e9;
long long msk;
for (int k = 1; k < n; ++ k) {
if (dp[n][0][0][k] != -1 && abs(n - k - k) < abs(n - mi - mi)) {
mi = k;
msk = dp[n][0][0][k];
}
}
if (mi == 1e9) cout << -1 << endl;
else {
string ret(n, 'B');
for (int i = 0; i < n; ++ i) {
if (msk >> i & 1) ret[i] = 'R';
}
cout << ret << endl;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t --) {
solve();
}
}
1593G - Changing Brackets
解法：
已知：
1.同一类型的括号正反互转开销为 0
2.对于一个下标从 1 开始的字符串，若其为有效字符串必然其 奇数位的圆括号数量 = 偶数为圆括号数量 且 奇数位方括号数量 = 偶数位方括号数量
则要使其成为有效括号，必然使其 奇数位圆括号的数量 = 偶数位圆括号数量。（此等式换为方括号也行）
这里用前缀和
时间复杂度 O(N), 空间复杂度 O(N)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1E6 + 5;
int pre[N][2];
// pre[i][0] 为第前 i 位，偶数位上的圆括号数量，pre[i][1] 为前 i 位，奇数位圆括号数量
void solve() {
string s;a
cin >> s;
int n = s.size();
int q;
cin >> q;
for (int i = 1; i <= n; ++ i) {
pre[i][0] = pre[i - 1][0];
pre[i][1] = pre[i - 1][1];
if (s[i - 1] == '(' || s[i - 1] == ')') {
pre[i][i % 2] ++;
}
}
while (q --) {
int a, b;
cin >> a >> b;
// 答案为使 奇数位圆括号数量 = 偶数位圆括号数量，即差值
cout << abs((pre[b][0] - pre[a - 1][0]) - (pre[b][1] - pre[a - 1][1])) << endl;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t --) {
solve();
}
return 0;
}
