网站建设投入及费用,网络营销ppt课件,网站前端模板下载,wordpress相册页A. 猴猴吃苹果
题意#xff1a;给定根节点k#xff0c;求访问点的顺序#xff0c;使得每次从上一个点到当前点的权值最大。访问过的点权值为0。权值一样时#xff0c;输出最小编号
思路#xff1a;由于是双向边#xff0c;先求根节点到每一个节点的距离值。在第一轮中给定根节点k求访问点的顺序使得每次从上一个点到当前点的权值最大。访问过的点权值为0。权值一样时输出最小编号
思路由于是双向边先求根节点到每一个节点的距离值。在第一轮中最深的叶节点一定为答案那么这一条路径就被访问过了权值变为0这个叶节点相同路径上的其他点到根节点最后一个未被标记的点的权值就改变了。所以从最优的叶节点出发dfs往上跳直到访问到已经被访问过的点为止即可。最后排序更新后的权值
#includebits/stdc.husing namespace std;const int N 1e6 10;int n,k,d[N],tot;
bool vis[N];
struct node{int id,val;
}a[N];
vectorint v[N];
inline bool cmp(node p,node q){if(p.val!q.val) return p.valq.val;else return p.idq.id;
}
void dfs1(int p,int fa){for(int t:v[p]){if(tfa) 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(tfa||d[t]d[p]) continue;dfs2(t,p);}
}
int main(){cinnk;for(int i1,x;in;i){cinx;v[i].push_back(x);v[x].push_back(i);}dfs1(k,-1);vis[k]true;for(int i0;in;i){a[i].idi;a[i].vald[i];}sort(a,an,cmp);
// for(int i0;in;i) couta[i].id ;for(int i0;in;i){tot0;dfs2(a[i].id,-1);a[i].valtot;
// couttot a[i].idendl;}sort(a,an,cmp);coutkendl;for(int i0;in;i){if(a[i].val)couta[i].idendl;}return 0;
}
B. 猴猴吃香蕉
题意选取n个数中的若干个数使得它们的乘积为k
思路计数dp容易得出的转移方程式。使得为组成k的一个因子。由于k的范围不可接受于是筛出k的所有因子如果能整除说明这个数能被分解。由于因子较大且个数趋近根号n需要离散化
最终dp方程答案为
C. 猴猴的比赛
题意给定两棵树求一个节点x在两棵树中有相同祖先的对数
思路考虑求出每一个点的子树中的范围连续的对于另一颗树而言每次处理一个点答案计数完成后就将这个点在第一棵树中的位置标记为1。答案计数为所有父节点中1的数量。注意在遍历子节点时需要减去子树所有点的中1的数量防止重复运算
核心代码
void dfs2(int p,int fa){//L[p]为点p的dfn序for(int t:g[p]){if(tfa) continue;ans-BIT.query(R[t])-BIT.query(L[t]);dfs2(t,p);} ansBIT.query(R[p])-BIT.query(L[p]);//整个子树 BIT.add(L[p],1);
}
