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

news/2024/10/15 19:21:50

Rank

一般，挂大分场。

A. 限速（speed）

签。

直接跑一棵最小生成树出来，然后 dfs 一遍，如果有边权不小于 $k$ 的就给答案加上绝对值的差，若没有则再遍历一遍所有边找到与 $k$ 之差绝对值最小的边插进去就行，答案就是这个绝对值。

赛时由于没考虑比 $k$ 小的边可以通过 +1 达到 $k$ 而怒挂 60pts。

点击查看代码

#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 = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m, k, maxx = -1e9;
int fx[N];
struct rmm{int u, v, val;} d[N];
bool cmp(rmm A, rmm B){return A.val < B.val;}
int hh[N], to[N << 1], ne[N << 1], w[N << 1], cnt;
ll ans;
bool ok;
namespace Wisadel
{int Wfind(int x){if(x == fx[x]) return x;return fx[x] = Wfind(fx[x]);}void Wadd(int u, int v, int val){to[++cnt] = v;w[cnt] = val;ne[cnt] = hh[u];hh[u] = cnt;}void Wdfs(int u, int fa){for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(v == fa) continue;if(w[i] >= k) ok = 1, ans += 1ll * (w[i] - k);maxx = max(maxx, w[i]);Wdfs(v, u);}}short main(){freopen("speed.in", "r", stdin) , freopen("speed.out", "w", stdout);// freopen(".err", "w", stderr);n = qr, m = qr, k = qr;memset(hh, -1, sizeof hh);fo(i, 1, n) fx[i] = i;fo(i, 1, m) d[i].u = qr, d[i].v = qr, d[i].val = qr;sort(d + 1, d + 1 + m, cmp);int cnt = 0, zc = 0, cz = 0, i = 1;while(cnt < n - 1){zc = Wfind(d[i].u), cz = Wfind(d[i].v);if(zc != cz){Wadd(d[i].u, d[i].v, d[i].val), Wadd(d[i].v, d[i].u, d[i].val);fx[zc] = cz;cnt++;}i++;}Wdfs(1, 0);if(ok) printf("%lld\n", ans);else{ans = k - maxx;fo(i, 1, m) ans = min(ans, 1ll * abs(d[i].val - k));printf("%lld\n", ans);}return Ratio;}
}
signed main(){return Wisadel::main();}

B. 酒鬼（drunkard）

也算是签。

直接大力分讨。由于没有撤销操作，所以只要一个线索矛盾，后面的都不用考虑了。因此我们判断只需找到与当前线索时间最接近的两个判一下就行。用 set 维护 pair，很方便。

这道题特殊之处在于，只有开局在 1 的时候是可以不动的，此后一定一直移动，因此走到每相隔两个的点的时间的奇偶性是一致的。因此我们需要特殊处理可以不走的 1 的情况。时间小于当前 $t_0$ 的最大值即可以不走的情况，这种情况需要更新最小值。

当目前没有最小值时，最小值更新为 $tim\mod 2$；当有最小值且最小值与当前时间奇偶性不一致时且该最小值由该情况更新，更新为上一个更新最小值的时间 +1，否则更新为当前时间，这是为了保证停留在 1 的线索都被满足。然后记得与地点不在 1 的其它线索共奇偶性，即若与之不同，最小值 +1。

我们将其它情况都丢进 set 内。当 set 为空时，可以确定最大值以及奇偶性，并更新最小值。否则用时间 lower_bound 出一条线索，若为 set 的第一个，说明这是最早的线索，只考虑它与二分出的线索是否合法。合法要求两点，一是奇偶性相同，而是在二者相隔的时间内能走到彼此。若不是，则需考它和左右两个线索是否合法。此时仍要求两点，一是与前一个线索满足奇偶性和可达性，二是与后一个线索满足奇偶性和可达性。注意考虑 lower_bound 结果为 end 指针的情况

任何时刻，只要最小值超过最大值，都是矛盾的。只要矛盾，我们就没必要进行其它的判断操作了。

其余就没啥了，记得最大值极大时输出 inf。

赛后调了大概 3 个细节，不知道还能不能算挂分，能算就挂 53pts。

点击查看代码

#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 M_P(a, b) make_pair(a, b)
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, m, cnt, mx = 1e9 + 1, mi = 1e9 + 1, ji = -1, pl = -1;
string s;
pii cl[N];
set<pii> st;
set<pii>::iterator it;
namespace Wisadel
{short main(){freopen("drunkard.in", "r", stdin) , freopen("drunkard.out", "w", stdout);// freopen(".err", "w", stderr);n = qr, m = qr;bool jia = 0, clu= 0;fo(i, 1, m){cin >> s;if(s == "clue"){cl[++cnt].se = qr, cl[cnt].fi = qr;if(cl[cnt].se != 1 && cl[cnt].se > cl[cnt].fi) jia = 1;if(jia) continue;if(cl[cnt].se == 1 && cl[cnt].fi <= mx){if(mi == 1e9 + 1) mi = cl[cnt].fi % 2, pl = cl[cnt].fi;else if((cl[cnt].fi + mi) % 2 != 0){if(pl != -1 && cl[cnt].fi % 2 != pl % 2) mi = max(mi, pl + 1), pl = cl[cnt].fi;else mi = max(mi, cl[cnt].fi);if(ji != -1 && mi % 2 != ji) mi++;}if(mi > mx) jia = 1;continue;}if(!st.size()){mx = cl[cnt].fi - cl[cnt].se + 1;ji = mx % 2;if(mi == 1e9 + 1) mi = ji;else if(mi % 2 != ji) mi = pl + 1;if(mi > mx) jia = 1;}else{it = st.lower_bound(M_P(cl[cnt].fi, 0));pii c, d;if(it == st.begin()){c = *it;int zc = c.fi - cl[cnt].fi;if(zc >= abs(c.se - cl[cnt].se) && (zc - abs(c.se - cl[cnt].se)) % 2 == 0){int maxx = cl[cnt].fi - cl[cnt].se + 1;mx = min(mx, maxx);}else jia = 1;}else{it--, c = *it;int zc = cl[cnt].fi - c.fi;if(zc >= abs(c.se - cl[cnt].se) && (zc - abs(c.se - cl[cnt].se)) % 2 == 0){it++;if(it != st.end()){d = c;c = *it;zc = c.fi - cl[cnt].fi;if(zc >= abs(c.se - cl[cnt].se) && (zc - abs(c.se - cl[cnt].se)) % 2 == 0);else jia = 1;}}else jia = 1;}if(mi > mx) jia = 1;}st.insert(cl[cnt]);}else if(s == "max"){if(jia) printf("bad\n");else if(mx == 1e9 + 1) printf("inf\n");else printf("%d\n", mx);}else{if(jia) printf("bad\n");else if(mi == 1e9 + 1) printf("0\n");else printf("%d\n", mi);}}return Ratio;}
}
signed main(){return Wisadel::main();}

C. 距离（distance）

暴力最爽的一集，直接给 $\mathcal{O(n^2)}$ 70pts，~~为出题人点赞~~

用到一个很好的 trick：切比雪夫距离转曼哈顿距离。

在一个平面上有两点 $\left(x,y\right)$，$\left(a,b\right)$。众所周知，两点的曼哈顿距离为 $|x-a|+|y-b|$，众所不周知，两点的切比雪夫距离为 $\max\left(|x-a|,|y-b|\right)$。我们将两点转变为 $\left(\frac{x+y}{2},\frac{x-y}{2}\right)$ 和 $\left(\frac{a+b}{2},\frac{a-b}{2}\right)$ 后，原坐标系的曼哈顿距离即为新坐标系的切比雪夫距离。

摘自 OI-wiki。

跟本题有什么关系呢？根据显然等式 $a+b=\max\left(a,b\right)+\min\left(a,b\right)$，我们可以将所求 $\sum_{i\in subtree_u}\sum_{j\in subtree_u}\ \min\left(|a_i-a_j|,|b_i-b_j|\right)$ 转化为 $\sum_{i\in subtree_u}\sum_{j\in subtree_u}\ |a_i-a_j|+|b_i-b_j| - \max\left(|a_i-a_j|,|b_i-b_j|\right)$，再令 $p_i=\frac{a_i+b_i}{2}$，$q_i=\frac{a_i-b_i}{2}$，则答案就转化为了 $\sum_{i\in subtree_u}\sum_{j\in subtree_u}\ |a_i-a_j|+|b_i-b_j| -\left(|p_i-p_j|+|q_i-q_j|\right) $。

那么问题就转化为了解决四个形如 $\sum_{i}\sum_j\ |a_i-a_j|$ 的问题。考虑依次插入数更新贡献会用到小于/大于 $a_i$ 的个数及和，用线段树维护一下即可，然后统计答案直接树上启发式合并即可，这样复杂度是 $\mathcal{O(n\log ^2n)}$ 的，需要卡常，建议小常数选手食用。

为降低复杂度，我们可以牺牲一些常数来使得 $a_i$ 数组有序，对于有序的数组统计答案就可以根据左右子树的信息直接 $\mathcal{O(1)}$ 得出了。时间复杂度 $\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 M_P(a, b) make_pair(a, b)
#define fi first
#define se second
const int Ratio = 0;
const int N = 5e5 + 5;
const int mod = 1e9 + 7;
int n, tot;
int a[N], b[N], p[N], q[N], c[N], d[N], zc[N], rot[N], cl;
int hh[N], to[N << 1], ne[N << 1], cntt;
int cnt[N << 5], sum[N << 5], ans[N << 5], son[N << 5][2];
ll Ans[N];
namespace Wisadel
{ll Wqp(ll x, int y){ll res = 1;while(y){if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1;}return res;}void Wadd(int u, int v){to[++cntt] = v;ne[cntt] = hh[u];hh[u] = cntt;}#define ls(rt) (son[rt][0])#define rs(rt) (son[rt][1])#define mid ((l + r) >> 1)void Wpushup(int rt){cnt[rt] = cnt[ls(rt)] + cnt[rs(rt)], sum[rt] = (sum[ls(rt)] + sum[rs(rt)]) % mod;ans[rt] = (((ans[ls(rt)] + ans[rs(rt)]) % mod + 1ll * sum[rs(rt)] * cnt[ls(rt)] % mod) % mod - 1ll * sum[ls(rt)] * cnt[rs(rt)] % mod + mod) % mod;}void Wins(int &rt, int pre, int l, int r, int x, int k){if(!rt) rt = ++cl;ls(rt) = ls(pre), rs(rt) = rs(pre);cnt[rt] = cnt[pre] + 1, sum[rt] = (sum[pre] + k) % mod;ans[rt] = ans[pre];if(l == r) return ;if(x <= mid) Wins(ls(rt), ls(pre), l, mid, x, k);else Wins(rs(rt), rs(pre), mid + 1, r, x, k);Wpushup(rt);}int Wmerge(int u, int v, int l, int r){if(!u || !v) return u + v;if(l == r){cnt[u] += cnt[v];sum[u] = (sum[u] + sum[v]) % mod;ans[u] = (ans[u] + ans[v]) % mod;return u;}ls(u) = Wmerge(ls(u), ls(v), l, mid), rs(u) = Wmerge(rs(u), rs(v), mid + 1, r);Wpushup(u);return u;}void Wdfs(int u, int fa, int quan){for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(v == fa) continue;Wdfs(v, u, quan);rot[u] = Wmerge(rot[u], rot[v], 1, tot);}Wins(rot[u], rot[u], 1, tot, c[u], d[u]);Ans[u] = (Ans[u] + 1ll * ans[rot[u]] * quan % mod) % mod;}void Wdo(int quan){fo(i, 1, n) c[i] = zc[i] = a[i];sort(zc + 1, zc + 1 + n);tot = unique(zc + 1, zc + 1 + n) - zc - 1;fo(i, 1, n) d[i] = c[i], c[i] = lower_bound(zc + 1, zc + 1 + tot, c[i]) - zc;Wdfs(1, 0, quan);fo(i, 1, n) rot[i] = 0;fo(i, 1, cl) cnt[i] = sum[i] = ans[i] = 0;cl = 0;}short main(){freopen("distance.in", "r", stdin) , freopen("distance.out", "w", stdout);// freopen(".err", "w", stderr);n = qr;memset(hh, -1, sizeof hh);fo(i, 1, n - 1){int a = qr, b = qr;Wadd(a, b), Wadd(b, a);}fo(i, 1, n) a[i] = qr, b[i] = qr, p[i] = a[i] + b[i], q[i] = a[i] - b[i];Wdo(1); memcpy(a, b, sizeof b);Wdo(1); memcpy(a, p, sizeof p);Wdo(1ll * (mod - 1) * Wqp(2, mod - 2) % mod); memcpy(a, q, sizeof q);Wdo(1ll * (mod - 1) * Wqp(2, mod - 2) % mod);fo(i, 1, n) printf("%lld\n", Ans[i] * 2 % mod);return Ratio;}
}
signed main(){return Wisadel::main();}

D. 团队选拔（selection）

大概不太可做？赛时打了指数做法和 $a_i=1$ 的特殊性质共 16pts，赛后学了 $\mathcal{O(n^4)}$ 的 dp 做法，然后 32pts。~~整场没见过这个分。~~

特殊性质还是很好找的，打个表发现每个数组第一个数的关系是 $f_i=f_{i-1}\times 3 -f_{i-2}$，此后每一个位置上的数有 $f_{i,j}=f_{i,0}+f_{i-2,j-1}$。然后你会发现这样空间复杂度是 $\mathcal{O(n^2)}$ 的，每次 shrink_to_fit 也无济于事，所以我们不能记下 $\left[1,n\right]$ 的全部答案。然后我们列举一下再推一层，就能得到 $f_{i,j}=f_{i,j-1}+f_{i-2\times j,0}$，此时我们就只用 $\mathcal{O(n)}$ 记第一个数，然后推出 $n$ 时的答案了。

至于 $\mathcal{O(n^4)}$ 的暴力，我们设 $f_{i,j}$ 表示 $\left[1,j\right]$ 的方案中 $\left[i,j\right]$ 是一支队伍的方案数。此时转移有 $f_{i,j}=\sum_{x\le y\lt i}\ f_{x,y}\left[gcd_{\left[x,y\right]}=gcd_{\left[i,j\right]}\right]$，区间 gcd 可以 st 表 $\mathcal{O(n\log n)}$ 预处理出来。然后再设 $g_{i,j}$ 为 $\left[i,n\right]$ 的方案中 $\left[i,j\right]$ 为一支队伍的方案数。最后 $\mathcal{O(n^3)}$ 统计答案。

点击查看代码

// ubsan: undefined
// accoders
#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 M_P(a, b) make_pair(a, b)
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 998244353;
int n;
int a[N], ans[N];
int st[N][20], f[5000][5000], g[5000][5000];
namespace Wtask
{vector<int> v[N];short main(){v[1].push_back(1);v[2].push_back(3);fo(i, 3, n){int tim = i / 2 + (i & 1);int zc = (1ll * v[i - 1][0] * 3 % mod - v[i - 2][0] + mod) % mod;v[i].push_back(zc);}int tim = n / 2 + (n & 1);int j = n - 2;fo(i, 1, tim - 1){int zc = (v[n][i - 1] + v[j][0]) % mod;v[n].push_back(zc), j -= 2;}fo(i, 0, tim - 1) printf("%d ", v[n][i]);if(n & 1) fu(i, tim - 2, 0) printf("%d ", v[n][i]);else fu(i, tim - 1, 0) printf("%d ", v[n][i]);puts("");return Ratio;}
}
namespace Wisadel
{int Wget(int l, int r){int zc = log2(r - l + 1);return __gcd(st[l][zc], st[r - (1 << zc) + 1][zc]);}short main(){freopen("selection.in", "r", stdin) , freopen("selection.out", "w", stdout);// freopen(".err", "w", stderr);n = qr; bool task = 1;fo(i, 1, n){a[i] = qr;if(a[i] != 1) task = 0;}if(task) return Wtask::main();fo(i, 1, n) st[i][0] = a[i];fo(j, 1, 19) fo(i, 1, n) if(i + (1 << (j - 1)) <= n)st[i][j] = __gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);fo(i, 1, n) fo(j, i, n){f[i][j] = 1;fo(x, 1, i - 1) fo(y, x, i - 1)if(Wget(i, j) == Wget(x, y))f[i][j] = (f[i][j] + f[x][y]) % mod;}fu(j, n, 1) fu(i, j, 1){g[i][j] = 1;fu(y, n, j + 1) fu(x, y, j + 1)if(Wget(i, j) == Wget(x, y))g[i][j] = (g[i][j] + g[x][y]) % mod;}fo(i, 1, n) fo(j, i, n) fo(k, i, j) ans[k] = (ans[k] + 1ll * f[i][j] * g[i][j]) % mod;fo(i, 1, n) printf("%d ", ans[i]);return Ratio;}
}
signed main(){return Wisadel::main();}