链接：https://codeforces.com/contest/2128
A. Recycling Center
算法：
贪心、排序。
思路：
直接从最小的开始销毁。
关键代码：
void solve()
{
ll n, c;
cin >> n >> c;
vector<ll> a(n);
for (auto &x : a)
cin >> x;
ranges::sort(a, greater<>());
ll ans = n;
for (int i = 0; i < n; ++i)
{
if (a[i] <= c)
{
--ans;
c /= 2;
}
}
cout << ans << endl;
}B. Deque Process
算法：
贪心、构造。
思路：
一边取一个。
关键代码：
void solve()
{
int n;
cin >> n;
vector<int> p(n + 1);
for (auto &x : p | views::drop(1))
cin >> x;
string ans;
int l = 1, r = n;
bool flag = 0;
while (l < r)
{
if (flag)
{
if (p[l] >= p[r])
{
ans += 'L';
++l;
}
else
{
ans += 'R';
--r;
}
flag = !flag;
}
else
{
if (p[l] <= p[r])
{
ans += 'L';
++l;
}
else
{
ans += 'R';
--r;
}
flag = !flag;
}
}
ans += 'L';
cout << ans << endl;
}C. Leftmost Below
算法：
贪心，数学。
思路：
可以发现构造第 \(i\) 个元素时，前 \(i – 1\) 个元素必然构造出来了。
定义 \(minn\) 为前 \(i – 1\) 个元素最小值。
当前构造 \(a[i]\) 你想让前面的元素都加不到值，只给 \(a[i]\) 加，最多加两次
第一次加 \(x\) 可选范围为 \([1, minn – 1]\)，第二次加 \(x\) 只能选 \(minn\)
所以每个元素最大为 \(minn * 2 – 1\), 只要大于这个必然构造不出
关键代码：
void solve()
{
int n;
cin >> n;
vector<ll> b(n + 1);
for (auto &x : b | views::drop(1))
cin >> x;
ll minn = INT_MAX;
for (int i = 1; i <= n; ++i)
{
if (b[i] > minn + minn - 1)
{
cout << "NO" << endl;
return;
}
minn = min(minn, b[i]);
}
cout << "YES" << endl;
}D. Sum of LDS
算法：
\(dp\)、组合数学、贪心。
思路：
定义 \(dp[i]\) 为所有以 \(i\) 结尾的子数组 \(LDS\) 长度之和，那么就答案为：\(∑dp[i]\)
由 \(max(p_i, p_i + 1) > p_i + 2\) 可知：
整个数组几乎是完全递减的，可能会有一些位置递增一下，但不会连续递增两次，既 \(p_i < p_i + 1\) 且 \(p_i + 1 < p_i + 2\)，这样是不满足题目给出的条件的。
所以一个子数组的 \(LDS\) = 子数组长度 – 子数组上升的个数。
每次状态转移考虑把所有以 \(i – 1\) 结尾的子数组延长一个元素到 \(i\)
- \(p_i – 1 > p_i:\)
- 前面每个子数组长度都可 \(+1\)，以 \(i – 1\) 结尾的子数组有 \(i – 1\) 个，再加上 \([i, i]\)，加到一起就是:\(dp[i] = dp[i – 1] + i\)
- \(p_i – 1 < p_i:\)
- 由于递增了，需要抛弃 \(p[i]\), 所以前面所有的子数组长度都不变，只会新增 \([i, i]\)，所以 \(dp[i] = dp[i – 1] + 1\)
关键代码：
void solve()
{
int n;
cin >> n;
vector<ll> p(n + 1);
for (auto &x : p | views::drop(1))
cin >> x;
ll ans = 1;
vector<ll> dp(n + 1);
dp[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (p[i - 1] > p[i])
dp[i] = dp[i - 1] + i;
else
dp[i] = dp[i - 1] + 1;
ans += dp[i];
}
cout << ans << endl;
}E1. Submedians (Easy Version)
算法：
前缀和、二分。
思路：
判断一个元素可不可以当作数组中某个子数组的中位数：
通常转换成 \(+-1\) 前缀和，既：如果 \(a[i] >= x\) 就令 \(a[i] = 1\), 反之为 \(-1\)。
此时只需一个子数组的和 \(>= 0\)，这个数字就为数组某个子数组的中位数。
证明：
当 \(n\) 为偶数时，需要 \(n / 2\) 的元素大于等于 \(x, [latex]n – n / 2\) 的元素小于 \(x\)，如果一段区间和大于等于\(0\)，既:
\(pre[r] – pre[l – 1] \geq 0 \;\;\Rightarrow\;\; pre[r] \geq pre[l – 1]\)。
当 \(n\) 为奇数时，需要 \(n / 2 + 1\) 的元素大于等于 \(x\), \(n – n / 2 – 1\) 的元素小于 \(x\)，如果一段区间和大于等于\(1\)，既:
\(pre[r] – pre[l – 1] >= 1 \Rightarrow pre[r] >= pre[l – 1] + 1\)
但是一个长度为奇数的子数组，其和也必然为奇数，不会出现偶数情况，所以判断 \(>= 0\) 即可。
由于中位数必然满足单调性，且满足条件最大的可能也会小于等于数组长度，所以只需在 \([1, n]\) 之间二分即可。
\(check\)函数：
根据当前中位数，将数组转换成 \(+-1\) 前缀和。
由于规定区间长度最少为 k, 那么我们就初始令 \(r = k, l = 0\)，每次循环让 \(r\) 递增，此时 \(l\) 的取值范围为\([0, r – k]\)，每次我们都贪心地选择 \([0, r – k]\) 区间内的最小前缀，这样如果 \(pre[r] >= pre[l]\)，就说明 \(x\) 可以当作数组某个子数组的中位数。
关键代码：
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
ll ansl, ansr;
auto check = [&](ll val)
{
vector<int> pre(n + 1, 0);
for (int i = 1; i <= n; ++i)
pre[i] = pre[i - 1] + (a[i] >= val ? 1 : -1);
for (int i = k, j = 0; i <= n; ++i)
{
if (pre[j] > pre[i - k])
j = i - k;
if (pre[i] >= pre[j])
{
ansl = j + 1;
ansr = i;
return 1;
}
}
return 0;
};
int l = 1, r = n;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
check(l);
cout << l << ' ' << ansl << ' ' << ansr << endl;
}E2. Submedians (Hard Version)
还没补。
