A. Alyona and a Square Jigsaw Puzzle
模拟即可
#include <bits/stdc++.h>
using i64 = long long;
void solve()
{
int n; std::cin >> n;
int cur = 0;
int ans = 0;
for(int i = 0, j = 1; i < n; i++)
{
int x; std::cin >> x;
cur += x;
while(cur > j * j) j += 2;
if(cur == j * j) ans++;
}
std::cout << ans << "\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t; std::cin >> t;
while(t--) solve();
return 0;
}
B. Replace Character
把出现次数最少的字母变成最多的即可
#include <bits/stdc++.h>
using i64 = long long;
void solve()
{
int n; std::cin >> n;
std::string s; std::cin >> s;
std::vector<int> cnt(26);
for(auto c : s) cnt[c - 'a']++;
auto t = s;
std::ranges::sort(s);
std::ranges::sort(s, [&](char x, char y) { return cnt[x - 'a'] > cnt[y - 'a']; });
for(auto &c : t)
{
if(c == s.back())
{
c = s[0];
break;
}
}
s = t;
std::cout << s << "\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t; std::cin >> t;
while(t--) solve();
return 0;
}
C. Swap Columns and Find a Path
第一行大就选第一行，第二行大就选第二行，再从剩下的格子里面选一个最大的用来转弯
#include <bits/stdc++.h>
using i64 = long long;
constexpr int INF = 1e9;
void solve()
{
int n; std::cin >> n;
std::vector a(2, std::vector<i64>(n));
for(int i = 0; i < n; i++) std::cin >> a[0][i];
for(int i = 0; i < n; i++) std::cin >> a[1][i];
i64 ans = 0, max = -INF;
for(int i = 0; i < n; i++)
{
if(a[0][i] > a[1][i]) ans += a[0][i];
else ans += a[1][i];
max = std::max(max, std::min(a[0][i], a[1][i]));
}
ans += max;
std::cout << ans << "\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t; std::cin >> t;
while(t--) solve();
return 0;
}
D. Move Back at a Cost
注意到每个数最多只会被加一次，因为如果存在一个数需要加两次，只可能是一个比它小的数在它之后加一，所以我们只需要让那个数先加一即可。由于要字典序最小，所以我们尽可能不要加数，我们可以维护一个栈和一个优先队列，维持栈内单调，弹出来的数都加一放进队列，然后再从队列放回栈里面，直到队列为空。
#include <bits/stdc++.h>
using i64 = long long;
void solve()
{
int n; std::cin >> n;
std::vector<int> a(n);
for(int i = 0; i < n; i++) std::cin >> a[i];
std::vector<int> x;
std::priority_queue<int, std::vector<int>, std::greater<>> y;
for(auto i : a)
{
if(x.empty() || i >= x.back()) x.emplace_back(i);
else
{
while(!x.empty() && i < x.back())
{
y.emplace(x.back() + 1);
x.pop_back();
}
x.emplace_back(i);
}
}
while(!y.empty())
{
int t = y.top(); y.pop();
while(!x.empty() && t < x.back())
{
y.emplace(x.back() + 1);
x.pop_back();
}
x.emplace_back(t);
}
for(int i = 0; i < n; i++) std::cout << x[i] << " \n"[i == n - 1];
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t; std::cin >> t;
while(t--) solve();
return 0;
}
E. Adventurers
两个log的做法
答案显然可以二分，考虑如何 \(check\)。首先我们可以把这些点按 \(x\) 坐标排序，然后从左往右扫，扫的过程中这些点会被分成两个部分，我们在这两个部分从下往上取第 \(mid\) 大的点，以 \(y\) 最大的那个点再横着分出上下两部分，这样就把区域分成了四个部分，最后再检查一下是不是四个部分都有 \(mid\) 个点即可。具体实现用了 \(pbds\) 的平衡树。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using i64 = long long;
constexpr int INF = 1e9;
void solve()
{
int n; std::cin >> n;
std::vector<int> x(n), y(n);
for(int i = 0; i < n; i++) std::cin >> x[i] >> y[i];
std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
std::ranges::sort(p, [&](int i, int j)
{
return x[i] < x[j] || (x[i] == x[j] && y[i] < y[j]);
});
std::array<int, 3> ans{};
auto check = [&](int m) -> bool
{
__gnu_pbds::tree<std::array<int, 3>, __gnu_pbds::null_type, std::less<std::array<int, 3>>,
__gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update> a, b;
for(auto i : p) b.insert({y[i], x[i], i});
for(int j = 0; j < p.size(); j++)
{
int i = p[j];
b.erase({y[i], x[i], i});
a.insert({y[i], x[i], i});
if(j + 1 < p.size() && x[p[j + 1]] == x[p[j]]) continue;
if(a.size() >= 2 * m && b.size() >= 2 * m)
{
auto tmp1 = *a.find_by_order(m - 1), tmp2 = *b.find_by_order(m - 1);
auto res = tmp1;
if(res[0] < tmp2[0]) res = tmp2;
res[0]++, res[1] = -INF;
int rk1 = a.order_of_key(res), rk2 = b.order_of_key(res);
if((int)a.size() - rk1 >= m && (int)b.size() - rk2 >= m)
{
ans = res;
ans[1] = x[i] + 1;
return true;
}
}
}
return false;
};
int lo = 0, hi = n / 4;
while(lo < hi)
{
int m = (lo + hi + 1) >> 1;
if(check(m)) lo = m;
else hi = m - 1;
}
std::cout << lo << "\n" << ans[1] << " " << ans[0] << "\n";
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t; std::cin >> t;
while(t--) solve();
return 0;
}