A. 猴猴吃苹果

题意:给定根节点k,求访问点的顺序,使得每次从上一个点到当前点的权值最大。访问过的点权值为0。权值一样时,输出最小编号

思路:由于是双向边,先求根节点到每一个节点的距离值。在第一轮中,最深的叶节点一定为答案,那么这一条路径就被访问过了,权值变为0,这个叶节点相同路径上的其他点到根节点(最后一个未被标记的点)的权值就改变了。所以从最优的叶节点出发,dfs往上跳,直到访问到已经被访问过的点为止即可。最后排序更新后的权值

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n,k,d[N],tot;
bool vis[N];
struct node{
	int id,val;
}a[N];
vector<int> v[N];
inline bool cmp(node p,node q){
	if(p.val!=q.val)  return p.val>q.val;
	else return p.id<q.id;
}
void dfs1(int p,int fa){
	for(int t:v[p]){
		if(t==fa)  continue;
		d[t]=d[p]+1;
		dfs1(t,p);
	}
}
void dfs2(int p,int fa){
	if(vis[p])  return;
	tot++;
	vis[p]=true;
	for(int t:v[p]){
		if(t==fa||d[t]>=d[p])  continue;
		dfs2(t,p);
	}
}
int main(){
	cin>>n>>k;
	for(int i=1,x;i<n;i++){
		cin>>x;
		v[i].push_back(x);
		v[x].push_back(i);
	}
    dfs1(k,-1);vis[k]=true;
    for(int i=0;i<n;i++){
    	a[i].id=i;a[i].val=d[i];
	}
	sort(a,a+n,cmp);
//	for(int i=0;i<n;i++)  cout<<a[i].id<<" ";
    for(int i=0;i<n;i++){
    	tot=0;
    	dfs2(a[i].id,-1);
    	a[i].val=tot;
//    	cout<<tot<<" "<<a[i].id<<endl;
	}
	sort(a,a+n,cmp);
	cout<<k<<endl;
	for(int i=0;i<n;i++){
		if(a[i].val)
		  cout<<a[i].id<<endl;
	}
	return 0;
}

B. 猴猴吃香蕉

题意:选取n个数中的若干个数,使得它们的乘积为k

思路:计数dp,容易得出f[j]+=f[j/a[i]]的转移方程式。使得a[i]为组成k的一个因子。由于k的范围不可接受,于是筛出k的所有因子,如果a[i]/x能整除,说明这个数能被分解。f[j]+=f[a[i]/t[j]],由于因子较大,且个数趋近根号n,需要离散化

最终dp方程:f[j]+=f[pos[a[i]/t[j]]],答案为f[pos[k]]

C. 猴猴的比赛

题意:给定两棵树,求一个节点x在两棵树中有相同祖先的对数

思路:考虑求出每一个点的子树中的范围[L,R](连续的),对于另一颗树而言,每次处理一个点答案计数完成后,就将这个点在第一棵树中的位置标记为1。答案计数为所有父节点[L,R]中1的数量。注意在遍历子节点时,需要减去子树所有点的[L,R]中1的数量,防止重复运算

核心代码:

void dfs2(int p,int fa){
	//L[p]为点p的dfn序
	for(int t:g[p]){
		if(t==fa)  continue;
		ans-=BIT.query(R[t])-BIT.query(L[t]);
		dfs2(t,p);
	} 
	ans+=BIT.query(R[p])-BIT.query(L[p]);//整个子树 
	BIT.add(L[p],1);
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部