链接：https://codeforces.com/contest/2149
A. Be Positive
算法：
数学。
思路：
无。
关键代码：
void miyan()
{
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
ll cnt1 = ranges::count(a, -1);
ll cnt2 = ranges::count(a, 0);
cout << cnt2 + 2 * (cnt1 & 1) << endl;
}B. Unconventional Pairs
算法：
贪心，排序。
思路：
经典最小差值排序问题。
关键代码：
void miyan()
{
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
ranges::sort(a);
ll ans = INT_MIN;
for (int i = 0; i < n; i += 2)
ans = max(ans, 1ll * a[i + 1] - a[i]);
cout << ans << endl;
}C. MEX rose
算法：
贪心。
思路：
无。
关键代码：
void miyan()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &x : a)
cin >> x;
map<int, int> m;
for (auto x : a)
++m[x];
ll ans = 0;
ll cnt = 0;
for (int i = 0; i < k; ++i)
{
if (!m.count(i))
{
++ans;
++cnt;
}
}
if (m.count(k))
ans += max(0ll, m[k] - cnt);
cout << ans << endl;
}D. A and B
算法：
前后缀和。
思路：
经典前后缀优化问题。
关键代码：
void miyan()
{
ll n;
string s;
cin >> n >> s;
s = ' ' + s;
vector<ll> a, b;
a.reserve(n), b.reserve(n);
for (int i = 1; i <= n; ++i)
{
if (s[i] == 'a')
a.push_back(i);
else
b.push_back(i);
}
ll la = a.size(), lb = b.size();
vector<ll> prea(la + 2, 0), preb(lb + 2, 0), sufa(la + 2, 0), sufb(lb + 2, 0);
for (int i = 2; i <= la; ++i)
prea[i] = prea[i - 1] + (a[i - 1] - a[i - 2] - 1) * (i - 1);
for (int i = la - 1; i >= 1; --i)
sufa[i] = sufa[i + 1] + (a[i] - a[i - 1] - 1) * (la - i);
for (int i = 2; i <= lb; ++i)
preb[i] = preb[i - 1] + (b[i - 1] - b[i - 2] - 1) * (i - 1);
for (int i = lb - 1; i >= 1; --i)
sufb[i] = sufb[i + 1] + (b[i] - b[i - 1] - 1) * (lb - i);
ll ans = 1e18;
for (int i = 1; i <= la; ++i)
{
ll cnt = prea[i] + sufa[i];
ans = min(ans, cnt);
}
for (int i = 1; i <= lb; ++i)
{
ll cnt = preb[i] + sufb[i];
ans = min(ans, cnt);
}
cout << ans << endl;
}E. Hidden Knowledge of the Ancients
算法：
双指针。
思路：
维护两个滑动窗口：
- \([i, j1]\) 该窗口是区间内不同元素个数为 \(k – 1\) 的以 \(i\) 为左端点的最大右端点。
- \([i, j2]\) 该窗口是区间内不同元素个数为 \(k\) 的以 \(i\) 为左端点的最大右端点。
那么区间内不同元素个数恰好为 \(k\) 的区间为 \([j1 + 1, j2]\)。
满足区间长度在 \([l, r]\) 范围的以 \(i\) 为左端点的区间为 \([i + l – 1, i + r – 1]\)。
那么满足以上两个条件的区间就为 \([max(j1 + 1, i + l – 1), min(j2, i + r – 1)]\)。
区间个数就为 \(max(0, min(j2, i + r – 1) – max(j1 + 1, i + l – 1) + 1)\)。
关键代码：
void miyan()
{
int n, k, l, r;
cin >> n >> k >> l >> r;
vector<int> a(n + 2);
for (int i = 1; i <= n; ++i)
cin >> a[i];
ll ans = 0;
map<int, int> m1, m2;
ll cnt1 = 0, cnt2 = 0;
for (int i = 1, j1 = 0, j2 = 0; i <= n; ++i)
{
while (j1 < n && cnt1 < k)
{
if (m1[a[j1 + 1]])
++m1[a[++j1]];
else if (cnt1 + 1 < k)
{
++cnt1;
++m1[a[++j1]];
}
else
break;
}
while (j2 < n && cnt2 <= k)
{
if (m2[a[j2 + 1]])
++m2[a[++j2]];
else if (cnt2 < k)
{
++cnt2;
++m2[a[++j2]];
}
else
break;
}
ans += max(0, min(j2, i + r - 1) - max(j1 + 1, i + l - 1) + 1);
if (--m1[a[i]] == 0)
--cnt1;
if (--m2[a[i]] == 0)
--cnt2;
}
cout << ans << endl;
}F. Nezuko in the Clearing
算法：
二分答案。
思路：
考虑休息：
- 如果只能休息一次，最优策略是在中间休息，尽可能的将移动分为两段，以最小化消耗。
- 如果可以休息两次，最优策略是将移动分为均匀的三段。
- 那么对应休息 \(k\) 次，最优策略是将移动分为 \(k + 1\) 段，平均每段长度为 \(d / (k + 1)\)。
总之就是平均。
在 \(d\) 除以 \(k + 1\) 时可能会有余数，既 \(d % (k + 1)\)，那么就会有 \(d % (k + 1)\) 段走 \(d / (k + 1) + 1\) 步，\(k + 1 – d % (k + 1)\) 段走 \(d / (k + 1)\) 步。
可以发现当 \(k\) 足够大时，必然可以走到终点，比如当 \(k = d\) 时，每走一步都休息，必然是可以到终点的，那么当 \(k\) 减小时，回合数也会减小，满足单调性，二分答案即可，二分休息几次。
关键代码：
void miyan()
{
ll h, d;
cin >> h >> d;
auto check = [&](ll k) -> bool
{
ll len = d / (k + 1);
ll m = d % (k + 1);
ll sum = len * (len + 1) / 2 * (k + 1);
sum += m * (len + 1);
return sum < h + k;
};
ll l = 0, r = 1e18;
while (l < r)
{
ll mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
cout << l + d << endl;
}G. Buratsuta 3
还没补。
