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整除的數(shù)，其末尾分為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.若存在一個數(shù) K 能使所有數(shù)通過相減而相等页慷，則 k 必定是這個數(shù)列相鄰兩項不同的數(shù)的差值的因子憔足，這里可以使用這個數(shù)列的 最大值 和 最小值 的差值 即 K | (max - min)。
2.存在數(shù)列 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] 的正模數(shù)
}
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
解法：動態(tài)規(guī)劃 或 記憶化搜索
記憶化搜索：可知對于一個數(shù)列的每一位要么是紅，要么是黑郎哭，如果直接暴力搜索他匪，一共 2 ^ 40 種情況
?設 dfs(track, u, a, b, k) 為前 u - 1 個中，紅色數(shù) % A = a, 黑色數(shù) % B = b, 已經(jīng)選了 k 個紅色位數(shù)
?此時考慮第 u 位情況彰居，若最終 a = b = 0诚纸，且 1 < k < n則合法撰筷，記錄 abs(n - k - k) 最小的答案序列即可陈惰。
動態(tài)規(guī)劃：設 dp[n][a][b][k],為前 n - 1 位，紅色數(shù) % A = a, 黑色數(shù) % B = b, 已經(jīng)選了 k 個紅位數(shù)的情況
?有 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();
}
}
// 動態(tài)規(guī)劃
#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 開始的字符串毕籽，若其為有效字符串必然其 奇數(shù)位的圓括號數(shù)量 = 偶數(shù)為圓括號數(shù)量 且 奇數(shù)位方括號數(shù)量 = 偶數(shù)位方括號數(shù)量
則要使其成為有效括號抬闯，必然使其 奇數(shù)位圓括號的數(shù)量 = 偶數(shù)位圓括號數(shù)量。（此等式換為方括號也行）
這里用前綴和
時間復雜度 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 位关筒，偶數(shù)位上的圓括號數(shù)量溶握，pre[i][1] 為前 i 位，奇數(shù)位圓括號數(shù)量
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;
// 答案為使 奇數(shù)位圓括號數(shù)量 = 偶數(shù)位圓括號數(shù)量蒸播，即差值
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;
}
