当前位置: 首页 > news >正文

百度网站分析报告网站建设应该注意什么

百度网站分析报告,网站建设应该注意什么,潮州 网站建设,做一个企业网站价格正题 题目链接:https://www.luogu.com.cn/problem/CF1039D 题目大意 给出nnn个点的一棵树#xff0c;然后对于k∈[1,n]k\in[1,n]k∈[1,n]求每次使用一条长度为kkk的链覆盖树并且不能重复覆盖点时最大覆盖条数。 1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路 先考虑暴力怎么…正题 题目链接:https://www.luogu.com.cn/problem/CF1039D 题目大意 给出nnn个点的一棵树然后对于k∈[1,n]k\in[1,n]k∈[1,n]求每次使用一条长度为kkk的链覆盖树并且不能重复覆盖点时最大覆盖条数。 1≤n≤1051\leq n\leq 10^51≤n≤105 解题思路 先考虑暴力怎么做因为每条链的价值都是一显然的一种贪心思想是能合并的就合并没有让出一条链给另一条链腾空间的必要。 这样的复杂度是O(n)O(n)O(n)的但是对于每个都要求所以需要优化。 之后考虑上根号分治对于一个kkk的答案显然不会超过nk\frac{n}{k}kn​所以可以当k≤nk\leq \sqrt nk≤n​的时候暴力做然后由于答案递增大于n\sqrt nn​的kkk答案的取值不会超过n\sqrt nn​每次二分断点即可。时间复杂度O(nnlog⁡n)O(n\sqrt n\log n)O(nn​logn)。 其实发现这样还是不够快可以找到一个更好的阈值设为TTT那么前面的复杂度就是TTT后面的复杂度就是nTlog⁡n\frac{n}{T}\log nTn​logn用平衡规划的思想当TnTlog⁡nT\frac{n}{T}\log nTTn​logn时最快也就是Tnlog⁡nT\sqrt{n\log n}Tnlogn​时最快了。 code #includecstdio #includecstring #includealgorithm #includecmath using namespace std; const int N1e510; struct node{int to,next; }a[N1]; int n,tot,cnt,dfn[N],ls[N],fa[N],f[N]; void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return; } void dfs(int x){dfn[cnt]x;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x])continue;fa[y]x;dfs(y);}return; } int solve(int k){if(k1)return n;int ans0;for(int i1;in;i)f[i]1;for(int in;i1;i--){int xdfn[i];if(f[x]f[fa[x]]){if(f[x]f[fa[x]]k)ans,f[fa[x]]0;else f[fa[x]]max(f[fa[x]],f[x]1);}}return ans; } int main() {scanf(%d,n);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs(1);int Tsqrt((double)n*(log(n)/log(2))),last,zT1;for(int i1;iT;i)printf(%d\n,lastsolve(i));while(zn){int lz1,rn,ksolve(z);while(lr){int mid(lr)1;if(solve(mid)k)rmid-1;else lmid1;}for(int iz;ir;i)printf(%d\n,k);zr1;}return 0; }
http://wiki.neutronadmin.com/news/348577/

相关文章:

  • 营销型网站建设需要有什么功能大唐网站首页
  • 做视频网站要用到的服务器厦门做网站哪家好
  • 黑山网站建设ipad做电影网站
  • ps网站导航怎么做分销系统软件
  • 哈尔滨网站建设哪儿好薇wordpress首页提示
  • 电子商务网站平台建设扬中网站建设机构
  • 佛冈县住房和城乡建设局网站怎么在手机上设计网站
  • 东莞网站建设0769dtwordpress 绿色
  • 一般设计网站页面用什么软件网站建设费用 知乎
  • 购物网站免费模板石家庄官网设计及搭建
  • .net网站开发用的书籍18岁以上站长统计
  • 免费制作婚介网站涡阳网站优化
  • 全国集团网站建设同城app开发公司排名
  • 网站如何做问卷调查报告网站收录方法
  • 舟山市建设工程造价管理协会网站安阳网站设计哪家好
  • 一个网站能卖多少钱?wordpress弹出式侧边栏
  • .net电商网站全站开发北京网站优化方案
  • 默认网站预览能能显示建设中成品源码灬1688高清完整版
  • 武进区城乡建设局网站电子商务网站建设与维护书
  • 吕梁网站建设公司网站查询页面设计
  • 宣传网站建设意义wordpress弹窗下载插件
  • dns网站卫士 收录郑州百度seo网站优化
  • 两个人做类似的梦 网站网站开发选定制还是模板
  • 浙江建设职业技术学院门户网站网站框架有哪些
  • 网站建设项目的工作分解碑林微网站建设
  • 网站建设价格费用关于一学一做的短视频网站
  • 做网站的毕设用什么软件百度快照提交入口
  • 网站被黑了怎么办网站正在建设中...为什么护卫神
  • 网站内容及实现的方式网站开发框架技术
  • 微擎 网站开发工具网址ip域名查询