CSP-S 2026题解

· · 题解

闲话

![image.png](https://cdn.luogu.com.cn/upload/image_hosting/lspw04si.webp) ## 前言 前两题是自己的考场上的做法,后两题参考了题解区个人认为最佳的做法,做了补充,写的会更加详细,比较适合 $5 \sim 7$ 级能力选手阅读学习。 T3: https://www.luogu.com.cn/article/1ukkypnp T4: https://www.luogu.com.cn/article/st6ljm36 ## crystal ### 题意 给 $n$ 个数,可以做至多 $m$ 次给某数 $+1$ 操作,最大化相同数数量。 $n\le 5\times 10^5$。 ### 分析 注意到最优解必然是排序后一段区间,且目标数字必然在 $a$ 数组里。枚举目标并动态维护这个区间的花费,双指针即可。 ### 代码 ```cpp #include <bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define ll long long using namespace std; const int N=5e5+10; ll n,m,a[N],l,r,cst,ans; int main(){ freopen("crystal.in","r",stdin); freopen("crystal.out","w",stdout); scanf("%lld%lld",&n,&m); rep(i,1,n) scanf("%lld",&a[i]); sort(a+1,a+n+1); l=1,r=0; while(r<n){ if(cst<=m) ans=max(ans,r-l+2); else { while(cst>m){ cst-=a[r+1]-a[l]; l++; } ans=max(ans,r-l+2); } r++; cst+=(a[r+1]-a[r])*(r-l+1); } cout<<ans; return 0; } ``` ## subway ### 题意 题面真傻逼,我发现我居然三句话说不清楚题意。 最神的是,这个人也是追忆的出题人,还是今年 J 组 T1、T2、T3、S 组 T1 的出题人。 有 $m$ 个地铁站,各有一个权值 $w$,代表从地铁口走下地铁站的时间。 有 $n$ 条地铁线路,双向经过若干互不相同的站。对这第 $i$ 条线里每个站 $a_{i,j}$,从站厅走到该线路上要消耗时间 $t_{i,j}$。 同一站最多被 $d$ 条线路经过,保证地铁网络连通。 乘坐地铁本身不计步行时间,换乘时需从原线路站台走到站厅,再从站厅走到另一线路站台。 有 $q$ 次询问,每次给出 $x,y$,求从第 $x$ 个站的地铁口出发,到第 $y$ 个站的地铁口,所需的最小总步行时间,包括进出站及所有换乘的步行时间。 $n\le 500,m \le 5\times 10^5,d\le 20$。 ### 分析 注意到题目保证任意两点可以通过地铁到达。而且 $n \le 500$,考虑对地铁建模比较好。 题目给了点线距,我们只需要搞定线线距。 任意两条地铁线路可以把他们的距离跑出来。由于 $d \le 20$,只要枚举每个点,看经过其的任意两条线路,可以用点与线路的距离来更新线线距。之后对地铁跑一次 floyd 就能找出任意两条线路之间距离。 询问就是看 $u$ 和 $v$ 两个点分别走哪条线路,答案就是点线距线线距以及 $w_u+w_v$ 之和最小值。这个 $w$ 没用,完全可以不给。 时间复杂度 $O(n^3+(m+q)d^2)$。 ### 代码 ```cpp #include <bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define ll long long #define pil pair<int,long long> using namespace std; const int M=5e5+10,N=510; int casee,n,m,d,Q; ll inf; struct node{ ll w; vector <pil> vec; }a[M]; ll f[N][N]; int main(){ freopen("subway.in","r",stdin); freopen("subway.out","w",stdout); scanf("%d%d%d%d%d",&casee,&n,&m,&d,&Q); rep(i,1,m) scanf("%lld",&a[i].w); rep(i,1,n){ int k;scanf("%d",&k); rep(j,1,k){ int id;ll len; scanf("%d%lld",&id,&len); a[id].vec.push_back({i,len}); } } memset(f,0x3f,sizeof(f)); inf=f[0][0]; rep(i,1,n) f[i][i]=0; rep(i,1,m){ for(auto prs:a[i].vec){ for(auto prt:a[i].vec){ int s=prs.first,t=prt.first; if(s==t) continue; f[s][t]=min(f[s][t],prs.second+prt.second); f[t][s]=min(f[t][s],prs.second+prt.second); } } } rep(k,1,n){ rep(i,1,n){ if(k==i) continue; if(f[i][k]>=inf) continue; rep(j,1,n){ if(k==i||i==j||j==k||f[k][j]>=inf) continue; f[i][j]=min(f[i][j],f[i][k]+f[k][j]); } } } while(Q--){ int u,v; ll ans=inf; scanf("%d%d",&u,&v); for(auto prs:a[u].vec){ for(auto prt:a[v].vec){ int s=prs.first,t=prt.first; ans=min(ans,a[u].w+a[v].w+prs.second+prt.second+f[s][t]); } } printf("%lld\n",ans); } return 0; } ``` ## migrate ### 题意 给定 $n$ 个位置 $x_i$,以及一个 $d$,表示从一个点 $i$ 能一步跳到 $j$ 当且仅当 $|x_i-x_j| \le d$。 对这样的无序对 $(u,v)$ 计数:从 $u$ 起跳到 $v$,最短路径走法数恰为 $2$。 $n \le 2\times 10^6$。 ### 分析 以下钦定 $u \le v$。 考虑路径 $u \to v$ 和 $u \leftarrow v$,每一步都要尽力跳(如果最后一步尽力跳会跳过终点,就可以不尽力,直接到终点即可)。 如果这两条路径经过的点完全相同,说明 $(u,v)$ 只有一种走法。 观察这两条路径,我们可以发现,$u \to v$ 这条路径由于每次都是要跳到下一个最远能到的,也就是说其字典序一定是最大的。同理,$u \leftarrow v$ 的字典序一定是最小的。 我们要求只存在两种路径,换句话说,$u \to v$ 这条与 $u \leftarrow v$ 的不相等,且中间不能夹别的路径。 显然,他们只能有**某一位**有差别,且只能差 $1$。 说句题外话,这个由特殊性质 B 已经能大概推出来了。 你可以想象,存在某个平台(一段区间),只要上了这个平台,下一步尽全力跳,都只能跳到同一个终点。这也就会造成路径的多样。 所以,希望路径只有两条,那么只能存在一个这样的平台,且平台里只能由两座岛屿,那也就只能是 $i$ 和 $i+1$ 了。(这么讲应该很浅显了吧) 接下来考虑计数,枚举这样的 $(i+1,i)$,考虑其左边有多少能作为起点的点、右边有多少能作为终点的点。 可以双指针处理出每个点尽力往左、右跳能到最远的点 $l_i$ 和 $r_i$。 从左往右做和从右往左做是对称的,改几个参数、变量名即可。细节参看代码,这里只讲解从左往右。 设 $f_i$ 为只能通过一种最短走法走到 $i$ 的起点 $u$ 个数。 设 $g_i$ 为跳到 $i$ 和 $i+1$ 的最短路都唯一,且一直尽力跳最后跳到 $i+1$ 的起点 $u$ 个数。 考虑如何算。首先枚举 $i$ 作为起点的情况,尽力跳,下一步到 $r_i$。 若 $r_i>i$,则 $f_{r_i} \leftarrow f_{r_i}+1$。 若 $r_i-1>i$,则 $g_{r_i-1} \leftarrow g_{r_i-1}+1$。 考虑 $i$ 作为中间点的情况,向后跳一步。 若 $r_i>i$ 且 $l_{r_i}=i$,说明能跳到 $r_i$ 的岛屿之中,最左边是 $i$,故 $f_{r_i} \leftarrow f_{r_i}+f_i$。 若 $r_i-1>i$ 且 $l_{r_i-1}=i$,说明存在了一个形如 $(x+1,x)$ 的东西,$g_{r_i-1} \leftarrow g_{r_i-1}+f_{i}$。 于是做完了,答案是: $$ \sum_{i=1}^{n-1}左边到i+1的贡献 \times 右边到i的贡献 $$ 由于我们 $g_i$ 的定义是跳到 $i$ 的下一个,所以实际计算答案时计算的是: $$ \sum_{i=1}^{n-1}左g_i \times 右g_{i+1} $$ 时间复杂度 $O(n)$。 ### 代码 ```cpp #include <bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define int long long using namespace std; const int N=2e6+10; int n,T,d,cas; int l[N],r[N],x[N]; int f[N],g[N],ans[N]; signed main(){ freopen("migrate.in","r",stdin); freopen("migrate.out","w",stdout); scanf("%lld%lld",&cas,&T); while(T--){ scanf("%lld%lld",&n,&d); rep(i,1,n) scanf("%lld",&x[i]); int p=1; rep(i,1,n){ while(p<=n&&x[p]-x[i]<=d)p++; r[i]=p-1; } p=n; per(i,n,1){ while(p>=1&&x[i]-x[p]<=d)p--; l[i]=p+1; } rep(i,1,n){ if(r[i]>i) f[r[i]]++; if(r[i]-1>i) g[r[i]-1]++; if(r[i]>i&&l[r[i]]==i) f[r[i]]+=f[i]; if(r[i]-1>i&&l[r[i]-1]==i) g[r[i]-1]+=f[i]; } rep(i,1,n+1) ans[i]=g[i],f[i]=g[i]=0; per(i,n,1){ if(l[i]<i) f[l[i]]++; if(l[i]+1<i) g[l[i]+1]++; if(l[i]<i&&r[l[i]]==i) f[l[i]]+=f[i]; if(l[i]+1<i&&r[l[i]+1]==i) g[l[i]+1]+=f[i]; } int res=0; rep(i,1,n-1) res+=ans[i]*g[i+1]; printf("%lld\n",res); rep(i,0,n+1) x[i]=l[i]=r[i]=f[i]=g[i]=ans[i]=0; } return 0; } ``` ## hub ### 题意 给定一棵 $n$ 个点的树,要求选出 $k$ 个点,它们构成不超过两个连通块。要使其余所有点到这两个连通块距离的较小值的最大值最小,即覆盖半径最小。 $k \le n \le 10^6$。 ### 分析 二分答案,考虑 check 一个半径 $r$,先对原树剥去 $r$ 轮叶子,剩下一颗核心树 $C$。 若 $|C| \le k$,直接可行。对其他情况,考虑选择 $C$ 里面若干的点,使得要求达到,即挖去 $C$ 的一个子集 $C'$,且有 $|C'|=|C|-k$。令 $|C'|=d$。 思考需要 $C'$ 中的点具备什么样的性质。 首先,显然 $C'$ 里必然没有度数为 $1$ 的点,即叶子。 其次,$C'$ 中必然没有度数为 $3$ 及以上的点。因为,一旦这样的点被挖去,$C$ 必然被瓦解为至少三个连通块,不符合题意。 于是,$C'$ 里只能存在度数为 $2$ 的点。且由于我们要求挖去 $C'$ 中所有点之后,只能剩下两个连通块,所以 $C'$ 中所有的点,必然构成了一条链。这条链断开后,$C$ 变成两颗子树。 在此可以进行一次剪枝,即若 $d>2r$,则删去这么长的一条链之后,显然有链中点距离最近研发基地的距离都大于 $r$,这是不可行的。 考虑这样的一条链 $1,2,\dots,s-1,s$,选择其中编号 $i+1,i+2,\dots,i+d$,删除它。考虑一开始我们剥去 $r$ 轮叶子中被剥去的一些节点,由于这 $d$ 个节点的删除,导致它们可能已经超出了半径 $r$。 我们称一个节点的悬挂部分,为除了沿着链两端方向延伸出去的两个邻居之外的其他方向,连接着的邻居,由前面的设定可知,它们在一开始被剥去。 也就是说,如果我们选的链里存在这样一个节点,使得它的悬挂部分距离最近的研发基地距离的最大值大于 $r$,那么这条链是不可选的。 考虑 $j$ 的悬挂部分最晚被剥去的那个节点(即最深的)被剥去的时间为 $h_j$,则这个最远的叶子在删掉那条链后距离最近的研发基地的距离,就是: $$ h_j+\min(j-i,i+d+1-j) $$ 一旦存在一个 $j$ 使得这个东西大于 $r$,那么以 $i$ 为开头的这条链就是不可行的。可解出 $i$ 不可行的范围是:$[j+r-h_j-d,i+h_j-r-1]$。当我们遍历到 $j$ 时,给这段区间打上标记,表示该段数值不可作为 $i$。再考虑 $j$ 做终点之时,此时考察 $j-d \ge 0$ 是否被禁用,若否,则找到了一个答案。其中这个打标记的过程,可以用差分数组维护。 预处理出原树中所有点被剥去的时间 $t_i$,并记录原树中节点 $i$ 邻居里,被剥去时间最晚即最深、最靠里的三个点,记为 $a_i,b_i,c_i$,且 $t_{a_i} \ge t_{b_i} \ge t_{c_i}$。若不足则补 $0$。设 $t_i$ 是 $i$ 被剥去的轮数,则 $t_i=t_{b_i}+1$。 对于核心树中可删链中的点而言,必有 $t_{b_i} \ge r+1,t_{c_i} \le r$,即 $a_i,b_i$ 是在链上与其相连接的两点,$c_i$ 是悬挂,所以 $h_i=t_{c_i}$。 每次从一个在 $C$ 里度数为 $1$ 的点开始,跑整条链,找是否存在满足要求的一条。这是 $O(n)$ 的,总复杂度为 $O(n \log n)$。 ### 代码 ```cpp #include <bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) using namespace std; const int N=1e6+10; int T,n,k; int t[N],deg[N],cnt[N]; int ok[N],a[N],b[N],c[N],f[N]; vector <int> g[N]; bool check(int r){ int d=cnt[r+1]-k; if(d<=0) return 1; if(d>2*r) return 0; rep(i,1,n) ok[i]=(t[i]>r+1)&&(t[c[i]]<=r); rep(i,1,n){ if(!ok[i]||ok[a[i]]&&ok[b[i]]) continue; int u=i,v=ok[a[i]]?b[i]:a[i],cur=0,j=0; f[0]=0; while(ok[u]){ ok[u]=0,f[++j]=0; int h=r-t[c[u]],left=max(0,j+h-d),right=j-h-1; if(left<=right) f[left]++,f[right+1]--; if(j>=d){ cur+=f[j-d]; if(!cur) return 1; } int nxt=a[u]^b[u]^v; v=u,u=nxt; } } return 0; } int find(){ int l=0,r=n-1,ans=n-1; while(l<=r){ int mid=(l+r)/2; if(check(mid)) ans=min(ans,mid),r=mid-1; else l=mid+1; } return ans; } signed main(){ freopen("hub.in","r",stdin); freopen("hub.out","w",stdout); ios::sync_with_stdio();cin.tie(0);cout.tie(0); cin>>T>>T; while(T--){ cin>>n>>k; rep(i,1,n-1){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); deg[u]++,deg[v]++; } queue <int> tmp; rep(i,1,n) if(deg[i]==1) t[i]=1,tmp.push(i); while(!tmp.empty()){ int u=tmp.front();tmp.pop(); for(auto v:g[u]) if(--deg[v]==1) t[v]=t[u]+1,tmp.push(v); } rep(i,1,n){ cnt[t[i]]++; for(auto v:g[i]){ if(t[v]>t[a[i]]) swap(v,a[i]); if(t[v]>t[b[i]]) swap(v,b[i]); if(t[v]>t[c[i]]) swap(v,c[i]); } } per(i,n-1,0) cnt[i]+=cnt[i+1]; cout<<find()<<"\n"; rep(i,0,n+1) a[i]=b[i]=c[i]=cnt[i]=deg[i]=t[i]=ok[i]=f[i]=0,g[i].clear(); } return 0; } ```