来讲点大家想听的:P17834
[CSP-S 2026] 研发基地 / hub
CSP 好好玩啊!啊!坑坏了!
思维难度中等。
代码难度超高。
简述题意
从一颗树里选择 \(k\) 个点,这 \(k\) 个点的连通块不超过两个。
使得剩下没选的 \(n-k\) 个点到这 \(k\) 个点的距离的最大值最小。
算法分析
我们发现“最大值最小”,一眼就是二分的条件啊!
我们直接考虑二分。
对啥二分呢?
对题目里的通勤半径二分也就是“\(n-k\) 个点到这 \(k\) 个点的距离的最大值”。
我们看能不能在这里面找出 \(k\) 个点使得满足条件。
于是开始考虑当二分到 \(rad\) 时可不可以。
check
首先我们去掉绝对可以不用管的东西,最外面的 \(rad\) 层叶子。
因为无论如何这个都可以满足。
这里要引进一个概念“关键点”。
“关键点”:就是必须要选的点。
所以去掉的点都是非关键点,易证明剥叶子后留下剩下的点一定满足条件。
设:剩下的点为 \(cnt\)。
如果 \(cnt\le k\) 好办,直接从其他地方补足即可,随便几个都可以,反正满足。
但反之就不好做了,要删掉多余的,咋办?
不能删掉剩下的那个图的叶子,也不能删除多叉节点,因为删掉叶子就会不满足条件,删除多叉节点就会不止 \(2\) 个连通块了,至少有 \(3\) 个。
所以我们只能删除每一条连续二度链。
而且长度要大于等于要删除点的个数,因为要不删不了,要不不止 \(2\) 个连通块。
于是我就转化成了链上操作。
进链
对于每一条链,我们可以使用滑动窗口然后依次判断是否可行。
但是依次判断会超时的,最坏情况会有 \(O(n^2)\)。
所以我们需要 \(O(1)\) 判断每个窗口是否可行。
我们可以把整个窗口划分成两个部分,一个部分离左边没删掉的点更近,另一个部分离右边没删掉的点更近,而且以正中间为分割线,于是我们可以把它拆成两个窗口。
于是只要判断左窗口的最右边和右窗口的最左边即可。
于是我们做完了。
呼。汗。
code
你们喜欢的 code 环节:
#include
using namespace std;
typedef long long ll;
const ll N=1e6+1,INF=0x541254484852;
int c,tc,t,n,k,u,v,deg[N],DEG[N],q[N],in_core[N],h[N];
basic_stringE[N];
bool vis[N];
void peel(int dep){
int l=1,r=0;
for(int i=1;i<=n;i++)
DEG[i]=E[i].size(),in_core[i]=h[i]=0;
for(int i=1;i<=n;i++)
if(DEG[i]<=1)
in_core[i]=1,q[++r]=i;
while(l<=r){
int u=q[l++];
for(auto v:E[u]){
if(in_core[v])
continue;
h[v]=max(h[v],in_core[u]),DEG[v]--;
if(DEG[v]==1&&in_core[u]chain,int del,int rad){
int len=chain.size();
if(lendiff(m+1,0);
for(int i=0;ichain;
while(true){
int nxt=-1;
for(int v:E[start])
if(!in_core[v]&&DEG[v]==2&&v!=pre){
nxt=v;
break;
}
if(nxt==-1)
break;
pre=start,start=nxt;
}
pre=0;
int cur=start;
while(cur!=0){
vis[cur]=true,chain.push_back(cur);
int nxt=0;
for(int v:E[cur])
if(!in_core[v]&&DEG[v]==2&&v!=pre){
nxt=v;
break;
}
pre=cur,cur=nxt;
}
if(solve_on_the_chain(chain,rem,rad))
return true;
}
return false;
}
void solve(){
for(int i=1;i<=n;i++)
E[i].clear();
cin>>n>>k;
for(int i=1;i>u>>v,E[u].push_back(v),E[v].push_back(u);
if(n==k){
cout<<0<>1;
if(check(mid))
r=mid-1,ans=mid;
else
l=mid+1;
}
cout<>c>>tc;
while(tc--)
solve();
}
后记
中途 TLE 了。
但是把 vector 换成 basic_string 后跑的飞快。
这是一个教训。
我调了 37 发呀!
算不算滥用测评啊?
可以顶一下吗?我写了两星期qwq。
不要直接抄啊!我讨厌验证码qwq。
原文地址: http://www.cveoy.top/t/topic/qHXj 著作权归作者所有。请勿转载和采集!