总结：
祭考试做出一道期望 dp /se
考试心路历程：
5 min 读完 T1, ahhhhhh，签到题，10 min 写完，一发过大样例。
8:20 开干 T2，期望 dp，读完题，感觉可做。
写了好久，调过样例，写了对拍，一拍就挂，rnm。
调半天，转移写挂 = =
10:10 开 T3
T3 题目好奇怪，为啥开头是 T2 的题目啊，没用，没用，删了。
艹，这花店在哪儿，我家在哪儿，我咋找不到我家！！
读了好几遍，没读懂题，麻了，睡觉。
赛后：为啥我 T3 题目少了一个自然段啊 ！！！！
T1 三向城
solution
手摸题目，你发现这是个满二叉树。
然后你会发现，他的层数其实很少。
你还会发现每个节点的父亲就是改节点 / 2
然后你就暴力向上跳就好了 = =
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 35;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int q, Ans;
int get(int x) {
for (int i = 1; i <= MAX; i++)
if((1 << i) > x) return i;
}
signed main(){
//freopen("city.in", "r", stdin);
//freopen("city.out", "w", stdout);
q = read();
for (int i = 1, x, y; i <= q; i++) {
x = read(), y = read();
Ans = 0;
int dep_x = get(x), dep_y = get(y);
if(dep_x < dep_y) swap(x, y), swap(dep_x, dep_y);
while(dep_x != dep_y) {
x = x / 2;
Ans++, dep_x--;
}
while(x != y) {
x = x / 2, y = y / 2;
Ans += 2;
}
cout<<Ans<<"
";
}
return 0;
}
T2 灵魂画师
solution
期望 = 概率 * 权值
显然权值就是颜色，考虑怎么计算每个位置变成某个颜色的概率。
不难发现，某个位置变成哪个颜色只与它被选中的次数有关。
设 (P_{i, j}) 表示 (i) 一个点出现在 (i) 个区间内，被选中 (j) 次的概率。
显然 (P_{i, j} = frac{C_{i}^{j}}{2})
设 (f_{i, j}) 表示选中 (i) 次，变为颜色 (j) 的概率。
(f_{i + 1, j imes o \% c} += f_{i, j} / c)
(P) 和 (f) 都可以预处理出来。
(Ans = sum_{i = 1}^{i leq n}sum_{j = 0}^{cnt[i]}sum_{o = 0}^{o < c} f_{j, o} imes P_{cnt[i], j} imes o)
code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 110;
const double eps = 1e-7;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, c, k, cnt[MAXN];
double C[MAXN][MAXN], P[MAXN][MAXN], Ans;
void Init_C() {
C[0][0] = 1;
for (int i = 1; i <= 100; i++) {
C[i][0] = 1;
C[i][0] = C[i][0] / 2.0;
for (int j = 0; j <= i; j++) {
C[i][j] = C[i - 1][j - 1] / 2.0 + C[i - 1][j] / 2.0;
}
}
}
void Init_P() {
P[0][1] = 1;
for (int i = 0; i <= k; i++)
for (int j = 0; j < c; j++) {
if(P[i][j] <= eps) continue;
for (int o = 0; o < c; o++) {
P[i + 1][j * o % c] = (P[i + 1][j * o % c] + P[i][j] / c);
}
}
}
int main(){
n = read(), c = read(), k = read();
Init_C(), Init_P();
for (int i = 1; i <= k; i++) {
int x = read(), y = read();
for (int j = x; j <= y; j++) cnt[j]++;
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= cnt[i]; j++)
for (int o = 0; o < c; o++) Ans += C[cnt[i]][j] * P[j][o] * o;
printf("%.3lf
", Ans);
return 0;
}
T3 香子兰
solution
直接搬 szt 的了 /cy
你看这个数据范围就知道要状压，你看它要求最短路径就得状压最短路。
我们先跑个 (Folyd) 求出两两之间的最短距离。
我们在设两个数组 (f[S][i],g[S][i]) 分别表示以 (1) 作为出发点，已经进行收割/播种的状态为 (S)，最后一个点为 (i) 的最短距离，(g) 数组则表示以 (n) 为出发点。
上面这个 (f,g) 数组可以预处理出来。时间复杂度为 (O(2^nn^2))，这个复杂度有点危，我们发现我们不用枚举全部的，我们只需要枚举 (S) 中 (1) 的个数 (≤frac{n−2}{2}+2) 的状态即可。复杂度就被我们优化掉一个 (n)（我们本质还是枚举所有子集，只不过在某些子集只做了 (O(n)) Check ）
然后你枚举首先选择哪 (n−2) 个花田收割，设枚举的收割的花田的状态为 (S)。
我们考虑收割的过程，考虑怎么把前一半的最短路和后一半的最短路合并起来，那就是，枚举在集合中的点 (i) 和不在集合中的点 (j)，设答案为 (res)，则：
(res=min{f[S|1][i] + g[M oplus (S|(1<<n−1))][j]+dis[i][j]})
其中 (M) 表示所有点的全集。
这样就保证了 (S) 状态中选中的点一定会在前 (frac{n−2}{2}) 花田里收割，剩余的点在后来收割。
同理，我们考虑播种的过程，其实就是反过来，我们再设一个播种的答案 (ans)，则
(ans=min{g[S|1][i]+f[M oplus (S|(1<<n−1))][j]+dis[i][j]})
最终答案就是 (min{res+ans})。
这个直接上搜索就行，控制一下搜索上限，可以控制复杂度为 (O(2^{frac{n−2}{2}}frac{n−2}{2}^2))。
code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 21;
const int INF = 0x3f3f3f3f3f;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, m, dis[MAXN][MAXN], N, M, Ans = 0x3f3f3f3f;
int f[MAXN][(1 << 20) - 1], g[MAXN][(1 << 20) - 1];
void Init_dis() {
for (int i = 1; i <= n; i++) dis[i][i] = 0;
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
void Init_F() {
memset(f, 0x3f, sizeof f);
f[1][1] = 0;
for (int s = 0; s < (1 << n); s++) {
int cnt = 0;
for (int k = 1; k <= n; k++) if(s & (1 << k - 1)) cnt++;
if (cnt > N + 2) continue;
for (int i = 1; i <= n; i++) {
if(!(s & (1 << i - 1))) continue;
for (int j = 1; j <= n; j++) {
if(s & (1 << j - 1)) continue;
f[j][s | (1 << j - 1)] = min(f[j][s | (1 << j - 1)], f[i][s] + dis[i][j]);
}
}
}
}
void Init_G() {
memset(g, 0x3f, sizeof g);
g[n][1 << n - 1] = 0;
for (int s = 0; s < (1 << n); s++) {
int cnt = 0;
for (int k = 1; k <= n; k++) if(s & (1 << k - 1)) cnt++;
if(cnt > N + 2) continue;
for (int i = 1; i <= n; i++) {
if(!(s & (1 << i - 1))) continue;
for (int j = 1; j <= n; j++) {
if(s & (1 << j - 1)) continue;
g[j][s | (1 << j - 1)] = min(g[j][s | (1 << j - 1)], g[i][s] + dis[i][j]);
}
}
}
}
int In[MAXN], Out[MAXN], Incnt, Outcnt;
void dfs(int s, int pos, int cnt) {
if(cnt > N) return ;
if(pos == n) {
if(cnt != N) return ;
int ret_1 = INF, ret_2 = INF;
for (int i = 1; i <= Incnt; i++) {
for (int j = 1; j <= Outcnt; j++) {
int x = In[i], y = Out[j];
ret_1 = min(ret_1, f[x][s | 1] + g[y][(s | 1) ^ M] + dis[x][y]);
ret_2 = min(ret_2, g[x][s | (1 << n - 1)] + f[y][(s | (1 << n - 1)) ^ M] + dis[x][y]);
}
}
Ans = min(Ans, ret_1 + ret_2);
return ;
}
In[++Incnt] = pos;
dfs(s | (1 << pos - 1), pos + 1, cnt + 1);
Incnt--;
Out[++Outcnt] = pos;
dfs(s, pos + 1, cnt);
Outcnt--;
}
int main(){
n = read(), m = read();
N = (n - 2) / 2, M = (1 << n) - 1;
memset(dis, 0x3f, sizeof dis);
for (int i = 1, u, v, w; i <= m; i++) {
u = read() + 1, v = read() + 1, w = read();
dis[u][v] = dis[v][u] = min(dis[u][v], w);
}
Init_dis();
if(n == 3) {
cout<<(dis[1][2] + dis[2][3]) * 2;
return 0;
}
Init_F(), Init_G();
dfs(0, 2, 0);
cout<<Ans;
return 0;
}