威海

C

本题的数学模型如下：
给定一棵树T、树的一个结点子集S，从S中任选三个结点，
求这三个结点到离这三个点距离和最短的点的距离和的期望
$$E[\sum (dis(u_i,v)+dis(u_j,v)+dis(u_k,v))]$$
其中$dis(x,y)$表示两个结点间的距离，v表示使得$dis(u_i,v)+dis(u_j,v)+dis(u_k,v)$取最小的某节点。

注意到$dis(u_i,v)+dis(u_j,v)+dis(u_k,v)=\frac{1}{2}(dis(u_i,u_j)+dis(u_j,u_k)+dis(u_k,u_i))$（结合树的性质不难证明），再结合期望的线性性质，本题目标简化为求：
$$\frac{1}{2}E[\sum dis(u_i,u_j)]$$

进行这样的化简后，即可对树上的每条边单独考虑贡献，一次深搜可以在O(n)时间内解决。

输入写错了一个变量，调了一万年
还忘开longlong了…破房子

#include <bits/stdc++.h>
using namespace std;
typedef long double ldb;
typedef long long ll;const int maxn = 2e5 + 1;
int n;
ll m[3];
ldb ans = 0;
ldb dp[3];struct node
{int id;vector<int> v;vector<int> w;ll num[3];
} nodes[maxn];void dfs1(int id, int fa)
{node &nd = nodes[id];for (int i = 0; i < nd.v.size(); ++i){if (nd.v[i] == fa)continue;dfs1(nd.v[i], id);for (int k = 0; k < 3; ++k)nd.num[k] += nodes[nd.v[i]].num[k];}
}void dfs2(int id, int fa)
{node &nd = nodes[id];for (int i = 0, j; i < nd.v.size(); ++i){if (nd.v[i] == fa)continue;j = nd.v[i];for (int k = 0; k < 3; ++k){dp[k] += nd.w[i] * nodes[j].num[k] * (m[(k + 1) % 3] - nodes[j].num[(k + 1) % 3]) + nd.w[i] * nodes[j].num[(k + 1) % 3] * (m[k] - nodes[j].num[k]);}dfs2(j, id);}
}int main()
{// freopen("cin", "r", stdin);scanf("%d", &n);for (int i = 1; i <= n; ++i){nodes[i].id = i;}for (int i = 1, x, y, w; i < n; ++i){scanf("%d%d%d", &x, &y, &w);nodes[x].v.push_back(y);nodes[x].w.push_back(w);nodes[y].v.push_back(x);nodes[y].w.push_back(w);}for (int k = 0; k < 3; ++k){scanf("%lld", m + k);for (int i = 0, tmp; i < m[k]; ++i){scanf("%d", &tmp);nodes[tmp].num[k]++;}}dfs1(1, 0);dfs2(1, 0);for (int i = 0; i < 3; ++i)ans += 1.0 * dp[i] / (m[i] * m[(i + 1) % 3]);ans /= 2;printf("%.10Lf\n", ans);return 0;
}

E

这题难度挺大的，我觉得属于“放到场上就算给我题解我也做不出来”的那种题
核心问题有两个

1. dp求状态转移
2. dp求辅助数组color（代表一个涂色模型子问题的解，用于赋权）

第一个问题可以在$O(2^{n}mn)$时间内求解，算是比较典型的状压DP（但是状态转移方程，不看题解不好推）
第二个问题是复杂度的“关键结点”，$O(2^n{m}^2)$的复杂度，挺难搞的一个问题。

#include <bits/stdc++.h>
using namespace std;
typedef long double ldb;
typedef long long ll;const int maxn = 20, maxm = 105;
const int maxs = 33000;
int status;
int n, m;
int a[maxn];
ldb c[maxm][maxm];
ldb p[maxs], dp[maxm][maxs];
ldb ans = 0.0;
int hp[maxs], cnt[maxs];
ldb color[maxm][maxs], g[maxm][maxm];
// color[i][s] stand for the num of schemes to attack i times without killingvoid dfs(int d, int S, int nt)
{if (d == n){for (int i = 0; i <= m; i++){color[i][S] = g[nt][i];}return;}for (int i = 0; i <= m; i++){for (int j = 0; j < a[d + 1] && j <= i; j++)g[nt + 1][i] += g[nt][i - j] * c[i][j];}dfs(d + 1, S, nt + 1); // d is livefor (int i = 0; i <= m; i++){g[nt + 1][i] = 0;}dfs(d + 1, S ^ (1 << d), nt);
}void init()
{status = 1 << n;for (int s = 0; s < status; ++s){hp[s] = 0;for (int i = 0; i < n; ++i){if ((s >> i) & 1)hp[s] += a[i + 1];}cnt[s] = __builtin_popcount(s);}c[0][0] = 1;for (int i = 1; i <= m; ++i){c[i][0] = 1;for (int j = 1; j <= i; ++j){c[i][j] = c[i - 1][j] + c[i - 1][j - 1];}}g[0][0] = 1;dfs(0, 0, 0);
}bool legal(int i, int s)
{int ns = (status - 1) ^ s;return (i >= hp[s]) && (i - hp[s] <= hp[ns] - cnt[ns]);
}void solve()
{dp[0][0] = 1;for (int s = 0; s < status; ++s){int t = cnt[s], nt = n - t;int ns = (status - 1) ^ s;for (int i = 0; i < m; ++i){if (!legal(i, s)){dp[i][s] = 0;continue;}for (int j = 0; j < n; ++j){if ((s >> j) & 1)continue;if (legal(i + 1, s | (1 << j))){ldb tmp = c[i - hp[s]][a[j + 1] - 1] / nt;dp[i + 1][s | (1 << j)] += dp[i][s] * tmp;}}if (legal(i + 1, s)){dp[i + 1][s] += dp[i][s] / nt;}}if (legal(m, s)){ans += dp[m][s] * color[m - hp[s]][s] * t;}}
}int main()
{// freopen("ein2", "r", stdin);scanf("%d%d", &n, &m);for (int i = 0; i < n; ++i)scanf("%d", a + i + 1);init();solve();printf("%.9Lf\n", ans);return 0;
}

K

这题是一个二叉查找树的题
题解看懂了，但没完全看懂
思路大致是在$O(n\log n)$时间内实现建树，然后在$O(k^3)$ 时间内dp求答案
但不是很懂为什么这种思路对于$[r,n]$范围内的数不会产生影响

Ongoing