2015年5月3日 星期日

[CF 538E] Demiurges Play Again

作法:

把題目要求的兩個數值分開計算,兩個數的算法類似,所以這裡只敘述「目的是要讓最終結果越大越好」的那個人的作法。對每個節點 $x$ 紀錄兩個 $dp$ 值,一個代表「若 $x$ 形成的子樹的子節點編號為 $1$ ~ $k$ ,且此時輪到先手,那麼在雙方採取最佳策略後所可以停留的最大值」,令一個則是輪到後手時的最終停留數字的最大值(假設 $dp[ x ][ 0 ]$ 代表前者,$dp[ x ][ 1 ]$ 代表後者)。首先計算 $dp[ x ][ 0 ]$ ,當 x 是葉子的時候顯然是 $1$ 。當 x 不是葉子的時候,假設他的子節點為 $T_1$ ~ $T_k$ ,並且記 $T_i$ 子樹的葉子數為 $S_i$ ,還有記 $d_i = dp[ T_i ][ 1 ]$ (因為走下去之後是輪到後手),那麼首先要先釐清其實 $d_i$ 代表的意義為:如果先手此時決定走向 $T_i$ ,那麼最後就一定會停留在 $T_i$ 的所有葉子中數值第 $d_i$ 小的節點上。因為我們在DP時是假設這棵子樹的葉子是從 $1$ 開始往上編號的,但事實上如果不是的話,也不影響雙方的最佳策略,因為和兩人的決策有關的只有「這個數是否比那個數大」,而不是每個數真正的數值。現在我們有 $1$ ~ $( S_1 + ... + S_k )$ 這些編號,且目的是要找出一個好的編號方法,讓先手做完決策之後最後到的數值最大。而由前面的結論可以知道,如果我們把 $a_1$ ~ $a_{S_i}$ 這些數分到子樹 $T_i$ 裡面的話(其中 $a_i < a_{ i+1 }$),那麼當先手決定走到 $T_i$ 時最終就會停留在 $a_{d_i}$ ,也就是不管在這個子樹裡放哪些數,都會恰好有 $S_i - d_i$ 個比終點還大但沒辦法走到的點,因此為了不讓那些「被浪費掉的大數值太多」,此時的最好配置方法就是:找出所有子樹中 $S_i - d_i$ 最小的子樹,並且把 $1$ ~ $( S_1 + ... + S_k )$ 中最大的 $S_i$ 個數都分配到這個子樹裡,這樣先手就會決定往這個子樹走,最後就會停留在標號 $( S_1 + ... + S_k ) - ( S_i - d_i )$ 的節點。

至於 $dp[ x ][ 1 ]$ 的算法則不太一樣了,因為後手的目的是要讓走到的數越小越好,因此他會去找每個子樹 $T_i$ 所標的所有數值中,第 $d_i$ 小的數最小會是多少,因此我們要找一個好的配置方法,使得後手不管怎麼樣都會選到一個蠻大的數。此時最好的配置方法為:記所有子樹的 $S_i - d_i + 1$ 的總和為 $S$ ,那麼就把 $1$ ~ $( S_1 + ... + S_k )$ 中最大的 $S$ 個數分配到每個子樹的「第 $d_i$ 小到第 $S_i$ 小的數」裡,這樣後手就會選擇走到 $( S_1 + ... + S_k ) - S + 1$ 所在的子樹了,因為這是所有子樹中,第 $d_i$ 小的數的最小值。

code :



#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
vector<int> v[maxn] ;
int ma[maxn][2] , mi[maxn][2] ; /// 0 : fir , 1 : sec
int num[maxn] ;
void dfs(int x)
{
    if(v[x].empty())
    {
        ma[x][0]=ma[x][1]=mi[x][0]=mi[x][1]=1 ;
        num[x]=1 ; return ;
    }
    for(auto i :v[x]) dfs(i) , num[x]+=num[i] ;
 
    int sum1=0,sum2=0 ;
    mi[x][1]=maxn ;
    for(auto i :v[x])
    {
        ma[x][0]=max(ma[x][0],num[x]-(num[i]-ma[i][1])) ;
        sum1+=num[i]-ma[i][0]+1 ;
        sum2+=mi[i][1] ;
        mi[x][1]=min(mi[x][1],mi[i][0]) ;
    }
    ma[x][1]=num[x]-sum1+1 ;
    mi[x][0]=sum2 ;
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
    }
    dfs(1) ;
    printf("%d %d\n",ma[1][0],mi[1][0]) ;
}
 

沒有留言:

張貼留言