Rank
比较还行
A. 小 Z 的手套（gloves）
签。
最大值最小，一眼二分答案。双指针 check 一下就完了，复杂度 \(\mathcal{O(n\log n)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 10007;
int n, m;
int a[N], b[N];
namespace Wisadel
{bool Wck(int x){int j = 1;fo(i, 1, n){while(j <= m && abs(a[i] - b[j]) > x) j++;if(j > m) return 0;j++;}return 1;}short main(){freopen("gloves.in", "r", stdin) , freopen("gloves.out", "w", stdout);// freopen(".err", "w", stderr);n = qr, m = qr;fo(i, 1, n) a[i] = qr; sort(a + 1, a + 1 + n);fo(i, 1, m) b[i] = qr; sort(b + 1, b + 1 + m);if(n > m){fo(i, 1, n) swap(a[i], b[i]);swap(n, m);}int l = 0, r = 1e9;while(l < r){int mid = (l + r) >> 1;if(Wck(mid)) r = mid;else l = mid + 1;}printf("%d\n", r);return Ratio;}
}
int main(){return Wisadel::main();}
B. 小 Z 的字符串（string）
分讨 dp。
赛时考虑了很久贪心做法，一直没有简单易行的方案，于是想了 dp，但没思路，于是交了假做法 50pts。
正解考虑设 \(f_{i,j,k,0/1/2}\) 表示目前 \(i\) 个 0，\(j\) 个 1，\(k\) 个 2，第 \(i+j+k\) 位为 0/1/2 的方案数。首先特判出不合法的情况，然后直接 dp 就完了，转移限制条件即为当前位与上一位不同，为方便统计坐标差，最后 \(\min\left(f_{num_0,num_1,num_2,0/1/2}\right)\) 除以 2 就是最终答案。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 5e4 + 5;
const int mod = 10007;
int n;
int num[3], q[3][405], f[205][205][205][3];
string s;
namespace Wisadel
{short main(){freopen("string.in", "r", stdin) , freopen("string.out", "w", stdout);// freopen(".err", "w", stderr);cin >> s;n = s.size(); s = " " + s;fo(i, 1, n)if(s[i] == '0') num[0]++, q[0][num[0]] = i;else if(s[i] == '1') num[1]++, q[1][num[1]] = i;else num[2]++, q[2][num[2]] = i;int zc = (n + 1) / 2;if(num[0] > zc || num[1] > zc || num[2] > zc){puts("-1"); return Ratio;}memset(f, 0x3f, sizeof f);f[0][0][0][0] = f[0][0][0][1] = f[0][0][0][2] = 0;fo(i, 0, num[0]) fo(j, 0, num[1]) fo(k, 0, num[2]){int zc = i + j + k;if(i) f[i][j][k][0] = min(f[i - 1][j][k][1], f[i - 1][j][k][2]) + abs(zc - q[0][i]);if(j) f[i][j][k][1] = min(f[i][j - 1][k][0], f[i][j - 1][k][2]) + abs(zc - q[1][j]);if(k) f[i][j][k][2] = min(f[i][j][k - 1][0], f[i][j][k - 1][1]) + abs(zc - q[2][k]); }int ans = 1e9;fo(i, 0, 2) ans = min(ans, f[num[0]][num[1]][num[2]][i]);ans /= 2;printf("%d\n", ans);return Ratio;}
}
int main(){return Wisadel::main();}
C. 一个真实的故事（truth）
我赛时 A 线段树啦！ 被 hack 了，悲（
看到修改查询首先考虑线段树。赛时思路被 T2 略微干扰了下于是考虑记 \(nxt_{i,j}\) 为 \(i\) 位置下一个 \(j\) 种类的坐标，答案为 \(\min\left(\max_{i\in\left[1,n\right]\left(nxt_{i,j}\right)}\right)\)，线段树统计答案是 \(\mathcal{O(1)}\) 的，但是修改操作很困难，主要是无法实现动态处理 \(nxt\) 数组，赛时尝试自我 hack 但是失败了，最慢跑了 0.5s。
考虑正解是如何优化的，改为记每个区间所有种类最靠左和最靠右的位置，pushup 时答案只会从 \(ans_{ls}\)，\(ans_{rs}\) 和左区间靠右、右区间靠左的所有种类合并出的答案。合并时取出上述至多 \(2\times k\) 个位置，然后双指针找出最小答案即可，合并其它信息比较简单。然后就做完了，\(\mathcal{O(\log n)}\) 修改 \(\mathcal{O(1)}\) 查询，带一个 \(k\) 的常数。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 5e4 + 5;
const int mod = 10007;
int n, k, m;
int a[N];
int las[N << 2], Lt[N << 2][31], Rt[N << 2][31], cnt[31], ans[N << 2];
namespace Wisadel
{#define ls (rt << 1)#define rs (rt << 1 | 1)#define mid ((l + r) >> 1)void Wpushup(int rt){int res = 1e9, ok = 0; memset(cnt, 0, sizeof cnt);pii zc[2 * k + 1]; int zcz = 0;fo(i, 1, k) if(Rt[ls][i]) zc[++zcz] = {Rt[ls][i], i};fo(i, 1, k) if(Lt[rs][i]) zc[++zcz] = {Lt[rs][i], i};sort(zc + 1, zc + zcz + 1, [](pii &x, pii &y){return x.fi < y.fi;});int j = 1;fo(i, 1, zcz){if(j < i) j = i;while(j <= zcz && ok < k){if(!cnt[zc[j].se]) ok++;++cnt[zc[j].se]; ++j;}if(ok == k) res = min(res, zc[j - 1].fi - zc[i].fi + 1);cnt[zc[i].se]--;if(!cnt[zc[i].se]) ok--;}if(res != 1e9) ans[rt] = res;if(ans[ls]) ans[rt] = min(ans[rt], ans[ls]);if(ans[rs]) ans[rt] = min(ans[rt], ans[rs]);fo(i, 1, k){if(Lt[ls][i]) Lt[rt][i] = Lt[ls][i];else Lt[rt][i] = Lt[rs][i];if(Rt[rs][i]) Rt[rt][i] = Rt[rs][i];else Rt[rt][i] = Rt[ls][i];}}void Wbuild(int rt, int l, int r){ans[rt] = 1e9;if(l == r){Lt[rt][a[l]] = Rt[rt][a[l]] = l;las[rt] = a[l];return ;}Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);Wpushup(rt);}void Wupd(int rt, int l, int r, int x, int v){ans[rt] = 1e9;if(l == r){Lt[rt][las[rt]] = Rt[rt][las[rt]] = 0;Lt[rt][v] = Rt[rt][v] = x;las[rt] = v;return ;}if(x <= mid) Wupd(ls, l, mid, x, v);else Wupd(rs, mid + 1, r, x, v);Wpushup(rt);}short main(){freopen("truth.in", "r", stdin) , freopen("truth.out", "w", stdout);// freopen(".err", "w", stderr);n = qr, k = qr, m = qr;fo(i, 1, n) a[i] = qr;Wbuild(1, 1, n);fo(i, 1, m){int op = qr, x, y;if(op == 1) x = qr, y = qr, Wupd(1, 1, n, x, y);else printf("%d\n", ans[1] == 1e9 ? -1 : ans[1]);}return Ratio;}
}
int main(){return Wisadel::main();}
D. 异或区间（xor）
trie 树和静态 RMQ，要用到笛卡尔树优化，仙姑。
什么笛卡尔树，不用，这里讲解可持久化 trie 树的做法。
思路起源于 Subtask3，即最大值位置已知的情况。此时构建出 01trie，边插边查询即可。因此考虑每一位作为最大值的管辖范围，由于会有重复的数所以要钦定一端开一段闭，单调栈即可线性实现。然后怎么跑？直接枚举一端端点统计另一端容易被卡成 \(\mathcal{O(n)}\) 统计，所以判断一下，每次枚举较短的一边即可。区间统计所以上可持久化 trie。复杂度是 \(\mathcal{O(n\log n\log V)}\) 的。
点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
int n;
int a[N], s[N];
int rot[N], L[N], R[N], tot;
stack<int> st;
int t[N << 5][2], sum[N << 5];
ll ans;
namespace Wisadel
{int Wbuild(int las, int s){int rt = ++tot, now = rt;sum[now] = sum[las] + 1;fo(i, 1, 30){int zc = (s >> (30 - i)) & 1;t[now][zc] = ++tot;t[now][!zc] = t[las][!zc];now = t[now][zc];las = t[las][zc];sum[now] = sum[las] + 1;}return rt;}int Wq(int x, int y, int a, int s){int res = 0;fo(i, 1, 30){// 如果 a 在这一位为 1，那么直接加上为 0 时的贡献int zc1 = (a >> (30 - i)) & 1, zc2 = (s >> (30 - i)) & 1;if(zc1) res += sum[t[y][zc2]] - sum[t[x][zc2]];x = t[x][zc1 ^ zc2], y = t[y][zc1 ^ zc2];}res += sum[y] - sum[x];return res;}short main(){freopen("xor.in", "r", stdin) , freopen("xor.out", "w", stdout);// freopen(".err", "w", stderr);n = qr;rot[0] = Wbuild(rot[0], 0);fo(i, 1, n) a[i] = qr, s[i] = s[i - 1] ^ a[i], rot[i] = Wbuild(rot[i - 1], s[i]);fo(i, 1, n){while(st.size() && a[st.top()] <= a[i]) st.pop();L[i] = st.size() ? st.top() : 0;st.push(i);}while(st.size()) st.pop();fu(i, n, 1){while(st.size() && a[st.top()] < a[i]) st.pop();R[i] = st.size() ? st.top() : n + 1;st.push(i);} // 单调栈找以 i 为最大值的管辖范围fo(i, 1, n)if(i - L[i] <= R[i] - i) // 枚举较短的一边fo(j, L[i], i - 1) ans += Wq(rot[i - 1], rot[R[i] - 1], a[i], s[j]);elsefu(j, R[i] - 1, i)if(L[i] == 0) ans += Wq(0, rot[i - 1], a[i], s[j]);else ans += Wq(rot[L[i] - 1], rot[i - 1], a[i], s[j]);printf("%lld\n", ans);return Ratio;}
}
int main(){return Wisadel::main();}
末
由于一些原因导致现在才发。
打的还行，可能是前一天的动员产生了一点作用。
总是场切不了 T2 有点恼，总是 T3 打假做法有点恼，总是不会 T4 很多暴力有点恼。
起码在进步，稳住就行。
你说得对但我去的时候是 5 车厢，有一块的吗。
完结撒花~
