2014 ACM/ICPC Asia Mudanjiang Regional Contest Onsite

Problem B. Domination

Brief description:

給定一棵無根樹 T 。定義以 T 上一對點 (a, b) 為「復根」的樹的高度 h(a, b) = max min(dist(x, a), dist(x, b)), for all x on T 。
現求 H(T) = min h(a, b), for all (a, b) | a != b。

Analysis:

結論:兩個復根一定在樹的直徑上。

先求直徑,並求出直徑上每個點為根的樹所到達的最遠距離。
二分答案,每次先貪心的將復根儘可能向中間移動。。。然後在判斷中間的那些點是否也合法。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2882177

Problem D. Domination

Brief description:

略。)

Analysis:

似乎是某場 CF 的 B。

f[i][j][k]: 表示當前有 i 行、j 列沒有覆蓋,且一共還有 k 個格子沒填時的期望。
轉移分四種情況討論即可。(似乎這個狀態表示不是特別好。。這樣做必須要使用 long double。。)

//}/* .................................................................................................................................. */

const int N = 51;
long double f[N][N][N*N];
int n, m;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{
        RD(n, m); RST(f);

#define u f[i][j][k]
        REP_2(i, j, n+1, m+1){
            if (!i && !j) continue;
            REP_1(k, n*m){
                u = (k-i*m-j*n+i*j) * f[i][j][k-1];
                if (i && j) u += i*j * f[i-1][j-1][k-1];
                if (i) u += i*(m-j) * f[i-1][j][k-1];
                if (j) u += j*(n-i) * f[i][j-1][k-1];
                u /= k, ++u;
            }
        }

        OT((DB)f[n][m][n*m]);
    }
}

Problem F. Fiber-optic Network

Brief description:

給定一顆 50 個結點的無向樹,每個結點可以填 [Li, Ri] 之間的數。
要求相鄰結點填的數 co-prime。問一共有多少種方案。(要求輸出所有方案里每個結點所填的數字和)

Analysis:

樹 DP,容斥原理轉移。

f1[u][val]:表示 u 點填 val 時的方案數。。。
用容斥原理進行轉移。。。

考慮 (u, v) 的轉移,設 f2[v][val] 為 v 結點所有以 val 為倍數的答案。我們預處理出 mu 函數,以及 val 所有的 mu 值不為 0 的倍數。。
那麼就是:

    ECH(it, adj[u]) if (v != p){
        FOR_1(i, ll[u], rr[u]){
            Int t = 0; ECH(d, dd[i]) t += Int(mu[*d])*f2[v][*d];            
            f1[u][i] *= t;
        }
    }

dfs 兩次。。
第一次可以得到根結點的答案。。
為了得到其它結點的答案。。需要將父親結點的結果除去以某個 v 作為孩子時的方案數作為一個新的孩子。。。參與轉移。。
得用一些麻煩的方法避免除法。。。TLE...

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2844775

改進:
按照邊進行 DP。。。
f1[i][val]:i 表示 (p, u) 這條邊。。。
。。u 點填 val 時的方案數。。。可以避免除法。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2845448

Problem K.

Brief description:

...

Analysis:

貪心。。digit 總是越靠前越好。。
。先在前面補齊必要的 digit。。。然後貪心的將最前的非法 * 和最後的 digit 交換。

//}/* .................................................................................................................................. */

string s;
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{
        cin >> s; n = s.size();
        int a = 0; REP(i, n) if (s[i] == '*') ++a;
        int b = n - a, bb = 0, z = 0; z += max(0, a-(b-1)); bb = z;
        REP(i, n) if (s[i] == '*'){
            if (bb < 2) ++bb, ++z;
            else --bb;
        }
        else ++bb;
        cout << z << endl;
    }
}

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2845839