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

news/2024/10/3 17:56:44

Rank

打得还可以

总

A. 构造字符串

签，但是挂了 40pts。

发现判条件只有相等和不相等，于是想到并查集维护连通块，将强制相同的两个位置的连通块合并，强制不同的先记下，最后统一判断。

重点在细节处理，合并连通块时要将位置靠后的合并到靠前的上，注意 \(LCP(x,y)=z\) 在 \(x+z,y+z\le n\) 时，存在 \(s_{x+z}\neq s_{y+z}\) 的要求，漏了这个就会狠挂 40pts，同样，判断位置字符不同时修改操作也要在位置靠后的块上进行，同时记一下每个块不能成为哪个数，为防止出现一个数先与其后的数更新然后与其前的数更新导致答案不优的情况，我将这些判断做了排序。

点击查看代码

#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 fi first
#define se second
const int Ratio = 0;
const int N = 1e4 + 5;
int n , m, tot;
int fx[N], ans[N];
bool yz[1005][1005];
struct neq{int x, y;} a[N];
namespace Wisadel
{int Wfind(int x){if(x == fx[x]) return x;return fx[x] = Wfind(fx[x]);}bool cmp(neq A, neq B){return Wfind(A.x) == Wfind(B.x) ? Wfind(A.y) < Wfind(B.y) : fx[A.x] < fx[B.x];}short main(){freopen("str.in", "r", stdin) , freopen("str.out", "w", stdout);n = qr, m = qr;fo(i, 1, n) fx[i] = i;fo(i, 1, m){int x = qr, y = qr, z = qr;if(x == y && z != 0){printf("-1\n"); return Ratio;}if(z == 0) a[++tot] = {x, y};else{fo(j, 0, z - 1){int _ = Wfind(x + j), __ = Wfind(y + j);if(_ > __) swap(_, __);fx[__] = _;}if(x + z > n || y + z > n) continue;a[++tot] = {x + z, y + z};}}sort(a + 1, a + 1 + tot, cmp);fo(i, 1, tot){int _ = Wfind(a[i].x), __ = Wfind(a[i].y);if(_ == __){printf("-1\n"); return Ratio;}if(ans[_] != ans[__]){yz[_][ans[__]] = yz[__][ans[_]] = 1 ; continue;}if(_ > __) swap(_, __);int zc = ans[_];yz[__][zc] = 1;while(yz[__][zc]) zc++;ans[__] = zc, yz[_][zc] = 1;}fo(i, 1, n) printf("%d ", ans[Wfind(i)]);return Ratio;}
}
int main(){return Wisadel::main();}

B. 寻宝

真·签。

过的人比 T1 多，那就简单说说好了。

还是用并查集，将完全相连的点聚合到一个连通块内，然后对于传送门，我们将连通块连上单向边，然后查询时每次对连通块跑一遍 bfs 即可，复杂度最差是 \(\mathcal{qk}\) 的，总复杂度 \(\mathcal{O(nm+qk)}\)。

点击查看代码

#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 fi first
#define se second
const int Ratio = 0;
const int N = 5e4 + 5;
int n, m, k, q;
int fx[N];
int hh[N], to[N << 1], ne[N << 1], cnt;
bool yz[N];
char ch[N];
namespace Wisadel
{void Wadd(int u, int v){to[++cnt] = v;ne[cnt] = hh[u];hh[u] = cnt;}int Wfind(int x){if(x == fx[x]) return x;return fx[x] = Wfind(fx[x]);}bool Wsol(int x, int tar){if(x == tar) return 1;memset(yz, 0, sizeof yz);queue<int> q;q.push(x);while(q.size()){int u = q.front(); q.pop();yz[u] = 1;for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(!yz[v]){yz[v] = 1;if(v == tar) return 1;q.push(v);}}}return 0;}short main(){freopen("treasure.in", "r", stdin) , freopen("treasure.out", "w", stdout);n = qr, m = qr, k = qr, q = qr;memset(hh, -1, sizeof hh);fo(i, 1, n * m) fx[i] = i;fo(i, 1, n) fo(j, 1, m) scanf(" %c", &ch[(i - 1) * m + j]);fo(i, 1, n)fo(j, 1, m){int _ , __;if(j != m && ch[(i - 1) * m + j] == '.' && ch[(i - 1) * m + j + 1] == '.'){_ = Wfind((i - 1) * m + j), __ = Wfind((i - 1) * m + j + 1);if(_ > __) swap(_, __);fx[__] = _;}if(i != n && ch[(i - 1) * m + j] == '.' && ch[i * m + j] == '.'){_ = Wfind((i - 1) * m + j), __ = Wfind(i * m + j);if(_ > __) swap(_, __);fx[__] = _;}}fo(i, 1, k){int xa = qr, ya = qr, xb = qr, yb = qr;int za = (xa - 1) * m + ya, zb = (xb - 1) * m + yb;int _ = Wfind(za), __ = Wfind(zb);Wadd(_, __);}fo(i, 1, q){int xa = qr, ya = qr, xb = qr, yb = qr;int za = (xa - 1) * m + ya, zb = (xb - 1) * m + yb;int _ = Wfind(za), __ = Wfind(zb);if(Wsol(_, __)) printf("1\n");else printf("0\n");}return Ratio;}
}
int main(){return Wisadel::main();}

C. 序列

\(\mathcal{O(n^2)}\) 做法很显然，对于给定的 \(p_i\) 求 \((l,r)\) 使得答案最大，我们可以将其拆成求 \([l,p_i]\) 和 \((p_i,r]\) 这两个区间分别的最大值，维护个前缀和实现 \(\mathcal{O(1)}\) 查询 \(a_i\) 和 \(b_i\) 的区间和，就能达到 \(\mathcal{O(nm)}\) 的复杂度。

有了前缀和的优化，此时我们所求可以转化为 \((A_r-A_l)-k\times (B_r-B_l)\) 的最大值，我们可以将其拆成两个式子 \(A_r-B_r\times k\) 和 \(-A_l+B_l\times k\)，可以看做是 \(k\) 为自变量的一次函数。维护一次函数最值问题遂想到李超线段树，将询问离线下来按 \(p_i\) 升序排序，分别求两个式子的最大值然后加和就是最终答案，时间复杂度 \(\mathcal{O(n\log^2n+m\log n)}\)。

还有，这道题 \(k\le|10^6|\)，所以空间大小应该是 \(10^6\times 2^3\)。

点击查看代码

#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 fi first
#define se second
const int Ratio = 0;
const int N = 1e6 + 5;
const int maxn = 1e6 + 2;
int n, m;
ll a[N], b[N], suma[N], sumb[N], ans[N];
struct rmm{ll p, k; int id;} q[N];
bool cmp(rmm A, rmm B){return A.p < B.p;}
struct edge{ll k, b; edge(){b = -1e18, k = 0;}} e[N << 3];
namespace Wisadel
{#define ls (rt << 1)#define rs (rt << 1 | 1)#define mid ((l + r) >> 1)ll W(ll x, ll k, ll b){return k * x + b;}void Wins(int rt, int l, int r, ll k, ll b){ll bf = W(mid, e[rt].k, e[rt].b), now = W(mid, k, b);if(now > bf) swap(k, e[rt].k), swap(b, e[rt].b);if(l == r) return;if(W(l, k, b) > W(l, e[rt].k, e[rt].b)) Wins(ls, l, mid, k, b);if(W(r, k, b) > W(r, e[rt].k, e[rt].b)) Wins(rs, mid + 1, r, k, b);}ll Wq(int rt, int l, int r, int x){ll res = W(x, e[rt].k, e[rt].b);if(l == r) return res;if(x <= mid) res = max(res, Wq(ls, l, mid, x));else res = max(res, Wq(rs, mid + 1, r, x));return res;}short main(){freopen("seq.in", "r", stdin) , freopen("seq.out", "w", stdout);n = qr, m = qr;fo(i, 1, n) a[i] = qr, b[i] = qr, suma[i] = suma[i - 1] + a[i], sumb[i] = sumb[i - 1] + b[i];fo(i, 1, m) q[i].id = i, q[i].p = qr, q[i].k = qr;sort(q + 1, q + 1 + m, cmp);int now = 1;Wins(1, -maxn, maxn, 0, 0);fo(i, 1, m){// - A_l + B_l\times kwhile(now <= n && now + 1 <= q[i].p)Wins(1, -maxn, maxn, sumb[now], -suma[now]), now++;ans[q[i].id] += Wq(1, -maxn, maxn, q[i].k);}fo(i, 1, maxn << 3) e[i].k = 0, e[i].b = -1e18;now = n;fu(i, m, 1){// A_r - B_r\times kwhile(now >= 1 && now >= q[i].p)Wins(1, -maxn, maxn, -sumb[now], suma[now]), now--;ans[q[i].id] += Wq(1, -maxn, maxn, q[i].k);}fo(i, 1, m) printf("%lld\n", ans[i]);return Ratio;}
}
int main(){return Wisadel::main();}