C. Bank Hacking 解析(思維)

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

今天我們來看看CF796C
題目連結

題目
略，請直接看原題。

前言

@copyright petjelinux 版權所有
觀看更多正版原始文章請至petjelinux的blog

想法

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

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

那麼我們可以想到以下的結論:
首先維護(:)最大的(a[i])((mx))，次大的(a[i])((smx))，最大的(a[i])的點的個數((cmx))，次大的(a[i])的點的個數((csmx))

1. 如果(mx)只有(1)，那麼我們一定是從這個點開始，否則我們最少需要(mx+1)的力量(次大的點最多(+2)，也就是(smx+2)，其小於等於(mx+1))。而如果這個點包含了所有的次大的點，那麼答案就是(mx)，否則就是(max{smx+2,mx})。
2. 如果(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<<'
';
    else cout<<max(mx,smx+2)<<'
';
  }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<<'
';return 0;}
    }cout<<mx+2<<'
';
  }
  return 0;
}

標頭、模板請點Submission看
Submission