Summary:

Make an expectation dp /se

Examination process:

After reading T1 and ahhhhhhhh in 5 min utes, sign in the question, and write it in 10 min utes. One too large example is sent.

8: 20 open dry T2, expect dp, after reading the questions, I feel I can do it.

I wrote it for a long time, adjusted the sample, wrote the opposite shot, and hung it as soon as I took it, rnm.

Adjust for half a day, transfer write hang ==

10: 10 open T3

T3 topic is so strange. Why is T2 topic at the beginning? It's useless. It's deleted.

Shit, where is the flower shop and my home? Why can't I find my home!! Children who can't find home

After reading it several times, I didn't understand the problem. I got numb and went to sleep.

After the game: Why did I miss a natural paragraph in T3!!!!

## T1 three-way city

solution

Touch the topic and you find that this is a full binary tree.

Then you will find that his layers are actually very few.

You will also find that the father of each node is to change node / 2

Then you jump up violently ==

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<<"\n"; } return 0; }

## T2 soul painter

solution

Expectation = probability * weight

Obviously, the weight is the color. Consider how to calculate the probability that each position becomes a color.

It is not difficult to find out which color a position becomes only related to the number of times it is selected.

Let \ (P {i, j} \) represent the probability that a point of \ (i \) appears in \ (i \) intervals and is selected \ (j \) times.

Obviously \ (P {I, J} = \ frac {C {I} ^ {J} {2} \)

Let \ (f_{i, j} \) represent the probability that \ (I \) is selected for times and becomes color \ (j \).

\(f_{i + 1, j \times o \% c} += f_{i, j} / c\)

\(P \) and \ (f \) can be preprocessed.

\(Ans = \sum_{i = 1}^{i \leq n}\sum_{j = 0}^{cnt[i]}\sum_{o = 0}^{o < c} f_{j, o} \times P_{cnt[i], j} \times 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\n", Ans); return 0; }

## T3 Vanilla

solution

Move szt directly / cy

If you look at this data range, you can see that the shape voltage is required. If it requires the shortest path, it must have the shortest shape voltage.

Let's run a \ (Folyd \) to find the shortest distance between two pairs.

We are setting two arrays \ (f[S][i],g[S][i] \) to represent \ (1 \) as the starting point, the state of harvesting / sowing is \ (s \), the last point is the shortest distance of \ (I \), and the \ (g \) array represents \ (n \) as the starting point.

The above \ (f,g \) array can be preprocessed. The time complexity is \ (O(2^nn^2) \), which is a bit dangerous. We find that we don't need to enumerate all, we just need to enumerate the number of \ (1 \) in \ (S \) (≤ \ frac{n − 2}{2} + 2 \). The complexity is optimized by one \ (n \) (we still enumerate all subsets, but only do \ (O(n)\) Check on some subsets)

Then you enumerate which \ (n − 2 \) flower fields to harvest first, and set the status of the enumerated harvested flower fields to \ (S \).

We consider the harvesting process and how to combine the shortest path of the first half and the shortest path of the second half, that is, enumerate the points \ (i \) in the set and the points \ (j \) not in the set, and set the answer to \ (res \), then:

\(res=min\{f[S|1][i] + g[M \oplus (S|(1<<n−1))][j]+dis[i][j]\}\)

Where \ (M \) represents the complete set of all points.

This ensures that the selected points in the \ (S \) state will be harvested in the front \ (\ frac{n − 2} {2} \) flower field, and the remaining points will be harvested later.

Similarly, when we consider the process of sowing, in fact, it is the reverse. We set another sowing answer \ (ans \), then

\(ans=\min\{g[S|1][i]+f[M \oplus (S|(1<<n−1))][j]+dis[i][j]\}\)

The final answer is \ (min\{res+ans \} \).

Just search directly. Control the upper search limit and control the complexity to \ (O(2^{\frac{n − 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; }