8.9套题

A. 猴猴吃苹果

题意：给定根节点k，求访问点的顺序，使得每次从上一个点到当前点的权值最大。访问过的点权值为0。权值一样时，输出最小编号
思绪：由于是双向边，先求根节点到每一个节点的间隔值。在第一轮中，最深的叶节点一定为答案，那么这一条路径就被访问过了，权值变为0，这个叶节点相同路径上的其他点到根节点（末了一个未被标记的点）的权值就改变了。所以从最优的叶节点出发，dfs往上跳，直到访问到已经被访问过的点为止即可。末了排序更新后的权值

1. #include<bits/stdc++.h>
3. using namespace std;
5. const int N = 1e6 + 10;
7. int n,k,d[N],tot;
8. bool vis[N];
9. struct node{
10.         int id,val;
11. }a[N];
12. vector<int> v[N];
13. inline bool cmp(node p,node q){
14.         if(p.val!=q.val)  return p.val>q.val;
15.         else return p.id<q.id;
16. }
17. void dfs1(int p,int fa){
18.         for(int t:v[p]){
19.                 if(t==fa)  continue;
20.                 d[t]=d[p]+1;
21.                 dfs1(t,p);
22.         }
23. }
24. void dfs2(int p,int fa){
25.         if(vis[p])  return;
26.         tot++;
27.         vis[p]=true;
28.         for(int t:v[p]){
29.                 if(t==fa||d[t]>=d[p])  continue;
30.                 dfs2(t,p);
31.         }
32. }
33. int main(){
34.         cin>>n>>k;
35.         for(int i=1,x;i<n;i++){
36.                 cin>>x;
37.                 v[i].push_back(x);
38.                 v[x].push_back(i);
39.         }
40.     dfs1(k,-1);vis[k]=true;
41.     for(int i=0;i<n;i++){
42.             a[i].id=i;a[i].val=d[i];
43.         }
44.         sort(a,a+n,cmp);
45. //        for(int i=0;i<n;i++)  cout<<a[i].id<<" ";
46.     for(int i=0;i<n;i++){
47.             tot=0;
48.             dfs2(a[i].id,-1);
49.             a[i].val=tot;
50. //            cout<<tot<<" "<<a[i].id<<endl;
51.         }
52.         sort(a,a+n,cmp);
53.         cout<<k<<endl;
54.         for(int i=0;i<n;i++){
55.                 if(a[i].val)
56.                   cout<<a[i].id<<endl;
57.         }
58.         return 0;
59. }

复制代码

B. 猴猴吃香蕉

题意：选取n个数中的若干个数，使得它们的乘积为k
思绪：计数dp，容易得出

的转移方程式。使得

为构成k的一个因子。由于k的范围不可接受，于是筛出k的所有因子，如果

能整除，说明这个数能被分解。

，由于因子较大，且个数趋近根号n，必要离散化
终极dp方程：

，答案为

C. 猴猴的比赛

题意：给定两棵树，求一个节点x在两棵树中有相同祖先的对数
思绪：考虑求出每一个点的子树中的范围

（一连的），对于另一颗树而言，每次处理一个点答案计数完成后，就将这个点在第一棵树中的位置标记为1。答案计数为所有父节点

中1的数量。注意在遍历子节点时，必要减去子树所有点的

中1的数量，防止重复运算
焦点代码：

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

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。