『模拟赛』CSP-S模拟7（更新 T4

news/2024/9/30 20:58:25

Rank

烂

A. median

签。

你说得对，但是赛时嗯打 150 行 5k 代码超级分讨过了。

因为容斥做的不好，求总的然后减总会差点东西，所以直接分着加。发现如果中位数在这五个数中不止出现一次那么就会算重，所以分三种大情况考虑。

一，中位数只有一个。那么此时我们需要找到另外两个小于它的和另外两个大于它的，符合乘法原理。

二，中位数有两个。那么此时要分为一个数比它们小和两个数比它们小的情况。

三，中位数三个及以上。此时无论其它数选什么都不会改变贡献。

考虑实现以上操作需要维护什么。首先值域范围 \(10^9\)，硬维护数量铁开不下，但 \(n\) 只有 \(10^5\)，也就是说最多有 \(5\times 10^5\) 种不同的数，读入之后离散化一下即可，然后处理出每个数组的前缀和，再根据上述情况做就行了。外层枚举中位数在离散化后的编号，内层找含有该数的数组，然后进 dfs 找到方案即可。复杂度看起来是 \(\mathcal{O(5n\times 2^5)}\) 的，但实际上跑不满，效率还是很高的。

赛时由于是一点一点打的，可能常数有点大，很多赘余可以合并起来，但我不想重构了，所以就放这个删了注释的赛时代码了，理解之后还是很好理解的。

点击查看代码

#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 = 1e5 + 5;
const int mod = 998244353;
int n, m;
int a[6][N], al[N * 5], tot, cnt[6][N * 5];
bool yz1[6], yz2[6], yzz[6], yz3[6], yz4[6];
ll ans;
namespace Wisadel
{void Wdfs1(int wc, int targ, int now, int rsum){if(rsum == 2){ll res = cnt[wc][targ] - cnt[wc][targ - 1];ll lca = 1, rca = 1;fo(i, 1, 5){if(i == wc) continue;if(yz1[i]) lca = lca * cnt[i][targ - 1] % mod;if(yz2[i]) rca = rca * (cnt[i][tot] - cnt[i][targ]) % mod;}res = res * lca % mod * rca % mod;ans = (ans + al[targ] * res) % mod;return;}if(now > 5) return ;if(now == wc || yz1[now]){Wdfs1(wc, targ, now + 1, rsum); return;}if(cnt[now][tot] - cnt[now][targ] > 0) yz2[now] = 1, Wdfs1(wc, targ, now + 1, rsum + 1), yz2[now] = 0;Wdfs1(wc, targ, now + 1, rsum);}void Wdfs(int wc, int targ, int now, int lsum){if(lsum == 2){Wdfs1(wc, targ, 1, 0);return ;}if(now > 5) return ;if(now == wc){Wdfs(wc, targ, now + 1, lsum); return;}if(cnt[now][targ - 1] > 0) yz1[now] = 1, Wdfs(wc, targ, now + 1, lsum + 1), yz1[now] = 0;Wdfs(wc, targ, now + 1, lsum);}void Wdfss(int now, int targ, int ned){if(ned <= 0){ll res = 1, cc = 1;fo(i, 1, 5){if(yzz[i]) res = res * (cnt[i][targ] - cnt[i][targ - 1]) % mod;else cc = cc * (cnt[i][tot] - (cnt[i][targ] - cnt[i][targ - 1])) % mod;}ans = (ans + res * cc % mod * al[targ] % mod) % mod;return;}if(now > 5) return;if(cnt[now][targ] - cnt[now][targ - 1] > 0) yzz[now] = 1, Wdfss(now + 1, targ, ned - 1), yzz[now] = 0;Wdfss(now + 1, targ, ned);}void Wdfsss(int now, int targ, int ned){if(ned <= 0){ll res = 1, lsu = 1, rsu = 1;fo(i, 1, 5){if(yz3[i]) res = res * (cnt[i][targ] - cnt[i][targ - 1]) % mod;else if(yz4[i]) lsu = lsu * cnt[i][targ - 1] % mod;else rsu = rsu * (cnt[i][tot] - cnt[i][targ]) % mod;}ans = (ans + res * lsu % mod * rsu % mod * al[targ] % mod) % mod;return;}if(now > 5) return;if(yz3[now]){Wdfsss(now + 1, targ, ned); return ;}if(cnt[now][targ - 1] > 0) yz4[now] = 1, Wdfsss(now + 1, targ, ned - 1), yz4[now] = 0;Wdfsss(now + 1, targ, ned);}void Wdfs2(int now, int targ, int ned){if(ned <= 0){Wdfsss(1, targ, 1);Wdfsss(1, targ, 2);return;}if(now > 5) return;if(cnt[now][targ] - cnt[now][targ - 1] > 0) yz3[now] = 1, Wdfs2(now + 1, targ, ned - 1), yz3[now] = 0;Wdfs2(now + 1, targ, ned);}short main(){freopen("median.in", "r", stdin) , freopen("median.out", "w", stdout);n = qr;fo(i, 1, 5)fo(j, 1, n) a[i][j] = qr, al[(i - 1) * n + j] = a[i][j];tot = n * 5;sort(al + 1, al + tot + 1);tot = unique(al + 1, al + tot + 1) -al - 1;fo(i, 1, 5)fo(j, 1, n)cnt[i][lower_bound(al + 1, al + tot + 1, a[i][j]) -al] ++;fo(i, 1, 5) fo(j, 1, tot) cnt[i][j] += cnt[i][j - 1];fo(i, 1, tot)fo(j, 1, 5)if(cnt[j][i] - cnt[j][i - 1] > 0)Wdfs(j, i, 1, 0);fo(i, 1, tot){if(i > 1 && i < tot) Wdfs2(1, i, 2);fo(tim, 3, 5)Wdfss(1, i, tim);}printf("%lld\n", ans);return Ratio;}
}
int main(){return Wisadel::main();}

B. travel

也算是签吧，虽然改了数据绑包之后保龄了。

赛时完全没想到自环对答案也是有影响的，就直接删了没管，然后 hack 全输出 Yes 的人的时候顺手给我 hack 了。

Upd：题意解释，任选起点和终点后，若不存在一个边界值，使得之后的 \(f(x,y,k)\) 都为定值，即 \(f(x,y,k)\) 的值是在定义域上不断变化的，那么它就是有趣的。

借助样例解释理解一下，就是当选择一个起点和终点后能一直跑下去并且存在不一样的路径数。事实上就是找环，显然当取环上某一点作为起点和终点时，如果 \(k\) 是环大小的倍数，则答案为 1，否则为 0，无论 \(k\) 取多大都不会成为一个定值。再考虑我漏掉的自环的影响，发现如果一条路径上存在两个及以上的自环，它的每一个自环都可以走任意次，以相连的两个点各有一个自环为例，根据 \(k\) 值的不同，它所得到的答案的数量为 \(k\)，显然不存在一个极限值使得其成为定值。

那么就考虑如何实现了。其实是非常简单的，一开始仍然不把自环连进去，重边用 set 处理一下，找环用 dfs 就行，找不到环再去枚举每一条路径求其上自环数量，复杂度 \(\mathcal{O(n+m)}\)。

点击查看代码

#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 = 5e5 + 5;
const int mod = 998244353;
int n, m;
int hh[N], to[N << 1], ne[N << 1], cnt, tot[N], rd[N], zh[N];
bool vis[N], bb[N], huan, yz[N];
set<int> st[N];
namespace Wisadel
{void Wadd(int u, int v){to[++cnt] = v;ne[cnt] = hh[u];hh[u] = cnt;}void Wdfs(int u){vis[u] = 1,yz[u] = 1;for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(yz[v]){huan = 1; return;}Wdfs(v);if(huan) return;}yz[u] = 0;}bool Wbfs(int x){queue<int> q;int sum = 0;q.push(x);while(q.size()){int u = q.front(); q.pop();bb[u] = 1;sum += zh[u];if(sum > 1) return 1;for(int i = hh[u]; i != -1; i = ne[i])q.push(to[i]);}return 0;}short main(){freopen("travel.in", "r", stdin) , freopen("travel.out", "w", stdout);n = qr, m = qr; huan = 0;memset(hh, -1, sizeof hh);fo(i, 1, m){int a = qr, b = qr;if(a == b){zh[a] += 1; continue;}st[a].insert(b);}fo(i, 1, n) for(auto j : st[i]) Wadd(i, j);fo(i, 1, n){if(!vis[i]) Wdfs(i);if(huan) break;}if(huan) printf("Yes\n");else{bool can = 0;fo(i, 1, n)if(!bb[i])if(Wbfs(i)){can = 1; break;}if(can) printf("Yes\n");else printf("No\n");}return Ratio;}
}
int main(){return Wisadel::main();}

C. game

挺简单的博弈论，不过赛时唐了错解没注释掉，然后又顺手给我 hack 了。

首先最基本的，偶数个 1 同时存在的局面一定是必败局面；额外很显然的，两个相同的数的局面也一定是必败局面；那么给出推论：偶数个相同的数存在的局面一定是必败局面。

那么现在只需证明两件事。其一是这些局面无论如何操作结果均不在这个集合内。比较显然的是，后首跟着先手做相同操作，一定能使结果局面仍为必败，因为这样操作的终点是剩余两个 1。此时我们发现可以将必败局面集合扩展到偶数个并且可分为两两相同的若干组的局面。

其二是不在集合内的局面有可以一步操作达到这个局面的操作。我们将个数按升序排序。可以发现此时只要我们选取最大的无法配对为两两相同的一组的一个数，一定存在一组分配方案使得结果局面在集合内。这个证明比较容易，对于当前有奇数的数的情况，达到必败局面所需的个数为 \(\sum_{i=1}^n\ a_{i+1}-a_i\ [i \mod 2 = 0]\)，显然其值是小于最大值的；对于偶数的情况，我们让最大的无法配对的数与最小的无法配对的数配对，所需结果仍然是小于拿去后可操作数的，所以结论得证。

然后就非常简单了，对于奇数直接 Yes，偶数就排个序，判一下能否两两配对即可。

点击查看代码

#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 = 2e5 + 5;
const int mod = 998244353;
int n;
int a[N];
namespace Wisadel
{short main(){freopen("game.in", "r", stdin) , freopen("game.out", "w", stdout);int T = qr;while(T--){n = qr;fo(i, 1, n) a[i] = qr;if(n & 1){printf("Yes\n"); continue;}bool can = 0;sort(a + 1, a + 1 + n);fo(i, 1, n){if(i & 1) continue;if(a[i] != a[i - 1]){can = 1; break;}}if(can) printf("Yes\n");else printf("No\n");}return Ratio;}
}
int main(){return Wisadel::main();}

D. counter

~~二分的题，看着像 ABC 常出的那种头脑风暴题，改出来再写。~~

改出来了。

简而言之，首先说明一个性质，一个数 \(x\) 扩展到另一个数的范围是 \([x + 1, x + 9]\)，也就是说，每一个区间中的连续九个数一定至少有一个是必经的。

然后我们考虑猫树，其实就是一个不完整的线段树，把每段中间的九个数扒下来，剩下的继续向下递归建树，深度仍然是 \(\log n\) 的。

我们分别处理出每一段上每个点到中间九个点的最短路和中间九个点到段上每个点的最短路，直接 \(\mathcal{O(n)}\) bfs 就行。查询时我们要先递归找到一段使得 \(x\) 与 \(y\) 在中间九个数的两边或者在其中，也就是点 \(x\) 和点 \(y\) 在猫树上的 lca 那一段，然后遍历中间 9 个点作为中途点时 \(x\) 到 \(y\) 的距离，取 min 就做完了。

这道题时间消耗主要在建树上，我们 bfs 的常数要尽可能的小，反向建边（每个点到中间九个点）时最好提前把边连上。还有就是一种最短路的更新可能超出当前段的范围，分别向左右扩展 30 即可。

细节还挺多的，在不影响观感的前提下加了尽量多的注释，代码看不懂可以评论问我。

点击查看代码

#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 = 1e5 + 35, M = 1e5 + 30;
const int maxn = 1e8;
int n, m, res;
int f[18][10][N], g[18][10][N], dis[N], zc[N], vis[N];
bool yz[N];
vector<int>e[N];
namespace Wisadel
{void Wbfs(int x, int l, int r){// 正着的，x -> vqueue<int> q;int LL = max(l - 30, 0), RR = min(r + 30, M);fill(dis + LL, dis + RR + 1, maxn);fill(yz + LL, yz + RR + 1, 0);// 扩大边界 + 初始化dis[x] = 0, yz[x] = 1;q.push(x);while(q.size()){int u = q.front(); q.pop();int tt = u, zct = 0;while(tt){// 暴力出发点的每一位if(tt % 10) zc[++zct] = tt % 10;tt /= 10;}sort(zc + 1, zc + 1 + zct);zct = unique(zc + 1, zc + 1 + zct) - zc - 1;// 离散化一下（好像是负提升？）fo(i, 1, zct){// bfs 最短路，可以往大可以往小，注意边界if(u + zc[i] <= RR && !yz[u + zc[i]])yz[u + zc[i]] = 1, dis[u + zc[i]] = dis[u] + 1, q.push(u + zc[i]);if(u - zc[i] >= LL && !yz[u - zc[i]])yz[u - zc[i]] = 1, dis[u - zc[i]] = dis[u] + 1, q.push(u - zc[i]);}}}void Wbfs1(int x, int l, int r){// 反，x <- vqueue<int> q;int LL = max(l - 30, 0), RR = min(r + 30, M);fo(i, LL, RR) e[i].clear();fo(i, LL, RR){// 提前连好边int x = i;dis[i] = maxn, yz[i] = 0;while(x){if(x % 10 && vis[x % 10] != i){vis[x % 10] = i;if(i - x % 10 >= LL)e[i - x % 10].push_back(i);if(i + x % 10 <= RR)e[i + x % 10].push_back(i);}x /= 10;}}dis[x] = 0, yz[x] = 1;q.push(x);while(q.size()){int u = q.front(); q.pop();for(auto v : e[u])if(!yz[v]) yz[v] = 1, dis[v] = dis[u] + 1, q.push(v);}}#define mid ((l + r) >> 1)void Wbuild(int dep, int l, int r){fo(i, -4, 4){// 处理相关距离if(mid + i < l || mid + i > r) continue;Wbfs(mid + i, l, r);fo(j, l, r) f[dep][i + 5][j] = dis[j];Wbfs1(mid + i, l, r);fo(j, l, r) g[dep][i + 5][j] = dis[j];}if(r - l + 1 <= 9) return;// 不大于 9 就不用向下再分了Wbuild(dep + 1, l, mid - 5), Wbuild(dep + 1, mid + 5, r);}int Wq(int dep, int l, int r, int x, int y){if(r - l + 1 <= 9) return f[dep][x - mid + 5][y];// x，y 在一块内if(min(x, y) <= mid + 4 && mid - 4 <= max(x, y)){int ans = maxn;fo(i, 1, 9)// 枚举每个中途点ans = min(ans, f[dep][i][y] + g[dep][i][x]);return ans;}if(max(x, y) < mid - 4) return Wq(dep + 1, l, mid - 5, x, y);if(min(x, y) > mid + 4) return Wq(dep + 1, mid + 5, r, x, y);// 判断该往哪边递归}short main(){// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);freopen("counter.in", "r", stdin) , freopen("counter.out", "w", stdout);Wbuild(1, 0, M);int T = qr;while(T--){n = qr ^ (res + 1), m = qr ^ (res + 1);printf("%d\n", (res = Wq(1, 0, M, n, m)) == maxn ? (res = -1) : res);}return Ratio;}
}
int main(){return Wisadel::main();}