A. Recycling Center
题意：给你一个数组\(a\)，和一个数\(c\)，每次选一个数，如果这个数小于等于\(c\)没有代价，否则有\(1\)的代价，没选一个数其它数乘二，求最小代价。
\(n\)很小，考虑倒着来，把所有数都乘上\(2^{n-1}\)，初始代价为\(n\)，如果有小于等于\(c\)的选最大的，然后代价减一，在把所有数除二，这样模拟\(n\)次就行了。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, c;std::cin >> n >> c;std::vector<i64> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];a[i] *= 1 << (n - 1);}std::ranges::sort(a);int ans = n;for (int i = 0; i < n; ++ i) {int k = -1;for (int j = 0; j < n; ++ j) {if (a[j] != -1 && a[j] <= c) {if (k == - 1 || a[k] < a[j]) {k = j;}}}if (k != -1) {-- ans;a[k] = -1;}for (int j = 0; j < n; ++ j) {if (a[j] != -1) {a[j] /= 2;}}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
B. Deque Process
题意：一个排列是好的，那么它没有长度大于等于\(5\)的连续子序列递减或递增。给你一个排列，每次从左拿数或者从右拿数，使得最终得到一个好的排列。
第奇数次拿大的，偶数次拿小的。
我也不会证明，模拟一下发现没两三轮就和从递减变成递增或者从递增变成递减。
点击查看代码
#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::string s;int l = 0, r = n - 1;int k = 0;while (l <= r) {if (k & 1) {if (a[l] > a[r]) {s += "L";++ l;} else {s += "R";-- r;}} else {if (a[l] < a[r]) {s += "L";++ l;} else {s += "R";-- r;}}++ k;}std::cout << s << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
C. Leftmost Below
题意：给你一个全\(0\)数组\(a\)，每次选择一个大于\(min(a)\)的数\(x\)，然后把小于\(x\)的最小位置加上\(x\)。求\(a\)能不能变成\(b\)。
除了\(b_i = 1\)的位置，如果我们想让\(a_i = b_i\)，那么\([1, i - 1]\)都应该满足了，则我们只能操作\(x\in [1, min_{i-1}\)]，其中\(min_{i-1}\)为\([1, i -1]\)的最小值。那么最多使得\(a_i\)变成\(min_{i-1} + min_{i-1} - 1\)。如果\(a_i \geq 2\times min_{i-1}\)无解。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> b(n);for (int i = 0; i < n; ++ i) {std::cin >> b[i];}for (int i = 0, min = 1e9; i < n; ++ i) {if (min + min - 1 < b[i]) {std::cout << "NO\n";return;}min = std::min(min, b[i]);}std::cout << "YES\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
D. Sum of LDS
题意：一个排列，满足\(max(p_i, p_{i+1}) > p_{i+2}\)。求所有子数组的最长递减子序列。
直接算肯定不行，我们只能观察这个给出的性质。
我们发现最长上升连续子序列长度最多为\(2\)，设\(p_i < p_{i+1}\)，那么\(p_{i+2} < \max(p_i, p_{i+1})\)，无法继续递增。
继续观察，发现除了这些递增子序列的位置，其它位置从左到右整体就是递减的。
每个子区间如果出现一个\(p_i < p_{i+1}\)，那么最长递减子序列长度减少\(1\)。如果\(p_i < p_{i+1}\)，那么有\(p_{i+2} < \max(p_i, p_{i+1}) < p_{i-1}\)。
则我们考虑减去这些\(p_i < p_{i+1}\)的贡献，一开始长度为\(k\)的子数组最长递减子序列长度就是\(k\)，那么有\(\sum_{k=1}^{n} k\times(n-k+1) = \frac{n(n+1)(n+2)}{6}\)，这个也可以循环算。
然后对于每个\(p_i < p_{i+1}\)，包含它们的区间有\(i\times(n-i)\)个。减去即可。
点击查看代码
#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];}i64 ans = 1LL * n * (n + 1) * (n + 2) / 6;for (int i = 0; i + 1 < n; ++ i) {if (a[i] < a[i + 1]) {ans -= (i64)(i + 1) * (n - i - 1);}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
E1. Submedians (Easy Version)
题意：给你一个数组。求一个最大的\(x\)，使得有一个长度大于等于\(k\)的子区间的中位数是\(x\)。
这个题貌似太典了，印象中光\(cf\)就出过好几次吧。
如果一个数小于等于数组里的中位数，那么把小于它的设置为\(-1\)，大于等于它的设置为\(1\)，那么如果有一个区间的和大于等于\(0\)则满足条件。
那么考虑二分中位数，求有没有区间的中位数大于等于\(mid\)。这里要求长度大于等于\(k\)，那么就只记录比当前位置小\(k\)的位置的前缀和就行了。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;std::cin >> n >> k;std::vector<int> a(n + 1);for(int i = 1; i <= n; ++ i){std::cin >> a[i];}auto check = [&](int v) -> std::tuple<bool, int, int> {static std::vector<int> S;S.resize(n + 1);S[0] = 0;for(int i = 1; i <= n; ++ i){S[i] = S[i - 1] + (a[i] >= v ? 1 : -1);}int tl, tr;int min = 0, min_pos = 0;for(int r = k; r <= n; ++ r){if(S[r] >= min){tl = min_pos + 1;tr = r;return {true, tl, tr};}int j = r - k + 1;if(S[j] < min){min = S[j];min_pos = j;}}return {false, -1, -1};};int lo = 1, hi = n;while(lo < hi){int mid = (lo + hi + 1) >> 1;if (std::get<0>(check(mid))){lo = mid;} else {hi = mid - 1;}}int max = lo;auto [_, L, R] = check(max);std::cout << max << " " << L << " " << R << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}