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 imes h \% c]。)
最后的答案=(sum f[b[i]][i][j] imes j) ，(b[i]) 表示 (i) 位置被操作了多少次。
时间复杂度 (O(n ^ 4))。
/*
Date:
Source:
Knowledge:
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define orz cout << "AK IOI" << "
"
#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" << "
"
#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" << "
"
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
", 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;
}