『模拟赛』多校A层冲刺NOIP2024模拟赛06

news/2024/10/13 10:47:02

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();}