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

Posted by xiaodao
Category: 日常