BZOJ #1999 [Noip2007]Core 树网的核 & #2936 [Poi1999]降 水 & #1907 树的路径覆盖 & #1270 [BeijingWc2008]雷涛的小猫

BZOJ #1999 [Noip2007]Core 树网的核

Description

设 $T=(V, E, W)$ 是一个无圈且连通的无向图(也称为无根树),每条边带有正整数的权,我们称 $T$ 为树网(treenetwork),其中 $V, E$ 分别表示结点与边的集合,$W$ 表示各边长度的集合,并设 $T$  有 $n$ 个结点。 路径:树网中任何两结点 $a,b$ 都存在唯一的一条简单路径,用 $d(a,b)$ 表示以 a,b 为端点的路径的长度,它是该路径上各边长度之和。我们称 $d(a,b)$ 为 $a,b$ 两结点间的距离。 一点 $v$ 到一条路径 $P$ 的距离为该点与 $P$ 上的最近的结点的距离:$d(v,P)=min\{d(v,u),u 为路径 P 上的结点\}$。 树网的直径:树网中最长的路径称为树网的直径。对于给定的树网 $T$,直径不一定是唯一的,但可以证明:各直径的中点(不一定恰好是某个结点,可能在某条边的内部)是唯一的,我们称该点为树网的中心。 偏心距 $ECC(F)$:树网 $T$ 中距路径 $F$ 最远的结点到路径 $F$ 的距离,即 。 任务:对于给定的树网 $T=(V, E,W)$ 和非负整数 $s$,求一个路径 $F$,它是某直径上的一段路径(该路径两端均为树网中的结点),其长度不超过 $s$(可以等于 $s$),使偏心距 $ECC(F)$ 最小。我们称这个路径为树网 $T=(V,E,W)$ 的核(Core)。必要时,$F$ 可以退化为某个结点。一般来说,在上述定义下,核不一定只有一个,但最小偏心距是唯一的。 下面的图给出了树网的一个实例。图中,$A-B$ 与 $A-C$ 是两条直径,长度均为 $20$。点 W 是树网的中心,$EF$ 边的长度为 $5$。如果指定 $s=11$,则树网的核为路径 $DEFG$(也可以取为路径 $DEF$),偏心距为 $8$。如果指定 $s=0$(或 $s=1$、$s=2$),则树网的核为结点 $F$,偏心距为 $12$。

Solution

找到一条直径,预处理好每个点的偏心距,从直径中点贪心扩散,选择长的那条边扩展直到核长度达到 $s$ 为止,最后还要更新到两端的距离。

Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int n,S,pre[500005],d[500005],dd[500005],bfsmax=0,bfsres,dfsmax=0,t[500005],m,p[500005];
bool v[500005];
int last[1000005],to[1000005],nextt[1000005],s[1000005],top=0;
void add(int a,int b,int c){
    nextt[++top]=last[a];
    to[top]=b;
    s[top]=c;
    last[a]=top;
}
void bfs(int from){
	memset(pre,0,sizeof(pre));
	memset(d,0,sizeof(d));
	memset(v,0,sizeof(v));
	bfsmax=0;
	queue<int> q;
	q.push(from);
	d[from]=0;
	v[from]=1;
	while (!q.empty()){
		int x=q.front();
		q.pop();
		for (int i=last[x];i;i=nextt[i]){
			int y=to[i];
			if (v[y]){
				continue;
			}
			v[y]=1;
			d[y]=d[x]+s[i];
			pre[y]=x;
			q.push(y);
		}
		if (d[x]>bfsmax){
			bfsmax=d[x];
			bfsres=x;
		}
	}
}
void dfs(int x){
	v[x]=1;
	dfsmax=max(dfsmax,d[x]);
	for (int i=last[x];i;i=nextt[i]){
		int y=to[i];
		if (v[y]){
			continue;
		}
		d[y]=d[x]+s[i];
		dfs(y);
	}
}
int main(){
	n=read();S=read();
	for (int i=1;i<=n-1;i++){
		int a=read(),b=read(),c=read();
		add(a,b,c);
		add(b,a,c);
	}
	bfs(1);
	int a=bfsres;
	bfs(a);
	int b=bfsres;
	memset(d,0,sizeof(d));
	memset(v,0,sizeof(v));
	for (int i=b;i;i=pre[i]){
		v[i]=1;
	}
	for (int i=b;i;i=pre[i]){
		dfsmax=0;
		dfs(i);
		t[i]=dfsmax;
		p[++m]=i;
		dd[m]=d[i];
	}
	reverse(p+1,p+1+m);
	bfs(a);
	for (int i=1;i<=m;i++){
		dd[i]=d[p[i]];
	}
	int l,r;
	for (int i=1;i<=m;i++){
		if (d[p[i]]>=d[b]/2){
			l=r=i;
			break;
		}
	}
	while (1){
		if (dd[r]-dd[l]+min(dd[r+1]-dd[r],dd[l]-dd[l-1])>S||(l==1&&r==m)){
			break;
		}
		
		if (dd[l]-dd[l-1]>dd[r]-dd[r+1]){
			if (l>1&&dd[r]-dd[l-1]<=S){
				l--;
			}else{
				r++;
			}
		}else{
			if (r<m&&dd[r+1]-dd[l]<=S){
				r++;
			}else{
				l--;
			}
		}
	}
	int maxx=0;
	for (int i=l;i<=r;i++){
		maxx=max(maxx,t[p[i]]);
	}
	maxx=max(maxx,max(dd[m]-dd[r],dd[l]-dd[1]));
	cout<<maxx;
}

#2936 [Poi1999]降 水

Description

有这样一块土地,它可以被划分成 $N×M$ 个正方形小块,每块面积是一平方英寸,第 $i$ 行第 $j$ 列的小块可以表示成 $P(i,j)$。这块土地高低不平,每一小块地 $P(i,j)$ 都有自己的高度 $H(i,j)$(单位是英寸)。
一场倾盆大雨后,这块地由于地势高低不同,许多低洼地方都积存了不少降水。假如你已经知道这块土地的详细信息,你能求出它最多能积存多少立方英寸的降水么?

Solution

从边缘开始 BFS,每次选择相邻最低的一块,更新高度并扩展

Code

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,h;
	bool operator < (const node &a) const {  
		return h>a.h;
	}
};
priority_queue<node> q;
int n,m,s[105][105],t[105][105],v[105][105],d[4][2]={{1,0},{-1,0},{0,1},{0,-1}},ans=0;
int main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			cin>>s[i][j];
			t[i][j]=s[i][j];
			if (i==1||i==n||j==1||j==m){
				q.push((node){i,j,s[i][j]});
				v[i][j]=1;
			}
		}
	}
	while (!q.empty()){
		node now=q.top();
		q.pop();
		for (int i=0;i<=3;i++){
			int x=now.x+d[i][0];
			int y=now.y+d[i][1];
			if (v[x][y]){
				continue;
			} 
			if (x<=1||x>=n||y<=1||y>=m){
				continue;
			}
			s[x][y]=max(s[x][y],now.h);
			v[x][y]=1;
			q.push((node){x,y,s[x][y]});
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			ans+=s[i][j]-t[i][j];
		}
	}
	cout<<ans;
}

 

#1907 树的路径覆盖

Description

Solution

贪心

Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int T,n,m,last[200005],to[200005],nextt[200005],v[200005],size[200005],top=0,ans=0;
void add(int a,int b){
    nextt[++top]=last[a];
    to[top]=b;
    last[a]=top;
}
void dfs(int x,int fa){
	size[x]=1;
	int sons=0;
	for (int i=last[x];i;i=nextt[i]){
		if (to[i]==fa){
			continue;
		}
		dfs(to[i],x);
		size[x]+=size[to[i]];
		if (!v[to[i]]){
			sons++;
		}
	}
	if (sons==1){
		size[x]--;
	}
	if (sons>=2){
		size[x]-=2;
		v[x]=1;
	}
}
int main(){
	T=read();
	while (T--){
		memset(last,0,sizeof(last));
		memset(to,0,sizeof(to));
		memset(nextt,0,sizeof(nextt));
		memset(v,0,sizeof(v));
		memset(size,0,sizeof(size));
		top=0;
		n=read();
		for (int i=1;i<=n-1;i++){
			int a=read(),b=read();
			add(a,b);
			add(b,a);
		}
		dfs(1,0);
		cout<<size[1]<<endl;
	}
}

#1270 [BeijingWc2008]雷涛的小猫

Description

雷涛的小猫雷涛同学非常的有爱心,在他的宿舍里,养着一只因为受伤被救助的小猫(当然,这样的行为是违反学生宿舍管理条例的)。  在他的照顾下,小猫很快恢复了健康,并且愈发的活泼可爱了。可是有一天,雷涛下课回到寝室,却发现小猫不见了!经过一番寻找,才发现她正趴在阳台上对窗外的柿子树发呆…在北京大学的校园里,有许多柿子树,在雷涛所在的宿舍楼前,就有 $N$ 棵。并且这 $N$ 棵柿子树每棵的高度都是 $H$。冬天的寒冷渐渐笼罩了大地,树上的叶子渐渐掉光了,只剩下一个个黄澄澄的柿子,看着非常喜人。而雷涛的小猫恰好非常的爱吃柿子,看着窗外树上的柿子,她十分眼馋,于是决定利用自己敏捷的跳跃能力跳到树上去吃柿子。小猫可以从宿舍的阳台上跳到窗外任意一棵柿子树的树顶。之后,她每次都可以在当前位置沿着当前所在的柿子树向下跳 $1$ 单位距离。当然,小猫的能力远不止如此,她还可以在树之间跳跃。每次她都可以从当前这棵树跳到另外的任意一棵,在这个过程中,她的高度会下降 $Delta$ 单位距离。每个时刻,只要她所在的位置有柿子,她就可以吃掉。整个“吃柿子行动”一直到小猫落到地面上为止。雷涛调查了所有柿子树上柿子的生长情况。饱很想知道,小猫从阳台出发,最多能吃到多少柿子?他知道写一个程序可以很容易的解决这个问题,但是他现在懒于写任何代码。于是,现在你的任务就是帮助雷涛写一个这样的程序。左图是 $N=3$,$H=10$,$Delta=2$ 的一个例子。小猫按照图示路线进行跳跃,可以吃到最多的 $8$ 个柿子。

Solution

水 DP,$f[x]$ 表示 $x$ 高度最大值,$g[x]$ 表示当前高度 $x$ 树最大值。

#include<bits/stdc++.h>
using namespace std;
int n,h,d,s[2005][2005],f[2005],g[2005];
int main(){
	cin>>n>>h>>d;
	for (int i=1;i<=n;i++){
		int m,x;
		cin>>m;
		while (m--){
			cin>>x;
			s[i][x]++;
		}
	}
	g[h+1]=0;
	for (int i=h;i>=1;i--){
		for (int j=1;j<=n;j++){
			g[j]=max(g[j],f[min(i+d,h+1)])+s[j][i];
			f[i]=max(f[i],g[j]);
		}
	}
	cout<<f[1];
}

评论

  1. Void_struct
    Windows Edge
    5月前
    2020-5-13 7:35:21

    嗯哼哼啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

    • solstice23 博主
      Windows Chrome
      已编辑
      5月前
      2020-5-13 7:37:00

      把别人评论区变臭的屑,自裁,请

  2. DrBlack
    Windows Chrome
    5月前
    2020-5-12 21:43:32

    真的厉害enmm…

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: Telegram @AmashiroNatsukiEars_NoWord Sticker
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
AmashiroNatsukiEars
小恐龙
花!
上一篇
下一篇