Codeforce 796 C. Bank Hacking 解析(思維)

今天我們來看看CF796C

題目連結

題目

略，請直接看原題。

前言

@copyright petjelinux 版權所有

觀看更多正版原始文章請至petjelinux的blog

想法

首先稍微在腦中模擬一下大概整個流程是怎麼進行的，會發現以下幾件事:

選取點\(v\)開始整個流程，之後是對以\(v\)為根的樹"Hack"，並且銀行防禦力增加只會加到子節點
每個點最多被\(+2\)

那麼我們可以想到以下的結論:

首先維護\(:\)最大的\(a[i]\)(\(mx\))，次大的\(a[i]\)(\(smx\))，最大的\(a[i]\)的點的個數(\(cmx\))，次大的\(a[i]\)的點的個數(\(csmx\))

如果\(mx\)只有\(1\)，那麼我們一定是從這個點開始，否則我們最少需要\(mx+1\)的力量(次大的點最多\(+2\)，也就是\(smx+2\)，其小於等於\(mx+1\))。而如果這個點包含了所有的次大的點，那麼答案就是\(mx\)，否則就是\(\max\{smx+2,mx\}\)。
如果\(mx\)有多個，那麼我們只需要遍歷所有點，看看有沒有點連接(含本身)了所有\(a[i]\)最大的點(就算點本身就是\(mx\)，由於有多個值為\(mx\)的點，我們最小還是需要\(mx+1\)的力量)，如果有，那麼答案就是\(mx+1\)，否則就是\(mx+2\)。(這個流程等於是遍歷所有的邊，所以複雜度是\(O(2(n-1))\))

程式碼:

const int _n=3e5+10;

int t,n,a[_n],cmx,csmx,mx=-1e9-1,smx=-1e9-1,cnt,uu,v;

VI G[_n];

main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

  cin>>n;rep(i,1,n+1)cin>>a[i];rep(i,1,n){cin>>uu>>v;G[uu].pb(v),G[v].pb(uu);}

  rep(i,1,n+1)mx=max(mx,a[i]);rep(i,1,n+1)if(a[i]!=mx)smx=max(smx,a[i]);

  rep(i,1,n+1)if(a[i]==mx)cmx++;rep(i,1,n+1)if(a[i]==smx)csmx++;

  if(cmx==1){

    rep(i,1,n+1)if(a[i]==mx)for(int u:G[i])if(a[u]==smx)cnt++;

    if(cnt==csmx)cout<<mx<<'\n';

    else cout<<max(mx,smx+2)<<'\n';

  }else{

    rep(i,1,n+1){

      cnt=0;if(a[i]==mx)cnt++;

      for(int u:G[i])if(a[u]==mx)cnt++;

      if(cnt==cmx){cout<<mx+1<<'\n';return 0;}

    }cout<<mx+2<<'\n';

  }

  return 0;

}

標頭、模板請點Submission看

Submission

巴特西

C. Bank Hacking 解析(思維)

Codeforce 796 C. Bank Hacking 解析(思維)

前言

想法

程式碼:

最新文章

热门文章