「题解」2023 ICPC 济南区域赛
2025/9/5大约 4 分钟
「题解」2023 ICPC 济南区域赛
要打网络赛了……
神秘的周五上午与神秘 VP 之梦。
A. Many Many Heads
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s;
cin >> s;
int n = s.size();
if (n == 2) {
cout << "Yes\n";
return;
}
vector<int> a(n);
for (int i = 0; i < n; i++) {
if (s[i] == '(' or s[i] == ')')
a[i] = 1;
}
int l0 = -1, l1 = -1;
for (int i = 0; i < n; i++) {
if (a[i]) {
if (l0 != -1) {
if (i - l0 > 2) {
cout << "No\n";
return;
}
l0 = -1;
}
if (l1 == -1) {
l1 = i;
}
} else {
if (l0 == -1) {
l0 = i;
}
if (l1 != -1) {
if (i - l1 > 2) {
cout << "No\n";
return;
}
l1 = -1;
}
}
}
if (l0 != -1) {
if (n - l0 > 2) {
cout << "No\n";
return;
}
}
if (l1 != -1) {
if (n - l1 > 2) {
cout << "No\n";
return;
}
}
vector<int> c[2] = {};
for (int i = 1; i < n; i++) {
if (a[i] == a[i - 1]) {
c[a[i]].emplace_back(i);
}
}
if (c[0].size() + c[1].size() > 2) {
cout << "No\n";
return;
}
cout << "Yes\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}D. Largest Digit
#include <bits/stdc++.h>
using namespace std;
int n;
void solve() {
int a, b, c, d;
cin >> a >> b >> c >> d;
int x = a + c, y = b + d;
string s1 = to_string(x);
int maxn = 0;
for (auto i : s1) {
maxn = max(maxn, i - '0');
}
for (int i = x; i <= y; i++) {
string s2 = to_string(i);
for (auto j : s2) {
maxn = max(maxn, j - '0');
}
if (maxn == 9) {
cout << 9 << '\n';
return;
}
}
cout << maxn << '\n';
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}G. Gifts from Knowledge
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct DSU {
vector<int> f;
DSU(int n) : f(n) { iota(f.begin(), f.end(), 0); }
int find(int x) {
while (f[x] != x)
x = f[x] = f[f[x]];
return x;
}
void merge(int x, int y) {
x = find(x), y = find(y);
f[y] = x;
}
};
constexpr int modn = 1e9 + 7;
int p2(i64 b) {
i64 res = 1;
i64 a = 2;
while (b) {
if (b & 1) {
(res *= a) %= modn;
}
(a *= a) %= modn;
b >>= 1;
}
return res;
}
void solve() {
int r, c;
cin >> r >> c;
vector g(r, vector<char>(c));
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
cin >> g[i][j];
DSU dsu(2 * r);
for (int i = 0, j = c - 1; i <= j; i++, j--) {
bool ok = false;
vector<int> c0, c1;
for (int k = 0; k < r; k++) {
if (g[k][i] == '1')
c0.emplace_back(k);
if (g[k][j] == '1')
c1.emplace_back(k);
}
if (i == j) {
if (c0.size() > 1)
ok = true;
} else {
if (c0.size() + c1.size() > 2)
ok = true;
}
if (ok == true) {
cout << "0\n";
return;
}
if (c0.size() == 2) {
dsu.merge(c0.front(), c0.back() + r);
dsu.merge(c0.back(), c0.front() + r);
}
if (c1.size() == 2) {
dsu.merge(c1.front(), c1.back() + r);
dsu.merge(c1.back(), c1.front() + r);
}
if (c0.size() == 1 and c1.size() == 1) {
dsu.merge(c0.front(), c1.front());
dsu.merge(c0.front() + r, c1.front() + r);
}
}
for (int i = 0; i < r; i++) {
if (dsu.find(i) == dsu.find(i + r)) {
cout << "0\n";
return;
}
}
i64 cnt = 0;
for (int i = 0; i < 2 * r; i++) {
if (dsu.find(i) == i)
cnt++;
}
cnt /= 2;
cout << p2(cnt) << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}I. Strange Sorting
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
auto check = [&]() -> bool {
for (int i = 1; i <= n; i++) {
if (a[i] != i)
return true;
}
return false;
};
vector<pair<int, int>> vec;
while (check()) {
int l = 1, r = n;
for (int i = 1; i <= n; i++) {
if (a[i] == i) {
l++;
} else {
break;
}
}
for (int i = n; i >= 1; i--) {
if (a[i] == i) {
r--;
} else {
break;
}
}
for (int i = r; i >= l; i--) {
if (a[i] < a[l]) {
vec.emplace_back(l, i);
sort(a.begin() + l, a.begin() + i + 1);
break;
}
}
r = n;
for (int i = n; i >= 1; i--) {
if (a[i] == i) {
r--;
} else {
break;
}
}
for (int i = l; i <= r; i++) {
if (a[i] > a[r]) {
vec.emplace_back(i, r);
sort(a.begin() + i, a.begin() + r + 1);
break;
}
}
}
cout << vec.size() << "\n";
for (auto [x, y] : vec)
cout << x << " " << y << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}K. Rainbow Subarray
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr void debug(auto first, auto... args) {
std::print(std::cerr, "{}", first);
((std::print(std::cerr, " {}", args)), ...);
std::print(std::cerr, "\n");
}
struct Midder {
multiset<int> le, gt; // le: 小于等于中位数，gt: 大于等于中位数
i64 fle = 0, fgt = 0; // 分别记录le和gt中元素的和
void balance() {
// 保持平衡：le.size() == gt.size() 或 le.size() + 1 == gt.size()
while (gt.size() > le.size() + 1) {
// 从gt移动最小元素到le
auto it = gt.begin();
int val = *it;
le.insert(val);
fle += val;
gt.erase(it);
fgt -= val;
}
while (le.size() > gt.size()) {
// 从le移动最大元素到gt
auto it = prev(le.end());
int val = *it;
gt.insert(val);
fgt += val;
le.erase(it);
fle -= val;
}
}
void insert(int x) {
if (le.empty() && gt.empty()) {
gt.insert(x);
fgt += x;
} else {
int mid = *gt.begin(); // 当前中位数
if (x <= mid) {
le.insert(x);
fle += x;
} else {
gt.insert(x);
fgt += x;
}
}
balance();
}
void erase(int x) {
if (le.find(x) != le.end()) {
le.erase(le.find(x));
fle -= x;
} else if (gt.find(x) != gt.end()) {
gt.erase(gt.find(x));
fgt -= x;
}
balance();
}
int query() {
// 返回中位数
if (le.size() == gt.size()) {
// 偶数个元素，返回平均值（注意整数除法可能的问题）
return (*le.rbegin() + *gt.begin()) / 2;
} else {
// 奇数个元素，返回中间值
return *gt.begin();
}
}
size_t size() const { return le.size() + gt.size(); }
};
void solve() {
i64 n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i] -= i; // 预处理：a[i] = a[i] - i
}
Midder m;
int ans = 0;
for (int l = 0, r = 0; r < n; r++) {
m.insert(a[r]);
// 计算当前中位数和代价
while (l <= r) {
int mid = m.query();
i64 cost = (i64)mid * m.le.size() - m.fle + m.fgt - (i64)mid * m.gt.size();
if (cost <= k) {
break;
}
m.erase(a[l]);
l++;
}
ans = max(ans, (int)m.size());
}
cout << ans << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}