链接：https://codeforces.com/contest/2009
一场难度完全不低于 \(div3\) 低的 \(div4\)。
A. Minimize!
算法：
数学。
思路：
\((c – a) + (b – c) = b – a\)。
关键代码：
void solve()
{
ll a, b;
cin >> a >> b;
cout << b - a << endl;
}B. osu!mania
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
int n;
cin >> n;
vector<string> s(n + 10);
for (int i = 0; i < n; ++i)
cin >> s[i];
for (int i = n - 1; ~i; --i)
{
for (int j = 0; j < 4; ++j)
{
if (s[i][j] == '#')
{
cout << j + 1 << ' ';
break;
}
}
}
cout << endl;
}C. The Legend of Freya the Frog
算法：
数学，模拟。
思路：
无。
关键代码：
void solve()
{
int x, y, k;
cin >> x >> y >> k;
ll cnt1 = (ll)ceil((double)x / k);
ll cnt2 = (ll)ceil((double)y / k);
ll ans = max(cnt1, cnt2) * 2;
if (cnt1 > cnt2)
--ans;
cout << ans << endl;
}D. Satyam and Counting
算法：
找规律，排序，二分。
思路：
题目要求一个字符串中不能包含 \(FFT\) 和 \(NTT\) 连续子串，考虑到两个连续子串中 \(T\) 都是在结尾，所以只需先把所以 \(T\) 输出了即可。
关键代码：
void solve()
{
int n;
cin >> n;
vector<vector<int>> v(2);
for (int i = 0; i < n; ++i)
{
int x, y;
cin >> x >> y;
v[y].push_back(x);
}
sort(all(v[0]));
sort(all(v[1]));
ll ans = 0;
for (auto pos : v[1])
{
int x1 = pos - 1, x2 = pos + 1;
auto it1 = lower_bound(all(v[0]), x1);
auto it2 = lower_bound(all(v[0]), x2);
if (it1 != v[0].end() && *it1 == x1 && it2 != v[0].end() && *it2 == x2)
++ans;
auto it3 = lower_bound(all(v[0]), pos);
if (it3 != v[0].end() && *it3 == pos)
ans += v[0].size() - 1;
}
for (auto pos : v[0])
{
int x1 = pos - 1, x2 = pos + 1;
auto it1 = lower_bound(all(v[1]), x1);
auto it2 = lower_bound(all(v[1]), x2);
if (it1 != v[1].end() && *it1 == x1 && it2 != v[1].end() && *it2 == x2)
++ans;
auto it3 = lower_bound(all(v[1]), pos);
if (it3 != v[1].end() && *it3 == pos)
ans += v[1].size() - 1;
}
cout << ans << endl;
}E. Klee’s SUPER DUPER LARGE Array!!!
算法：
二分。
思路：
无。
关键代码：
void solve()
{
ll n, k;
cin >> n >> k;
ll sum = n * (k + k + n - 1) / 2;
ll ans = LLONG_MAX;
ll l = 1, r = n;
while (l < r)
{
ll mid = l + r >> 1;
ll sum1 = mid * (k + k + mid - 1) / 2;
ll sum2 = sum - sum1;
ans = min(ans, abs(sum1 - sum2));
if (sum1 > sum2)
r = mid;
else if (sum1 < sum2)
l = mid + 1;
else
break;
}
cout << ans << endl;
}F. Firefly’s Queries
算法：
类容斥原理思想。
思路：
无。
关键代码：
void solve()
{
ll n, q;
cin >> n >> q;
vector<ll> a(n + 10);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<ll> sum(n + 10, 0);
for (int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + a[i];
auto get = [&](ll x) -> ll
{
return sum[x / n + min(x % n, n - x / n)] - sum[x / n] + sum[x % n - min(x % n, n - x / n)] + x / n * sum[n];
};
while (q--)
{
ll l, r;
cin >> l >> r;
cout << get(r) - get(l - 1) << endl;
}
}G1. Yunli’s Subarray Queries (easy version)
算法：
滑动窗口。
思路：
在本题中，由于每次询问的区间长度都是固定值 \(k\)，因此我们可以通过预处理所有长度为 \(k\) 的区间的最小修改次数，来实现在常数时间内回答每个查询。
为简化问题，注意到题目要求将某一段区间修改为公差为 1 的等差数列。我们可以将数组中的每个 \(a[i]\) 替换为 \(a[i]−i\)，这样目标就转化为了让一段区间内的所有元素都相等。因为等差为 \(1\) 的数列满足 \(a[i]−i=c\)，其中 \(c\) 为某个定值。
于是，问题就变成了：对于每个长度为 \(k\) 的区间，求其中出现次数最多的数的个数，答案即为将该区间变为等差数列所需的最小修改次数 \(k – \text{max_count}\)。
为高效计算所有滑动窗口的答案，可以使用滑动窗口配合以下两个数据结构：
map<int, int>用于维护当前窗口中每个数的出现次数；multiset<int>维护这些出现次数的集合，便于快速获取当前窗口内最大出现次数（即*s.rbegin()）。
滑动窗口从左到右遍历，窗口每右移一步，就将左端的元素移除，右端的新元素加入，并实时更新 map 和 multiset。每次移动后，记录当前窗口的最小修改次数，即 k - 当前最大出现次数。
处理完所有窗口后，对于每个查询，直接输出对应起点位置的预处理结果即可，时间复杂度为 \(\mathcal{O}(n \log k + q)\)。
关键代码：
void solve()
{
ll n, k, q;
cin >> n >> k >> q;
vector<int> a(n + 10);
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
a[i] = a[i] - i;
}
vector<int> ans(n + 10);
map<int, int> m;
multiset<int> s;
for (int i = 1; i <= k; ++i)
++m[a[i]];
for (auto [x, y] : m)
s.insert(y);
ans[1] = k - *s.rbegin();
int l = 1;
for (int i = k + 1; i <= n; ++i)
{
s.erase(s.find(m[a[l]]));
--m[a[l]];
s.insert(m[a[l]]);
++l;
int now = a[i];
if (m.count(now))
s.erase(s.find(m[now]));
++m[now];
s.insert(m[now]);
ans[l] = k - *s.rbegin();
}
while (q--)
{
int l, r;
cin >> l >> r;
cout << ans[l] << endl;
}
}G2. Yunli’s Subarray Queries (hard version)
还没补。
