B. Missing Boundaries
给\(N\)个区间，可能存在一些区间的端点不确定。现在你要指定区间的端点，是否可以使得所有不重不漏的覆盖\([1,L]\)
首先考虑两个端点都确定的区间，两两之间应该不相交。
考虑只有一个端点的区间，对于已经被确定的点，一定不能是在已被覆盖的区间内。其次所有的区间的点应该保证不相等。
两个点都不确定的区间可以任意防止，我们只要统计一下个数就好。被两种区间覆盖后，剩下的点统计出最多最少能够放多少个区间，只要在这个范围内就可以。
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = INT_MAX / 2;
void solve() {
int n, L;
cin >> n >> L;
vector<pii> seg, p;
int cnt = 0;
for (int i = 1, l, r; i <= n; i++) {
cin >> l >> r;
if (l != -1 and r != -1) seg.emplace_back(l, r);
else if (l != -1) p.emplace_back(l, 0);
else if (r != -1) p.emplace_back(r, 1);
else cnt++;
}
ranges::sort(seg), ranges::sort(p);
for (int i = 1; i < seg.size(); i++)
if (seg[i - 1].second >= seg[i].first) {
cout << "NIE\n";
return;
}
for (int i = 1; i < p.size(); i++)
if (p[i - 1].first == p[i].first) {
cout << "NIE\n";
return;
}
int i = 0, cntMax = 0, cntMin = 0;
auto work = [&](int l, int r) -> bool {
int lastI = i;
while (i < p.size() and p[i].first <= r) {
if (p[i].first < l) return false;
i++;
}
cntMax += (r - l + 1) - (i - lastI);
if (i == lastI) cntMin++;
else {
for (int j = lastI + 1; j < i; j++)
if (p[j].first != p[j - 1].first + 1 and p[j].second == 0 and p[j - 1].second == 1) cntMin++;
if (p[lastI].first != l and p[lastI].second == 0) cntMin++;
if (p[i - 1].first != r and p[i - 1].second == 1) cntMin++;
}
return true;
};
int lst = 1;
for (auto [l, r]: seg) {
if (l > lst and not work(lst, l - 1)) {
cout << "NIE\n";
return;
}
lst = r + 1;
}
if (lst <= L and not work(lst, L)) {
cout << "NIE\n";
return;
}
if (i != p.size()) {
cout << "NIE\n";
return;
}
if (cntMin <= cnt and cnt <= cntMax) cout << "TAK\n";
else cout << "NIE\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
D. Data Determination
给你一个长度为\(n\)的序列\(a\)，请你选出一个长度为\(k\)的子序列，要满足子序列的中位数为\(m\)
根据\(k\)分奇偶考虑
当为奇数时，中位数只有一个，所以必须是\(m\)，剩下的分别需要在大于等于\(m\)和小于等于\(m\)中任意选择\(\left\lfloor \frac{k}{2} \right\rfloor\)个。
当为偶数时，中位数是两个数的均值，令这两个数是\(l,r\)且满足\(l \le r\)，剩下的分别需要在大于等于\(r\)和小于等于\(l\)中任意选择$\frac k 2 \(个。考虑枚举\)l\(则\)r = 2 m - l$。
统计个数可以用两次二分来实现，总体复杂度\(O(n\log n)\)
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
using vi = vector<int>;
void solve() {
int n, k, m;
cin >> n >> k >> m;
vi a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
ranges::sort(a);
if (k & 1) {
k /= 2;
int cntM = ranges::upper_bound(a, m) - ranges::lower_bound(a, m);
if (cntM == 0) {
cout << "NIE\n";
return;
}
cntM -= 1;
int x = a.end() - ranges::upper_bound(a, m);
int y = ranges::lower_bound(a, m) - a.begin();
cntM -= max(0, k - x) + max(0, k - y);
if (cntM >= 0) cout << "TAK\n";
else cout << "NIE\n";
} else {
k = k / 2 - 1;
for (int r; auto l: a) {
r = 2ll * m - l;
if (r < l) break;
if (l == r) {
int cntM = ranges::upper_bound(a, m) - ranges::lower_bound(a, m);
if (cntM == 0) continue;
cntM -= 2;
int x = a.end() - ranges::upper_bound(a, m);
int y = ranges::lower_bound(a, m) - a.begin();
cntM -= max(0, k - x) + max(0, k - y);
if (cntM >= 0) {
cout << "TAK\n";
return;
}
} else {
int cntL = ranges::upper_bound(a, l) - ranges::lower_bound(a, l);
int cntR = ranges::upper_bound(a, r) - ranges::lower_bound(a, r);
if (cntL == 0 or cntR == 0) continue;
cntL--, cntR--;
int x = a.end() - ranges::upper_bound(a, r);
int y = ranges::lower_bound(a, l) - a.begin();
cntR -= max(0, k - x), cntL -= max(0, k - y);
if (cntR >= 0 and cntL >= 0) {
cout << "TAK\n";
return;
}
}
}
cout << "NIE\n";
}
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
G. Game of Geniuses
给一个\(n\times n\)的矩形，两个人轮流操作。每一轮操作，先手删掉一行，后手删掉一列。\(n-1\)轮后只剩下一个数字，先手希望尽可能大，后手希望尽可能小。两个人都绝对聪明。输出最后的解。
答案就是\(\max_{i} min_j a_{i,j}\)，也就是每一行最小值的最大值。
我们考虑先手，无论如何先手最后会留下一行，而因为先手绝对聪明的，所以留下这一行是固定的。对于后手来说，后手要删掉这一行的\(n-1\)列，因此剩下的一定是这一行的最小值。
在这种情况下，无论先手留下哪一行，在后手的操作下都只能保留这一行的最小值，因此先手会留下最小值最大的一行。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
#define int i64
using vi = vector<int>;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector a(n, vi(n));
for (auto &ai: a)
for (auto &aij: ai)
cin >> aij;
int res = -inf;
for(auto ai : a)
res = max(res, ranges::min(ai));
cout << res;
return 0;
}
J. Juliet Unifies Ones
给一个二进制序列，你可以进行若干次操作，每次操作删除一个位，求最少的操作次数可以使得所有的1都相邻。
可以枚举相邻的\(1\)的区间\([l,r]\)，然后把\([l,r]\)中的\(0\)都删掉，把\([1,l),(r,n]\)中的\(1\)都删掉。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
#define int i64
using vi = vector<int>;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
vi a(n + 1);
for (int i = 1; i <= n; i++)
a[i] = a[i - 1] + s[i - 1] - '0';
int res = a[n];
for (int l = 1, val; l <= n; l++)
for (int r = l; r <= n; r++) {
val = a[n] - 2 * (a[r] - a[l - 1]) + r - l + 1;
res = min(res, val);
}
cout << res;
return 0;
}
L. Random Numbers
给一个排列，求有趣区间的个数。
有趣区间是指，区间的和等于区间长度的平方。
没想到什么很好的思路,前排队伍也没有找到什么其他的做法。
这里有一点要注意的，题目说的序列是随机的。这种情况下，每一位的期望都是\(\frac {n + 1} 2\)，这样的话，长度为\(k\)的区间和的期望为\(\frac{n + 1}2 k\)。根据题目可得到
\[\frac{n+1}{2} k = k ^ 2 \Rightarrow k = \frac{n+1}{2} \]也就说当\(k\)比较接近\(\frac n 2\)时，容易出现解。还有一种情况当\(k\)很小时，因为区间数量很多，也容易出现解。因此我们可以设置一个常数\(B\)，只检查所有长度为\([1,B]\and [\frac n 2 - B , \frac n 2 + B]\)的情况。
本题取\(B=500\)就可以通过。
#include<bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using i128 = __int128;
#define int i64
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = INT_MAX / 2;
void solve() {
int n;
cin >> n;
vi a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i], a[i] += a[i - 1];
const int B = 500;
int res = 0;
for (int len = 1, LEN; len <= n; len++) {
if (len > B and abs(len - n / 2) > B) continue;
LEN = len * len;
for (int l = 1, r = len; r <= n; l++, r++) {
if (LEN == a[r] - a[l - 1]) res++;
}
}
cout << res << "\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
M. Mathematics Championships
先排序，然后相邻两个进行比较，并记录过程中的最大值即可。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
const i32 inf = INT_MAX / 2;
const i64 INF = LLONG_MAX / 2;
#define int i64
using vi = vector<int>;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
int N = 1 << n;
vi a(N);
for (auto &i: a) cin >> i;
int res = -inf;
ranges::sort(a);
for (int t = n; t; t--) {
res = max(res, a.back());
vi na;
for (int i = 1; i < a.size(); i += 2)
na.push_back(a[i] + a[i - 1]);
a = move(na);
}
res = max(res, a.back());
cout << res;
return 0;
}