首页 > 其他分享 >Living-Dream 系列笔记 第65期

Living-Dream 系列笔记 第65期

时间:2024-07-25 17:28:29浏览次数:19  
标签:Living cur int siz fa 65 max Dream mx

HDU 6567

首先我们发现每棵树内部的距离已经固定,只有经过新边的路径才会产生贡献。

又因为重心到树上所有节点的距离和最小,所以我们连接两树重心。

然后我们想到一个经典套路:计算距离可以不枚举点,只枚举边。于是我们枚举每条边,计算出它们各自被经过的次数,再求和即为答案。

维护 \(siz_x\) 表示以 \(x\) 为根的子树大小,则由乘法原理,易得过 \(x \to fa_x\) 这条边的次数即为 \(siz_x \times (n-siz_x)\)。\(O(n)\)。

code
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;

const int N=2e5+5;
vector<int> G[N];
int n,ans,sum;
int ctr1,ctr2;
int siz[N],mx[N];
bool tag[N];

void get_ctr(int cur,int fa,int f){
	siz[cur]=1;
	for(int i:G[cur]){
		if(i!=fa){
			get_ctr(i,cur,f);
			siz[cur]+=siz[i];
			mx[cur]=max(mx[cur],siz[i]);
		}
	}
	mx[cur]=max(mx[cur],sum-siz[cur]);
	if(mx[cur]*2<=sum){
		if(f==1) ctr1=cur;
		else ctr2=cur;
	} 
}
void mark(int cur,int fa){
	tag[cur]=1,sum++;
	for(int i:G[cur])
		if(i!=fa)
			mark(i,cur);
}
void dfs(int cur,int fa){
	siz[cur]=1;
	for(int i:G[cur])
		if(i!=fa)
			dfs(i,cur),siz[cur]+=siz[i];
}

signed main(){
	cin>>n;
	for(int i=1,u,v;i<=n-2;i++)
		cin>>u>>v,
		G[u].push_back(v),
		G[v].push_back(u);
	mark(1,0);
	get_ctr(1,0,1);
	memset(siz,0,sizeof siz);
	memset(mx,0,sizeof mx);
	for(int i=1;i<=n;i++){
		if(!tag[i]){
			sum=n-sum;
			get_ctr(i,0,2);
			break;
		}
	}
	G[ctr1].push_back(ctr2),G[ctr2].push_back(ctr1);
	//cout<<ctr1<<' '<<ctr2<<'\n';
	memset(siz,0,sizeof siz),dfs(1,0);
	for(int i=1;i<=n;i++)
		ans+=siz[i]*(n-siz[i]);
	cout<<ans;
	return 0;
}

CF708C

考虑 bf 怎么做。

我们可以枚举每个点 \(i\) 作为根,维护最大子树大小 \(mx_i\)。

若 \(mx_i > \frac{n}{2}\),则尝试在 \(i\) 的重儿子 \(son_i\) 中分离一棵不超过 \(\frac{n}{2}\) 的子树 \(part_{son_i}\),分离后剩余的部分 \(x = mx_i-part_{son_i}\) 若满足 \(x \le \frac{n}{2}\),则说明 \(i\) 可为重心。

\(O(n^2)\)。

然后我们发现与其枚举 \(i\) 为重心,不如直接让整棵树的重心作为根,去发掘性质(套路:换根 dp 避免枚举)。

我们效仿求树的中心的换根 dp,维护 \(part1_i,part2_i\) 分别表示点 \(i\) 最大 / 次大的不超过 \(\frac{n}{2}\) 的子树大小,\(up_i\) 表示点 \(i\) 子树外最大的不超过 \(\frac{n}{2}\) 的子树大小,并依然像那样 dp 即可(具体实现见 code)。

最后,因为是以重心为根,所以子树内大小不会超过限制,于是仅需检查子树外切割后是否合法即可。

\(O(n)\)。

code
#include<bits/stdc++.h>
using namespace std;

const int N=4e5+5;
int n,rt;
vector<int> G[N];
int mx[N],siz[N];
int part1[N],part2[N],up[N];

void get_ctr(int cur,int fa){
	siz[cur]=1;
	for(int i:G[cur]){
		if(i==fa) continue;
		get_ctr(i,cur);
		siz[cur]+=siz[i];
		mx[cur]=max(mx[cur],siz[i]);
	}
    mx[cur]=max(mx[cur],n-siz[cur]);
    if(mx[cur]<=n/2) rt=cur;
}
void dfsd(int cur,int fa){
	siz[cur]=1;
	for(int i:G[cur]){
		if(i==fa) continue;
		dfsd(i,cur);
		siz[cur]+=siz[i];
		if(siz[i]>n/2) continue;
		if(siz[i]>part1[cur])
			part2[cur]=part1[cur],
			part1[cur]=siz[i];
		else if(siz[i]>part2[cur])
			part2[cur]=siz[i];
	}
}
void dfsu(int cur,int fa,int maxx){
	up[cur]=maxx;
	for(int i:G[cur]){
		if(i==fa) continue;
		//if(siz[i]>n/2) continue;
		if(n-siz[cur]<=n/2) maxx=max(maxx,n-siz[cur]);
		if(siz[i]!=part1[cur])
			dfsu(i,cur,max(maxx,part1[cur]));
		else
			dfsu(i,cur,max(maxx,part2[cur]));
	}
}

int main(){
	cin>>n;
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,
		G[u].push_back(v),
		G[v].push_back(u);
	get_ctr(1,0);
	dfsd(rt,0);
	dfsu(rt,0,0);
	for(int i=1;i<=n;i++){
		if((n-siz[i]-up[i]<=n/2)||rt==i)
			cout<<"1 ";
		else
			cout<<"0 ";
	}
	return 0;
}

P1522

显然,

\[两个牧场连边的直径最大值 = \max(第一个牧场原直径,第二个牧场原直径,连新边的两点到离各自最远点的距离 + 连边两点之间距离) \]

(因为若直径两端点不过连新边的两点,则原直径一定更长,否则一定后者更长)

于是我们维护 牧场直径(由下个信息取 max 可得,用并查集维护联通性,存在根下面)、牧场每个点到各自最远点距离(floyd + 取 max)即可。

code
#include<bits/stdc++.h>
using namespace std;
#define pdd pair<double,double>
#define ll long long 

const int N=155;
const ll INF=1e9;
int n,fa[N];
double ans;
pdd p[N];
double dis[N][N],l[N],d[N];

void floyd(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(dis[i][k]+dis[k][j]<dis[i][j])
					dis[i][j]=dis[i][k]+dis[k][j];
}
double gdis(pdd a,pdd b){
	return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
int fnd(int x){ return (x==fa[x]?x:fa[x]=fnd(fa[x])); }
void uni(int x,int y){ x=fnd(x),y=fnd(y); if(x!=y) fa[x]=y; }

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++) cin>>p[i].first>>p[i].second;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=(i==j?0:INF); 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char c; cin>>c;
			if(c=='1')
				dis[i][j]=gdis(p[i],p[j]),uni(i,j);
		}
	}
	floyd();
	for(int i=1;i<=n;i++){
		double mx=-1e9;
		for(int j=1;j<=n;j++)
			if(dis[i][j]!=INF&&dis[i][j]>mx)
				mx=dis[i][j];
		d[i]=mx;
		int r=fnd(i);
		l[r]=max(l[r],d[i]);
	}
	ans=INF;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(dis[i][j]==INF)
				ans=min(ans,max(d[i]+d[j]+gdis(p[i],p[j]),max(l[fnd(i)],l[fnd(j)])));
	cout<<setprecision(6)<<fixed<<ans;
	return 0;
}

标签:Living,cur,int,siz,fa,65,max,Dream,mx
From: https://www.cnblogs.com/XOF-0-0/p/18323754

相关文章

  • .h264 .h265 压缩率的直观感受
    1.资源文件  https://download.csdn.net/download/twicave/89579327上面是.264.265和原始的YUV420文件,各自的大小。2.转换工具:2.1.h264.h265互转可以使用ffmpeg工具:[email protected]命令行参数:ffmpeg-iTennis1080p.h264-c:vlibx265-preset......
  • 题解—[ABC265E] Warp
    题面简单计数DP。由于数据范围很大,所以状态不能常规设置为\(dp_{i,j}\)。注意到\(n\)只有\(300\),考虑设\(dp_{i,j,k}\)表示三种行走方法分别使用\(i\),\(j\),\(k\)次的路径数量。状态转移很简单,先计算出来当前所在位置,如果是障碍就跳过,否则$dp_{i,j,k}=dp_{i-1,j,k}+dp......
  • Living-Dream 系列笔记 第64期
    树的重心当\(u\)作为根时,其节点数最大的子树最小,则称\(u\)为树的重心。性质一:节点数最大的子树的节点数不超过\(\frac{节点总数}{2}\)。(反证法,若某重心\(u\)的节点数最大的子树的节点数超过\(\frac{节点总数}{2}\),则将其一个子节点提起来会更优)性质二:至多两个且一......
  • Living-Dream 系列笔记 第63期
    树的中心当选取树上节点\(u\)为根时,最长链最短,则称\(u\)为树的中心。性质一:至多\(2\)个且一定相邻。性质二:一定位于树的直径上。性质三:若一棵树有多条直径,则它们必定交于树的中心。性质四:树的中心为根时,根到直径两端点分别为最长/次长链。U392706板子。......
  • MOTOROLAVME172PA-652SE 嵌入式控制器
    高性能控制:MOTOROLAVME172PA-652SE模块具有高性能的控制能力,可以用于实现复杂的工业自动化系统的控制和监测。多功能模块:该模块可能具备多种功能,如输入/输出控制、数据采集、信号处理等,可适应不同的应用需求。可编程性:MOTOROLAVME172PA-652SE模块通常支持编程和定制化,使......
  • Living-Dream 系列笔记 第62期
    树的直径:定义:树上两个距离最远的点形成的简单路径(不重复走一条边/点)性质:不唯一。树的直径的端点一定是度数为\(1\)的点。证明:显然。树的直径若有多条,则必交汇于一点,即中心。证明:首先每条直径只能交于端点(因为是一棵树,一个节点不能有两个父节点),然后此交点必定......
  • Qmi8658a姿态传感器使用心得(4)linux
    1.FIFO结构与大小FIFO数据可以包含陀螺仪和加速度计数据,通过SPI/I2C/I3C接口以突发读模式读取。FIFO大小可配置为16样本、32样本、64样本或128样本(每个样本为6字节)。2.FIFO模式Bypass模式:禁用FIFO功能。FIFO模式:FIFO满后停止写入新数据,直到主机读取FIF......
  • office365.sharepoint 中的 moveto 或 move_to_using_path 是否处于活动状态?
    我正在尝试使用Office365-REST-Python-Client中的示例将文件从一个文件夹移动到另一个文件夹,但它不起作用:fromoffice365.sharepoint.client_contextimportClientContextfromoffice365.sharepoint.files.move_operationsimportMoveOperationsfromtestsimporttest_t......
  • Linux C++ 065-设计模式之组合模式
    LinuxC++065-设计模式之组合模式本节关键字:Linux、C++、设计模式、组合模式相关库函数:概念组合模式(CompositePattern),又叫做部分-整体模式,使得用户对单个对象和组合对象的使用具有一致性。它使我们树型结构的问题中,模糊了简单元素和复杂元素的概念,客户程序可以像处理......
  • Qmi8658a姿态传感器使用心得(3)linux
    中断模式1.说明:SyncSample模式:CTRL7.bit7(SyncSample)==1启用SyncSample模式。INT1:CTRL9握手信号、运动事件中断(AnyMotion,NoMotion,SignificantMotion,Pedometer,Tap)。INT2:DRDY信号。非SyncSample模式:CTRL7.bit7(SyncSample)==0启用非SyncSample模式。......