devbox
运维做开发
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2024 暑假友谊赛-热身2

作者：运维做开发 | 2024-08-02 22:57:20

赞

踩

2024 暑假友谊赛-热身2

Tree Destruction - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:树的直径。

定理：在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。
第一次dfs1(),从任意一个点,到达的最远的点必然是直径两端的其中一个。
再从找到的端点开始dfs1(),找到另一个端点。这样就可以o(n)确定该树的直径.得到直径的端点S和T.
再两次dfs2(),分别得到S和T到达其他每个点的距离.
之后就可以从度为1的点x开始删除,每次都选和x更远的端点.并且删除x.
最后再处理剩下的直径的点.
  1. int n;
  2. vector<int> vct[200005];
  3. int S=0,T=0,maxd=0,tag=0,typ=0;
  4. int dis[2][200005];
  5. int du[200005];
  6. vector<array<int,3>> ans;
  7. int sum=0;
  8. queue<int> que;
  9. void dfs1(int s,int d,int fa){    求从s点出发,可以达到最远的点.
  10.     if(d>maxd){
  11.         if(!tag) S=s;
  12.         else T=s;
  13.         maxd=d;
  14.     }
  15.     for(auto v:vct[s]) if(v!=fa) dfs1(v,d+1,s);
  16. }
  17. void dfs2(int s,int d,int fa){   从端点S/T出发到达其他点的距离
  18.     dis[typ][s]=d;
  19.     for(auto v:vct[s]) if(v!=fa) dfs2(v,d+1,s);
  20. }
  21. void process(int op){
  22.     while(que.size()){
  23.         int cur=que.front();
  24.         que.pop();
  25.         du[cur]--;
  26.         if(op==1){
  27.             if(dis[0][cur]>=dis[1][cur]) ans.emplace_back(array{S,cur,cur}),sum+=dis[0][cur];
  28.             else ans.emplace_back(array{T,cur,cur}),sum+=dis[1][cur];
  29.         }
  30.         else if(op==2) ans.emplace_back(array{S,cur,cur}),sum+=dis[0][cur];
  31.         for(auto v:vct[cur]) {
  32.             du[v]--;
  33.             if(du[v]==1) que.emplace(v);
  34.         }
  35.     }
  36. }
  37. 题意:从树上选两个叶子节点，把他们的距离加到ans中，并且删去其中一个节点。求剩下一个点时的ans最大值。
  38. Tree Destruction
  39. https://www.luogu.com.cn/problem/CF911F
  40. 定理：在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。
  41. 第一次dfs1(),从任意一个点,到达的最远的点必然是直径两端的其中一个。
  42. 再从找到的端点开始dfs1(),找到另一个端点。这样就可以o(n)确定该树的直径.得到直径的端点S和T.
  43. 再两次dfs2(),分别得到S和T到达其他每个点的距离.
  44. 之后就可以从度为1的点x开始删除,每次都选和x更远的端点.并且删除x.
  45. 最后再处理剩下的直径的点.
  46. void solve(){           补B  选叶子   o(n)
  47.     cin>>n;
  48.     for(int i=1;i<=n-1;i++){
  49.         int u,v; cin>>u>>v;
  50.         vct[u].emplace_back(v);
  51.         vct[v].emplace_back(u);
  52.         du[u]++,du[v]++;
  53.     }
  54.     tag=0,maxd=0,dfs1(1,0,0);
  55.     tag=1,maxd=0,dfs1(S,0,0);
  56.     typ=0,dfs2(S,0,0);
  57.     typ=1,dfs2(T,0,0);
  58.     for(int i=1;i<=n;i++) if(du[i]==1&&i!=S&&i!=T) que.emplace(i);
  59.     du[S]=0,du[T]=0;
  60.     process(1);
  61.     que.emplace(T);
  62.     process(2);
  63.     cout<<sum<<endl;
  64.     for(auto a:ans) cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
  65. }

DivRem Number - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:

N%m=N-(N/m)*m
移项N=(m+1)*(N/m), 那么(m+1)是N的因子 , 那么枚举N的因子即可
  1. 题意:给定N,求满足(N/m)=N%m的m的总和.   除法全都是向下取整
  2. DivRem Number
  3. https://www.luogu.com.cn/problem/AT_diverta2019_d
  4. N%m=N-(N/m)*m
  5. 移项N=(m+1)*(N/m), 那么(m+1)是N的因子 , 那么枚举N的因子即可
  6. void solve(){           补G  o(sqrt(N))
  7.     int N; cin>>N;
  8.     int ans=0;
  9.     for(int i=0;i<=sqrt(N);i++){
  10.         if(N%(i+1)==0){       i是在枚举m的值,但是i不是因子,i+1才是因子
  11.             int x=N/(i+1);   另一个因子
  12.             if(i!=0&&N==(i+1)*(N/i)) ans+=i;
  13.             if(x-1!=0&&N==x*(N/(x-1))) ans+=x-1;  x=m+1,那么m=x-1.
  14.         }
  15.     }
  16.     cout<<ans;
  17. }

Beautiful Mirrors - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:还是不懂。。

  1. const int mod=998244353;
  2. int quickpow(int a,int b){
  3.     int res=1;
  4.     while(b){
  5.         if(b&1) res*=a,res%=mod;
  6.         a*=a,a%=mod;
  7.         b>>=1;
  8.     }
  9.     return res;
  10. }
  11. 定义f[i]为到达第i天，并且第i天也快乐的期望天数.
  12. 思路:第i天询问失败，从头开始。此时概率为1-p，消耗天数为f[i-1]+1+f[i]。乘上概率，代价为(1-pi)(f[i-1]+1+f[i]).
  13. 第i天询问成功。此时概率为p，消耗天数为f[i-1]+1。乘上概率，代价为pi*(f[i-1]+1).
  14. 那么f[i]=pi*(f[i-1]+1)+(1-pi)(f[i-1]+1+f[i]).
  15. 整理有f[i]=( (f[i-1]+1) / (pi/100) ). 注意除法取mod用逆元.
  16. 此处解释,询问失败时消耗天数为 f[i-1]+1+f[i] 是因为：
  17. 当前要重新回到第i天，所以需要加f[i]. 而到达第i天之前需要先到达i-1天并且再+1才能回到第i天.
  18. 还是不懂。。为什么不用考虑回到i-2天然后加一天到达i-1天，然后再加一天回到第i天?i-3?i-4?..
  19. 官方题解: https://codeforces.com/blog/entry/71995
  20. 声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
    推荐阅读
    相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。