T1
算出 \(x, y\) 分别是 \(2\) 的幾次方也就是在多少層，讓 \(x, y\) 跳到同一層，當 \(x, y\) 不相等是就向上跳，記錄跳的次數。
T2
機率期望 DP。
首先要發現一個性質，每個位置的顔色于這個位置修改了多少次有關，而與中間的過程沒有關系。
考慮每個位置被選中了多少次？
假設一次作畫，選擇的區間為 \([l, r]\)， 區間的長度為 \(len = r - l + 1\), 考慮一個位置被選中其他的位置随便選的方案數，它會被選中 \(2 ^ {len - 1}\)次， 子集的情況是 \(2 ^ {len}\)，每個位置被選中的機率為 \(\frac 12\)。
\(f[k][i][j]\) 表示操作了 \(k\) 次，第 \(i\) 張畫紙改成顔色 \(j\) 的機率。不改轉移到 \(f[k+1][i][j]\),改轉移到 \(f[k+1][i][j \times h \% c]。\)
最後的答案=\(\sum f[b[i]][i][j] \times j\) ，\(b[i]\) 表示 \(i\) 位置被操作了多少次。
時間複雜度 \(O(n ^ 4)\)。
/*
Date:
Source:
Knowledge:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
const int maxn = 110;
int read()
{
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 ^ '0');
}
int Max(int a, int b){
return a > b ? a : b;
}
int Min(int a, int b){
return a < b ? a : b;
}
int n, c, k, b[maxn];
double ans, f[maxn][maxn][maxn];
signed main()
{
//freopen("paint.in", "r", stdin);
//freopen("paint.out", "w", stdout);
n = read(), c = read(), k = read();
for(int i = 1; i <= k; i++)
{
int l = read(), r = read();
b[l]++, b[r + 1]--;
}
for(int i = 1; i <= n; i++) b[i] += b[i - 1];
for(int i = 1; i <= n; i++) f[0][i][1] = 1;
for(int i = 1; i <= n; i++) //第 i 張
{
for(int j = 0; j < b[i]; j++) // 改動了多少次
{
for(int k = 0; k < c; k++) // 改成什麼顔色
{
f[j + 1][i][k] += f[j][i][k] / 2; // 不改
for(int l = 0; l < c; l++) //改
f[j + 1][i][(k * l) % c] += f[j][i][k] / c / 2;
}
}
}
for(int i = 1; i <= n; i++)
for(int j = 0; j < c; j++)
ans += f[b[i]][i][j] * j;
printf("%.3lf", ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}
優化：
相同顔色的紙改的結果的機率相同，而且開始都是1。
是以 \(i\) 那一維可以壓去,即 \(f[k][j]\) 表示一張紙操作了 \(k\) 次，變成顔色 \(j\) 的機率。
時間複雜度 \(O(n ^3)\)。
/*
Date:
Source:
Knowledge:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define orz cout << "AK IOI" << "\n"
#define int long long
using namespace std;
const int maxn = 110;
int read()
{
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 ^ '0');
}
int Max(int a, int b){
return a > b ? a : b;
}
int Min(int a, int b){
return a < b ? a : b;
}
int n, c, k, b[maxn];
double ans, f[maxn][maxn];
signed main()
{
//freopen("paint.in", "r", stdin);
//freopen("paint.out", "w", stdout);
n = read(), c = read(), k = read();
for(int i = 1; i <= k; i++)
{
int l = read(), r = read();
b[l]++, b[r + 1]--;
}
for(int i = 1; i <= n; i++) b[i] += b[i - 1];
f[0][1] = 1;
for(int j = 0; j < k ; j++) // 改動了多少次
{
for(int k = 0; k < c; k++) // 改成什麼顔色
{
f[j + 1][k] += f[j][k] / 2; // 不改
for(int l = 0; l < c; l++) //改
f[j + 1][(k * l) % c] += f[j][k] / c / 2;
}
}
for(int i = 1; i <= n; i++)
for(int j = 0; j < c; j++) ans += f[b[i]][j] * j;
printf("%.3lf", ans);
//fclose(stdin);
//fclose(stdout);
return 0;
}
T3
30 pts
100
看到資料範圍都很小，可以想到狀壓，又因為題目中要求的是最短距離，是以就想到狀壓最短路。
\(f[i][S]\) 表示從家到點 \(i\)，經過了狀态為 \(S\) 的點集。
\(g[i][S]\) 表示從花店到點 \(i\)，經過了狀态為 \(j\) 的點集。
Floyd 預處理任意兩點間的最短距離 dis。
上面這個 \(f\), \(g\) 數組可以預處理出來。隻需要枚舉 \(S\) 中 \(1\) 的個數 \(\leq \frac {n - 2}2 + 2\)的狀态即可。複雜度就被優化掉一個 n。
然後考慮首先選擇哪 \(\frac {n - 2}2\) 個花田收割，設枚舉的收割的花田的狀态為 S。
我們考慮收割的過程，把前一半的最短路和後一半的最短路合并起來。
直接進行搜尋。
收割過程，$ res1 = min(res1, f[S | 1][x] + g[M ^ (S | 1)][y] + dis[x][y])\(。
播種過程，\)res2 = min(res2, g[S | (1 << n - 1)][x] + f[M ^ (S | (1 << n - 1))][y] + dis[x][y])$。
/*
Date:
Source:
Knowledge:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define orz cout << "AK IOI" << "\n"
using namespace std;
const int maxn = 2e6 + 10;
int read()
{
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
void print(int X)
{
if(X < 0) X = ~(X - 1), putchar('-');
if(X > 9) print(X / 10);
putchar(X % 10 ^ '0');
}
int Max(int a, int b){
return a > b ? a : b;
}
int Min(int a, int b){
return a < b ? a : b;
}
int n, m, N, M, ans = 0x3f3f3f3f;
int dis[22][22], f[maxn][22], g[maxn][22];
int a[22], sc = 0;
int b[22], top = 0;
void dfs(int S, int pos, int cnt)
{
if(cnt > N) return ;
if(pos == n)
{
if(cnt != N) return ;
int res1 = 0x3f3f3f3f, res2 = 0x3f3f3f3f;
for(int i = 1; i <= sc; i++)
{
for(int j = 1; j <= top; j++)
{
int x = a[i], y = b[j];
res1 = min(res1, f[S | 1][x] + g[M ^ (S | 1)][y] + dis[x][y]);
res2 = min(res2, g[S | (1 << n - 1)][x] + f[M ^ (S | (1 << n - 1))][y] + dis[x][y]);
}
}
ans = min(ans, res1 + res2);
return ;
}
a[++sc] = pos;
dfs(S | (1 << pos - 1), pos + 1, cnt + 1);
--sc;
b[++top] = pos;
dfs(S, pos + 1, cnt);
--top;
}
signed main()
{
n = read(), m = read();
N = (n - 2) / 2, M = (1 << n) - 1;
memset(dis, 0x3f, sizeof dis);
for(int i = 1; i <= n; i++) dis[i][i] = 0;
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);
}
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]);
if(n == 3)
{
printf("%lld\n", 1ll * (dis[1][2] + dis[2][3]) * 2);
return 0;
}
memset(f, 63, sizeof f);
f[1][1] = 0;
for(int S = 0; S < (1 << n); S++)
{
int cnt = 0;
for(int i = 1; i <= n; i++) if(S & (1 << i - 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[S | (1 << j - 1)][j] = min(f[S | (1 << j - 1)][j], f[S][i] + dis[i][j]);
}
}
}
memset(g, 63, sizeof g);
g[(1 << n - 1)][n] = 0;
for(int S = 0; S < (1 << n); S++)
{
int cnt = 0;
for(int i = 1; i <= n; i++) if(S & (1 << i - 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[S | (1 << j - 1)][j] = min(g[S | (1 << j - 1)][j], g[S][i] + dis[i][j]);
}
}
}
dfs(0, 2, 0);
printf("%d", ans);
return 0;
}