洛谷每日一练5.11--P4145+P2015+P2195(图+线段树+DP)

Rowena ·

更新时间:2024-09-20

· 606 次阅读

目录P4145题意：思路：P2015题意：思路：P2195题意：思路： P4145 题意：

给一个长度为n的数列，有两个操作：给一个长度为n的数列，有两个操作：给一个长度为n的数列，有两个操作：
①将[L,R]内的数都取平方根(向下取整)①将[L,R]内的数都取平方根(向下取整)①将[L,R]内的数都取平方根(向下取整)
②求[L,R]的区间和②求[L,R]的区间和②求[L,R]的区间和

思路：

暴力单点修改可过暴力单点修改可过暴力单点修改可过
可知若对1取平方根也是1，可以把这种操作省略可知若对1取平方根也是1，可以把这种操作省略可知若对1取平方根也是1，可以把这种操作省略
当要修改这个区间时，若该区间最大值小于等于1，则不修改当要修改这个区间时，若该区间最大值小于等于1，则不修改当要修改这个区间时，若该区间最大值小于等于1，则不修改

#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,q;
ll a[N];
struct Node{
	int l,r;
	ll sum,mx;
}tr[N<<2];
void pushup(int p){
	tr[p].mx = max(tr[p<<1].mx,tr[p<<1|1].mx);
	tr[p].sum = tr[p<<1].sum + tr[p<> 1;
	build(p<<1,l,mid);
	build(p<= L&& r > 1;
	ll ans = 0;
	if(L <= mid) ans += query(p< mid) ans += query(p<> 1;
	if(L <= mid && tr[p< 1) update(p< mid && tr[p< 1) update(p<<1|1,L,R);
	pushup(p);
}
int main(){
	scanf("%d",&n);
	for(int i = 1;i  r) swap(l,r);
		if(op == 0) update(1,l,r);
		else printf("%lld\n",query(1,l,r));
	}
	return 0;
}

P2015 题意：

给一颗以1为根的树给你，每条树边都有一个权重给一颗以1为根的树给你，每条树边都有一个权重给一颗以1为根的树给你，每条树边都有一个权重
要求你把这颗以1为根的树砍剩下m条边,使得这棵树边权之和最大要求你把这颗以1为根的树砍剩下m条边,使得这棵树边权之和最大要求你把这颗以1为根的树砍剩下m条边,使得这棵树边权之和最大

思路：

和P2014一样，树形背包，不过这题权重在边上，而不是在点和P2014一样，树形背包，不过这题权重在边上，而不是在点和P2014一样，树形背包，不过这题权重在边上，而不是在点
注意转移方程的不同注意转移方程的不同注意转移方程的不同

#include 
#include 
#include 
using namespace std;
const int N = 105;
int n,m,head[N],idx;
struct Node{
	int to,nex,w;
}e[N<= 1;j--){
			//枚举子节点选取边的数量
			for(int k = 0;k < j;k++){
				f[u][j] = max(f[u][j],f[u][j-k-1]+f[v][k]+e[i].w);
			} 
		} 
	}
} 
int main(){
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(int i = 1,u,v,w;i < n;i++){
		scanf("%d%d%d",&u,&v,&w);
		add_edge(u,v,w);add_edge(v,u,w);
	}
	dfs(1,0);
	printf("%d\n",f[1][m]);
	return 0;
}

P2195 题意：

给一个有n个点，m条边的森林，有q组操作给一个有n个点，m条边的森林，有q组操作给一个有n个点，m条边的森林，有q组操作
有两种类型的操作：有两种类型的操作：有两种类型的操作：
①①① 111 xxx ：询问x所在树的直径：询问x所在树的直径：询问x所在树的直径
②②② 222 xxx yyy ：若x和y本来在一棵树忽略这次操作，否则将x所在树和y所在树：若x和y本来在一棵树忽略这次操作，否则将x所在树和y所在树：若x和y本来在一棵树忽略这次操作，否则将x所在树和y所在树
用一条边连成一颗新树，并要求这颗新树的直径在所有方案中最小用一条边连成一颗新树，并要求这颗新树的直径在所有方案中最小用一条边连成一颗新树，并要求这颗新树的直径在所有方案中最小

思路：

首先对于一棵树的用并查集连起来，并且求出每颗树的直径；重点在于第二个操作首先对于一棵树的用并查集连起来，并且求出每颗树的直径；重点在于第二个操作首先对于一棵树的用并查集连起来，并且求出每颗树的直径；重点在于第二个操作
如果让新树的直径最小,最小是多少？如果让新树的直径最小,最小是多少？如果让新树的直径最小,最小是多少？
答案是max(⌈dima[x]/2⌉答案是max(\lceil dima[x]/2 \rceil答案是max(⌈dima[x]/2⌉ + ⌈dima[y]/2⌉\lceil dima[y]/2 \rceil⌈dima[y]/2⌉+1+1+1,max(dima[x],dima[y])max(dima[x],dima[y])max(dima[x],dima[y]))
为什么是这个?为什么是这个?为什么是这个?
因为选择相连的两个点应该在两颗树的直径上，且应该在直径的中间因为选择相连的两个点应该在两颗树的直径上，且应该在直径的中间因为选择相连的两个点应该在两颗树的直径上，且应该在直径的中间
所以是两颗树的直径向上取整之和再加上连边，其次为什么还要和取两个直径取max所以是两颗树的直径向上取整之和再加上连边，其次为什么还要和取两个直径取max所以是两颗树的直径向上取整之和再加上连边，其次为什么还要和取两个直径取max
可以想象当一颗直径很大的树连接一个点时，答案应该还是这颗大树的直径可以想象当一颗直径很大的树连接一个点时，答案应该还是这颗大树的直径可以想象当一颗直径很大的树连接一个点时，答案应该还是这颗大树的直径

#include 
#include 
#include 
#include 
using namespace std;
const int N = 3e5+10;
int n,m,q,fa[N],len;
inline int read() {
	char ch=getchar();
	int x=0,cf=1;
	while(ch'9') {
		if(ch=='-') cf=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*cf;
}
struct Node{
	int to,nex;
}e[N<= d1) d2 = d1,d1 = d;
		else if(d > d2) d2 = d;
	} 
	len = max(len,d1+d2);
	return dist;
}
void cal(int root){
	len = 0;
	dfs(root,0);
	dima[root] = len;
}
int main(){
	memset(head,-1,sizeof(head));
	n = read(),m = read(),q = read();
	for(int i = 1;i <= n;i++) fa[i] = i;
	for(int i = 0,u,v;i < m;i++){
		u = read(),v = read();
		fa[find(u)] = find(v);
		add_edge(u,v),add_edge(v,u);
	}
	for(int i = 1;i >1) + ((dima[y]+1)>>1) + 1,max(dima[x],dima[y]));
			fa[find(x)] = y,dima[find(x)] = ans;
		}
	} 
	return 0;
}