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
