Bank Hacking CodeForces - 796C

2018-06-17 21:57:51来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目

题意:

一条笨狗要去黑银行,银行有n个,它们之间用n-1条边连接。可以选择任意一个银行开始黑,但是后面每一次黑的银行都要求与已经黑过的银行直接相连。每个银行初始有一个防御值,每一个银行被黑后,与其直接相连的未被黑的银行的防御值会+1,与“与其直接相连的未被黑的银行”相连的未被黑的银行的防御值也会+1,。笨狗要黑完所有银行,且其电脑的强度要求大于等于所有银行被黑那一刻的防御值。现在要求电脑的最小强度。

分析:

记点x在被hack时比原来高的强度为s[x], 稍微尝试一下就会发现,s[第一次选的]=0,s[第一次选的的neighbor]=1,s[其他所有]=2.

选的 s有更新的
选4 s[4]=0 s[3]=s[5]=s[2]=s[6]=1
选5 s[6]=2 s[7]=1
选6 s[7]=2
选3 s[2]=2 s[1]=1
选7
选2 s[1]=2
选1

所以,暴力吧

  1 #include<cstdio>
  2 #include<algorithm>
  3 using namespace std;
  4 typedef long long LL;
  5 struct Edge
  6 {
  7     LL to,next;
  8 }edge[1000100];
  9 LL num_edge,first[500100],d[500100],ans=0x3f3f3f3f,n;
 10 struct Node
 11 {
 12     Node *lc,*rc;
 13     LL l,r;
 14     LL maxn;
 15 }ssss[3000100];//线段树,然而根本用不着
 16 LL num_node;
 17 Node* getnode()
 18 {
 19     return &ssss[num_node++];
 20 }
 21 Node* build(LL l,LL r)
 22 {
 23     Node *_tmp=getnode();
 24     _tmp->l=l;
 25     _tmp->r=r;
 26     if(l==r)
 27     {
 28         _tmp->maxn=d[l];
 29         //_tmp->lc=NULL;
 30         //_tmp->rc=NULL;
 31         return _tmp;
 32     }
 33     LL m=(l+r)>>1;
 34     _tmp->lc=build(l,m);
 35     _tmp->rc=build(m+1,r);
 36     _tmp->maxn=max(_tmp->lc->maxn,_tmp->rc->maxn);
 37     return _tmp; 
 38 }
 39 LL query(LL L,LL R,Node *p)
 40 {
 41     LL l=p->l;
 42     LL r=p->r;
 43     if(L<=l&&r<=R)
 44         return p->maxn;
 45     LL ans=-0x3f,m=(l+r)>>1;
 46     if(L<=m)    ans=max(ans,query(L,R,p->lc));
 47     if(R>m)        ans=max(ans,query(L,R,p->rc));
 48     return ans;
 49 }
 50 void update(LL L,Node *p,LL x)
 51 {
 52     LL l=p->l;
 53     LL r=p->r;
 54     if(l==r)
 55     {
 56         //p->maxn=max(p->maxn,x);
 57         p->maxn+=x;
 58         return;
 59     }
 60     LL m=(l+r)>>1;
 61     if(L<=m)    update(L,p->lc,x);
 62     else        update(L,p->rc,x);
 63     p->maxn=max(p->lc->maxn,p->rc->maxn);
 64 }
 65 int main()
 66 {
 67     LL i,a,b,k;
 68     scanf("%lld",&n);
 69     for(i=1;i<=n;i++)
 70         scanf("%lld",&d[i]);
 71     for(i=1;i<n;i++)
 72     {
 73         scanf("%lld%lld",&a,&b);
 74         edge[++num_edge].to=b;
 75         edge[num_edge].next=first[a];
 76         first[a]=num_edge;
 77         edge[++num_edge].to=a;
 78         edge[num_edge].next=first[b];
 79         first[b]=num_edge;
 80     }
 81     Node *x=build(1,n);
 82     for(i=1;i<=n;i++)
 83     {
 84         update(i,x,-2);
 85         k=first[i];
 86         while(k!=0)
 87         {
 88             update(edge[k].to,x,-1);
 89             k=edge[k].next;
 90         }
 91         ans=min(ans,query(1,n,x)+2);
 92         update(i,x,2);
 93         k=first[i];
 94         while(k!=0)
 95         {
 96             update(edge[k].to,x,1);
 97             k=edge[k].next;
 98         }
 99     }
100     printf("%lld",ans);
101     //del(x);
102     return 0;
103 }

 再贴一张

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Mike and gcd problem CodeForces - 798C

下一篇:Qt窗口及控件-窗口Close()自动释放