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

门户网站制作的公司广告语

门户网站制作的公司,广告语,wordpress yosat,提供广东中山网站建设AGC034E Complete Compress 洛谷[AGC034E] Complete Compress 题目大意 给你一棵有 n n n个节点的树,并用 01 01 01串告诉你哪些节点上有棋子(恰好一棵)。 你可以进行若干次操作,每次操作可以将两颗距离至少为 2 2 2的棋子向彼…

AGC034E Complete Compress

洛谷[AGC034E] Complete Compress

题目大意

给你一棵有 n n n个节点的树,并用 01 01 01串告诉你哪些节点上有棋子(恰好一棵)。

你可以进行若干次操作,每次操作可以将两颗距离至少为 2 2 2的棋子向彼此移动一步。

问能否通过若干次操作使得所有的棋子都在一个点上。如果能,输出最小操作次数;否则,输出 − 1 -1 1

2 ≤ n ≤ 2000 2\leq n\leq 2000 2n2000

时间限制 3000 m s 3000ms 3000ms,空间限制 1024 M B 1024MB 1024MB


题解

我们可以枚举最后所有棋子聚集在哪个点,设这个点为 r r r,我们设 r r r为根。

d i s u dis_u disu表示 u u u的子树中每个棋子到 u u u的距离,那每一次操作会使 d i s r dis_r disr减少 2 2 2或者不变。我们发现, 如果不变的话,相当于浪费了一次,所以最优的肯定是选择减少 2 2 2

每次减少 2 2 2,要不是在 r r r的一个儿子的 d i s dis dis值减少 2 2 2,要不是在 r r r的两个儿子分别减少 1 1 1。我们考虑什么时候无解,无解就是子树不能抵消完。设 m n u mn_u mnu表示子树 u u u中的棋子在内部操作若干次,直到不能再操作时的 d i s u dis_u disu(也就是需要与其他子树操作的最小次数)。设 v v v u u u的儿子,我们比较 m n v + s i z v mn_v+siz_v mnv+sizv d i s u − d i s v − s i z v dis_u-dis_v-siz_v disudisvsizv的大小( s i z v siz_v sizv表示子树 v v v中的棋子个数):

  • 如果 m n v + s i z v ≤ d i s u − d i s v − s i z v mn_v+siz_v\leq dis_u-dis_v-siz_v mnv+sizvdisudisvsizv,那就是能抵消完,最后剩的就是 m n u = d i s u % 2 mn_u=dis_u\%2 mnu=disu%2
  • 如果 m n v + s i z v > d i s u − d i s v − s i z v mn_v+siz_v>dis_u-dis_v-siz_v mnv+sizv>disudisvsizv,就不能抵消完,那我们拿其他部分来抵消 m n v mn_v mnv m n u = m n v + s i z v − ( d i s u − d i s v − s i z v ) mn_u=mn_v+siz_v-(dis_u-dis_v-siz_v) mnu=mnv+sizv(disudisvsizv)

我们记录 u u u的所有儿子 v v v m n v + d i s v + 2 s i z v mn_v+dis_v+2siz_v mnv+disv+2sizv的最大值 m x u mx_u mxu,然后用这个最大值来与 d i s u dis_u disu作比较即可。

最后,看 m n r mn_r mnr是否为 0 0 0。如果为 0 0 0,则可以抵消完,则用 d i s r / 2 dis_r/2 disr/2来更新答案(这里的 d i s r dis_r disr是最开始的 d i s r dis_r disr);否则,以 r r r为最终聚集的点是无解的。

时间复杂度为 O ( n 2 ) O(n^2) O(n2)

可以参考代码帮助理解。

题外话:这道题还有加强版,题意相同但数据范围更大,加强版的题目和题解请看这篇博客。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int n,tot=0,d[2*N+5],l[2*N+5],r[N+5],dep[N+5],siz[N+5];
long long ans=1e18,dis[N+5],mn[N+5],mx[N+5];
char s[N+5];
void add(int xx,int yy){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void dfs(int u,int fa){siz[u]=(s[u]=='1');dis[u]=0;mn[u]=0;mx[u]=0;for(int i=r[u];i;i=l[i]){int v=d[i];if(v==fa) continue;dfs(v,u);siz[u]+=siz[v];dis[u]+=dis[v]+siz[v];long long tmp=dis[v]+siz[v]*2+mn[v];mx[u]=max(mx[u],tmp);}if(mx[u]<=dis[u]) mn[u]=dis[u]%2;else mn[u]=mx[u]-dis[u];
}
int main()
{scanf("%d",&n);scanf("%s",s+1);for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i=1;i<=n;i++){dfs(i,0);if(mn[i]==0) ans=min(ans,dis[i]/2);}if(ans==1e18) printf("-1\n");else printf("%lld\n",ans);return 0;
}
http://www.dt0577.cn/news/20782.html

相关文章:

  • 品牌建设经费投入占销售比重湖南优化推广
  • 哪里做网站靠谱优化防疫措施
  • 可以做qq空间背景音乐的网站seo零基础培训
  • 本地网站环境搭建app开发费用标准
  • 网站运营seo招聘宁波百度推广优化
  • 网站页面设计版权seo博客网站
  • 南通购物网站建设百度搜索引擎
  • 怎样用vs做简单网站市场营销咨询
  • 我在某赌博网站做代理武汉seo全网营销
  • python做的网站哪些网站优化的方式有哪些
  • 有什么可以在线做数学题的网站大连seo关键词排名
  • 做图片推广的网站吗软文写作服务
  • 在哪个网站做一件代发靠谱什么是电商?电商怎么做
  • 网站建设服务市场分析淘宝宝贝排名查询
  • 做网站需要多少钱济宁微信广告投放平台
  • 没有备案的网站怎么做淘宝客百度图片
  • 深圳网站建设推广论坛大连网络推广公司哪家好
  • 东营网站开发公司seo网站关键词优化价格
  • 互联网广告精准营销网页优化seo广州
  • 手机号注册网站免费的网络推广渠道
  • 网站开发方式演进北京企业网站seo平台
  • 网站重做推广软件的app
  • 江苏茂盛建设有限公司网站打开百度一下网页版
  • 网站开发的账务处理广告代理公司
  • 国内做的较好的网站免费推客推广平台
  • 专业外贸网站企业网上的推广
  • 网站构造全网品牌推广
  • 天津网站建设icp备竞彩足球最新比赛
  • 金融网站怎么做百度登录
  • 实用网站推荐在百度平台如何做营销