小 Z 的手套（gloves）100pts
最大值最小，考虑二分答案；
首先排序，然后每次找出数量较少的那个数组中的每个数 $ x $ 在另一个数组中有没有值在范围 $ [x - mid, x + mid] $ 的（其中 $ mid $ 为二分的答案），其实只需找 $ x - mid $ 就行，最后判断一下所有数是否合法即可；
因为已经升序排序，所以可以双指针维护，当然也可以 lower_bound，但是多个 $ \log $；
时间复杂度；$ \Theta(n \log Z) $ 到 $ \Theta(n \log Z \log n) $ 不等（其中 $ Z $ 为两个数组的极差）；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n, m;
int a[500005], b[500005];
int vis[500005], vi[500005];
bool ck(int x) {
for (int i = 1; i <= max(n, m); i++) {
vis[i] = 0;
vi[i] = 0;
}
if (n < m) {
int now = lower_bound(b + 1, b + 1 + m, a[1] - x) - b;
for (int i = 1; i <= n; i++) {
int lpos = lower_bound(b + 1, b + 1 + m, a[i] - x) - b;
if (lpos > m) return false;
if (now < lpos) now = lpos;
while(vis[now]) now++;
vis[now] = i;
}
for (int i = 1; i <= m; i++) {
if (vis[i]) {
vi[vis[i]] = true;
if (abs(a[vis[i]] - b[i]) > x) return false;
}
}
for (int i = 1; i <= n; i++) if (!vi[i]) return false;
return true;
} else {
int now = lower_bound(a + 1, a + 1 + n, b[1] - x) - a;
for (int i = 1; i <= m; i++) {
int lpos = lower_bound(a + 1, a + 1 + n, b[i] - x) - a;
if (lpos > n) return false;
if (now < lpos) now = lpos;
while(vis[now]) now++;
vis[now] = i;
}
for (int i = 1; i <= n; i++) {
if (vis[i]) {
vi[vis[i]] = true;
if (abs(b[vis[i]] - a[i]) > x) return false;
}
}
for (int i = 1; i <= m; i++) if (!vi[i]) return false;
return true;
}
}
int main() {
freopen("gloves.in", "r", stdin);
freopen("gloves.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
}
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + m);
int l = 0;
int r = 1000000000;
int ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if (ck(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans;
return 0;
}
小 Z 的字符串（string）20pts
DP；
设 $ f_{i, j, k, 0/1/2} $ 表示现在选了 $ i $ 个 $ 0 $， $ j $ 个 $ 1 $ ，$ k $ 个 $ 2 $，当前是 $ 0/1/2 $ 的最小次数；
对于转移，发现肯定不会换同一个数，所以假设有转移 $ f_{i, j, k - 1, 0} \rightarrow f_{i, j, k, 2} $，我们只需将第 $ k $ 个数移动到当前位置 $ (i + j + k) $ 即可，然后计算贡献（注意绝对值），其它同理；
最后答案要除以 $ 2 $，因为假设有两个数能够被转移，它们两个的相对位置是不变的，也就是说前面的由后面的转移过来，后面的也由前面的转移过来，所以要除以 $ 2 $；
时间复杂度：$ \Theta(n^3) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
char s[505];
int t[3][405];
int f[205][205][205][3];
int c[3];
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> (s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
t[s[i] - '0'][++c[s[i] - '0']] = i;
}
if (c[0] > (n + 1) / 2 || c[1] > (n + 1) / 2 || c[2] > (n + 1) / 2) {
cout << -1;
return 0;
}
memset(f, 0x3f, sizeof(f));
f[0][0][0][0] = f[0][0][0][1] = f[0][0][0][2] = 0;
for (int i = 0; i <= c[0]; i++) {
for (int j = 0; j <= c[1]; j++) {
for (int k = 0; k <= c[2]; k++) {
int p = i + j + k;
if (p == 0) continue;
if (i) f[i][j][k][0] = min(f[i - 1][j][k][1], f[i - 1][j][k][2]) + abs(p - t[0][i]);
if (j) f[i][j][k][1] = min(f[i][j - 1][k][0], f[i][j - 1][k][2]) + abs(p - t[1][j]);
if (k) f[i][j][k][2] = min(f[i][j][k - 1][0], f[i][j][k - 1][1]) + abs(p - t[2][k]);
}
}
}
cout << min({f[c[0]][c[1]][c[2]][0], f[c[0]][c[1]][c[2]][1], f[c[0]][c[1]][c[2]][2]}) / 2;
return 0;
}
一个真实的故事（truth）50pts
赛时打的 $ \Theta(\frac{nm \log^2 n}{w}) $ 结果算的时候少算俩 $ \log $，所以50pts；
正解就是线段树；
维护三个东西：
-
答案；
-
从左边开始的1 ~ k 出现的位置；
-
从右边开始的1 ~ k 出现的位置；
这样合并的时候只需将左区间的2和右区间的3合并起来，然后双指针扫一下即可；
时间复杂度：$ \Theta(nk \log n \log k) $，使用 $ sort $ 时可能会把后面的 $ \log $ 去掉；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, k, m;
int a[500005];
int cnt[35];
pair<int, int> rem[75];
int rcnt;
namespace SEG{
inline int ls(int x) {
return x << 1;
}
inline int rs(int x) {
return x << 1 | 1;
}
struct sss{
int l, r, ans, lb[35], rb[35];
}tr[800005];
inline void push_up(int id) {
memset(cnt, 0, sizeof(cnt));
rcnt = 0;
for (int i = 1; i <= k; i++) {
rem[++rcnt] = {tr[ls(id)].rb[i], i};
rem[++rcnt] = {tr[rs(id)].lb[i], i};
}
sort(rem + 1, rem + 1 + rcnt);
int now = 0;
int an = 0x3f3f3f3f;
int pos = 1;
for (int i = 1; i <= rcnt; i++) {
if (rem[i].first) {
pos = i;
break;
}
}
int j = pos;
for (int i = pos; i <= rcnt; i++) {
if (!cnt[rem[i].second]) now++;
cnt[rem[i].second]++;
while(now == k) {
an = min(an, rem[i].first - rem[j].first + 1);
cnt[rem[j].second]--;
if (cnt[rem[j].second] == 0) now--;
j++;
}
}
tr[id].ans = min({an, tr[ls(id)].ans, tr[rs(id)].ans});
for (int i = 1; i <= k; i++) {
if (tr[ls(id)].lb[i]) tr[id].lb[i] = tr[ls(id)].lb[i];
else tr[id].lb[i] = tr[rs(id)].lb[i];
if (tr[rs(id)].rb[i]) tr[id].rb[i] = tr[rs(id)].rb[i];
else tr[id].rb[i] = tr[ls(id)].rb[i];
}
}
void bt(int id, int l, int r) {
tr[id].l = l;
tr[id].r = r;
tr[id].ans = 0x3f3f3f3f;
if (l == r) {
tr[id].lb[a[l]] = tr[id].rb[a[l]] = l;
if (k == 1) {
if (a[l] == k) tr[id].ans = 1;
}
return;
}
int mid = (l + r) >> 1;
bt(ls(id), l, mid);
bt(rs(id), mid + 1, r);
push_up(id);
}
void add(int id, int pos, int x) {
if (tr[id].l == tr[id].r) {
tr[id].ans = 0x3f3f3f3f;
if (k == 1) {
if (a[tr[id].l] == k) tr[id].ans = 1;
}
tr[id].lb[x] = tr[id].rb[x] = 0;
tr[id].lb[a[tr[id].l]] = tr[id].rb[a[tr[id].l]] = tr[id].l;
return;
}
int mid = (tr[id].l + tr[id].r) >> 1;
if (pos <= mid) add(ls(id), pos, x);
else add(rs(id), pos, x);
push_up(id);
}
}
using namespace SEG;
int main() {
freopen("truth.in", "r", stdin);
freopen("truth.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
bt(1, 1, n);
int s, p, v;
for (int i = 1; i <= m; i++) {
cin >> s;
if (s == 1) {
cin >> p >> v;
int x = a[p];
a[p] = v;
add(1, p, x);
}
if (s == 2) {
if (tr[1].ans == 0x3f3f3f3f) cout << -1 << '\n';
else cout << tr[1].ans << '\n';
}
}
return 0;
}