A Game
题意：A,B各自拥有两堆石子，数目分别为n1, n2，每次至少取1个，最多分别取k1,k2个, A先取，最后谁会赢。
分析：显然每次取一个是最优的，n1 > n2时，先手赢。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT; int main() {
// in
int n1, n2, k1, k2;
cin >> n1 >> n2 >> k1 >> k2;
puts(n1 > n2 ? "First" : "Second"); return ;
}
B1, B2 Permutations
题意：给定排列长度 n <= 50, ,要求输出字典序第m大的排列,同时使得f(p)最大。
分析：
首先肯定的是应该从小到大，将每个数往剩余位置的两边放。反证法，如果将较小的放在中间，那么被各个区间包含的次数会比较多，结果会比较小，而将小的放在两边结果至少不会变小。
所以最多2^(n-1)个可能值，首先考虑1的放置，如果m > 2^(n-2)则放置在末尾，其他数同样考虑。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT; int main() { vector<int> ans();
int n, m;
cin >> n >> m;
int l = , r = n;
for(int i = (n-); i > ; i--){
if(m <= (<<(i-))) {
ans[l++] = n-i;
}else {
ans[r--] = n-i;
m -= (<<(i-));
}
}
ans[l] = n;
for(int i = ; i <= n; i++)
printf("%d ", ans[i]);
return ;
}
C Second price auction
题意：n个区间(2 <= n <= 5), [Li, Ri](Ri <= 10000)，每个区间中随机选出一个整数，求第二大的数的数学期望。
分析：
比赛时做的比较复杂，但还是通过了。具体分为两种情况，最大值唯一和不唯一。
最大值唯一时：
用st表示此时除开最大值的是那些区间，然后dp[i][st]表示这些区间中最大值为i时的概率。
最大值不唯一：
只需要枚举那些区间为最大值，及最大值，计算期望即可。
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT;
const int maxn = + ; double dp[maxn][(<<)+];
int L[], R[];
int n;
double getProb(int st, int m) {
vector<int> comp;
for(int i = ; i < n; i++) if(st&(<<i))
comp.pb(i);
int nn = sz(comp);
double res = 0.0;
for(int x = ; x < (<<nn); x++) {
// vector<int> tmp;
double tmpPro = 1.0;
int ok = ;
for(int j = ; j < nn; j++) if(x&(<<j)) {
// tmp.pb(comp[j]);
// cout << L[comp[j]] << ' ' << R[comp[j]] << endl;
if(m < L[comp[j]] || m > R[comp[j]]) {
ok = ;
// bug(1)
break;
}
tmpPro *= 1.0/(R[comp[j]]-L[comp[j]] + ); } else {
if(m <= L[comp[j]]) {
ok = ;
break;
}
tmpPro *= 1.0*(min(R[comp[j]]+, m)-L[comp[j]])/(R[comp[j]]-L[comp[j]] + );
}
if(ok) {
// cout << tmpPro << endl;
res += tmpPro;
}
}
return res;
}
int main() {
// in
cin >> n;
int mx = , mi = inf;
for(int i = ; i < n; i++) {
cin >> L[i] >> R[i];
mi = min(mi, L[i]);
mx = max(mx, R[i]);
}
for(int i = ; i < (<<n); i++) {
for(int j = mi; j <= mx; j++)
dp[j][i] = getProb(i, j);
}
// cout << getProb(5, 7) << endl;
// cout << dp[7][5] << endl;
double ans = 0.0;
int mask = (<<n)-;
for(int k = ; k < n; k++) {
for(int l = mi; l < R[k]; l++) {
// if(k == 1) cout << l << ' ' << dp[l][mask^(1<<k)] << endl;
ans += dp[l][mask^(<<k)]*l*(R[k]-max(L[k]-, l))/(R[k]-L[k]+);
}
}
// cout << ans << endl;
for(int i = mi; i <= mx; i++) {
for(int st = ; st < (<<n); st++) {
int ok = ;
double tmp = 1.0;
for(int x = ; x < n; x++) if((st&(<<x))) {
// ct++;
if(i < L[x] || i > R[x]) {
ok = ;
break;
}
tmp *= 1.0/(R[x]-L[x]+);
} else {
if(i <= L[x]) {
ok = ;
break;
}
tmp *= 1.0*(min(R[x]+,i)-L[x])/(R[x]-L[x]+);
}
if(ok && __builtin_popcount(st) >= ) {
ans += tmp*i;
}
}
}
printf("%.12f\n", ans);
return ;
}
D1, D2 Constrained Tree
题意：先序遍历的方式给二叉树标号，一些限制描述：ai bi LEFT or ai bi RIGHT表示bi位于ai的左子树或右子树，构造一棵满足条件的二叉树，中序遍历输出结点编号。
分析：对输入的描述处理，maxL[i]表示位于i结点左子树的点的最大编号，minR[i]，maxR[i]，表示i右子树结点最小和最大编号。
那么构造时，dfs(rt, must, no)记录rt为根的子树的3个信息，rt， must表示必须包含的点，no表示结点编号不能超过，对于根为rt的子树，其maxL[rt] < minR[rt]，并且当
进行构造时，要用maxR[rt]更新must。
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT;
const int maxn = + ;
const int maxm = + ;
int a[maxm], b[maxm], c[maxm];
int maxL[maxn], maxR[maxn], minR[maxn];
vector<int> ans;
int solve(int rt, int must, int no){
if(must < maxR[rt])
must = maxR[rt];
if(must >= no) {
puts("IMPOSSIBLE");
exit();
}
int last = rt;
if(maxL[rt])
last = solve(rt+, maxL[rt], minR[rt] ? minR[rt] : no);
if(!last) {
puts("IMPOSSIBLE");
exit();
}
ans.pb(rt);
if(must >= last+)
return solve(last+, must, no);
return last;
}
int main(){
// in
int n, m;
cin >> n >> m;
for(int i = ; i < m; i++){
static char s[];
scanf("%d%d%s", a+i, b+i, s);
if(s[] == 'L') maxL[a[i]] = max(maxL[a[i]], b[i]);
else {
maxR[a[i]] = max(maxR[a[i]], b[i]);
if(!minR[a[i]] || b[i] < minR[a[i]])
minR[a[i]] = b[i];
}
if(a[i] >= b[i] || (minR[a[i]] && maxL[a[i]] >= minR[a[i]]))
{
puts("IMPOSSIBLE");
return ;
}
}
solve(, n, n+);
for(int x: ans)
printf("%d ", x);
return ;
}
E1, E2 Subarray Cuts
题意：一个长度为n的数组，依次选取连续的k部分（ k >= 2)，si表示第i部分的和，要求 最大。
分析：官方题解对于E1的解法用到了另一种结论，便是只需要考虑选取m个部分，m <= k， ( + s1 - 2·s2 + 2·s3 - 2·s4 + …) and ( - s1 + 2·s2 - 2·s3 + 2·s4 - …)的大小，且剩下的没有选取的元素>=k-m即可。采用dp即可解决，dp[i][sign][first][last][unused][max]， 表示从第i个元素开始，选取max个部分的最大值。
对于E2有另一种解法，,
f(i, j, c1, c2) = max(... ± (sj -1 - sj -2)±c2(sj - sj - 1) ± c1 (0 - sj)...), 选取ai作为sj的一部分时，
f(i, j, c1, c2) = max(... ± (sj -1 - sj -2)±c2(sj - sj - 1) ± c1 (0 - sj)...)
= max(... ± (sj -1 - sj -2)±c2(0- sj - 1) ± c2sj+c1 (0 - sj)...)
= max(... ± (sj -1 - sj -2)±c2(0- sj - 1) ± (c2-c1)ai...) ，
f[c1][c2][k]表示从第i个往后选取sk时的最大值，g[c1][k] 表示max(f[c1][c2][k])，即当前选取sk后最大值，
更新时，f[c1][c2][k] = max(f[c1][c2][k], g[c1][k-1]) + (c2-c1)*a[k]。
虽然dp时没有确定各项前的符号，但是绝对值会是>=0, 因此最后得到最大值一定是将前面的c1, c2一定使得各项为>=0的，所以使能够得到最大值的。
题解看了不是很明白，上面的思路属于Petr的代码的，看了觉得理解了就将其按照理解写了一下。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT;
const int maxn = + ;
const int maxm = + ;
int a[maxn], f[][][maxm], g[][maxm];
int main() {
// inC
int n, k;
cin >> n >> k;
for (int i = ; i <= n; i++) scanf("%d", a+i);
for(int i = ; i < maxm; i++) for(int j = ; j < ; j++) {
g[j][i] = -inf;
for(int u = ; u < ; u++)
f[u][j][i] = -inf;
} g[][] = g[][] = ;//init by 0
for (int cur = ; cur <= n; ++cur) {
for (int u = ; u <= k; u++)
for (int now = ; now < ; now++)
for (int pre = ; pre < ; pre++) {
int e = (u == ? : *pre-);
e += (u == k ? : -*now);
f[now][pre][u] = max(f[now][pre][u], g[pre][u-]) + e*a[cur];
}
for(int now = ; now < ; now++)
for(int u = ; u <= k; u++) {
g[now][u] = max(g[now][u], max(f[now][][u], f[now][][u]));
}
}
printf("%d\n", max(g[][k], g[][k]));
return ;
}
F1,F2 Scaygerboss
题意：males,female只雄蜂，雌蜂，及蜂王，位于一个n*m的迷宫，每只蜂可以移动到相邻位置上，时间为t，有障碍物的格子不能移动上去，要求能否每一只蜂和另外一只性别不同的蜂处于同一格子，且移动的最大时间最小。
分析：首先根据males和females的数目，将蜂王看做雌性或雄性（少的那一种），如果两种数目仍然不相等，则显然不会满足条件。
然后，构建网络流图，(src, sink)， src->males，容量为1，females-sink，容量为1，然后将每个空格子拆成两点，u,v,males->u, 及v->females表示占领该格子，u->v容量为1，当然为了求最小时间，需二分可能的时间，只有当males，females到相应格子时间<=二分值时才连相应的边，最大流的值 == males时表示可行。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
#define INF 0x0f0f0f0f0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT; const int maxn = ;
const int maxm = ; char maze[maxn][maxn];
int g[maxn*maxn][maxn*maxn];
int n, m, N, M;
int src, sink; LL ans; struct Node {
int r, c, t;
Node() {}
Node(int r, int c, int t):r(r), c(c), t(t) {}
};
vector<Node> males, fmales; struct Edge {
int u, v, c;
Edge() {}
Edge(int u, int v, int c):u(u), v(v), c(c) {}
}; struct MaxFlow {
int n, m;
int Now[maxm], Dfn[maxm], Cur[maxm]; vector<Edge> edges;
vector<int> G[maxm];//border ! void init(int n) {
this->n = n;
for(auto &x: G)
x.clear();
edges.clear();
} void add(int u, int v, int c) {
// cout << u << '-' << v << endl;
edges.pb(Edge(u, v, c));
edges.pb(Edge(v, u, ));
m = sz(edges);
G[u].pb(m-);
G[v].pb(m-);
} int ISAP(int s, int flow){
if(s == sink) return flow;
int v, tab = n, now = , vary;
int p = Cur[s], &q = Cur[s];
do{
Edge &e = edges[G[s][q]];
if(e.c > ){
if(Dfn[s] == Dfn[v = e.v] + )
vary = ISAP(v, min(flow-now, e.c)), now += vary,
e.c -= vary, edges[G[s][q]^].c += vary;
if(Dfn[src] == n) return now;
if(e.c > ) tab = min(tab, Dfn[v]); }
if(++q == sz(G[s])) q = ;
if(now == flow) break;
}
while(p != q);
if(now == ){
if(--Now[Dfn[s]] == )
Dfn[src] = n;
++Now[Dfn[s] = tab+];
}
return now;
}
int getAns() {
int flow = ;
memset(Dfn, , sizeof Dfn);
memset(Now, , sizeof Now);
memset(Cur, , sizeof Cur);
Now[] = n;
while(Dfn[src] < n) flow += ISAP(src, inf);
return flow;
}
} solver; int idx(char x, int y) {
return x*m+y;
}
bool cango(int x, int y) {
return x >= && x < n && y >= && y < m;
}
int dx[] = {, , -, };
int dy[] = {-, , , }; void calDist() {
memset(g, 0x0f, sizeof g);
for(int i = ; i < n*m; i++) g[i][i] = ;
for(int x = ; x < n; x++)
for(int y = ; y < m; y++) {
if(maze[x][y] != '.') continue;
int u = idx(x, y);
for(int k = ; k < ; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if(!cango(nx, ny) || maze[nx][ny] == '#') continue;
int v = idx(nx, ny);
g[u][v] = ;
}
}
for(int k = ; k < n*m; k++)
for(int i = ; i < n*m; i++)
for(int j = ; j < n*m; j++) {
if(g[i][k] == inf|| g[k][j] == inf)
continue;
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
bool check(LL mid) {
src = *N+*n*m;
sink = src + ;
solver.init(sink+);
for(int j = ; j < n; j++) for(int k = ; k < m; k++) {
if(maze[j][k] == '#') continue; int v = idx(j, k);
int id1 = *N+v*;
int id2 = id1 + ;
solver.add(id1, id2, );
}
// bug(1)
for(int i = ; i < N; i++) {
int x = males[i].r, y = males[i].c, t = males[i].t;
int u = idx(x, y); solver.add(src, i, );
for(int j = ; j < n; j++) for(int k = ; k < m; k++) {
if(maze[j][k] == '#') continue;
int v = idx(j, k);
// if(u == v) continue;
int id1 = *N+v*;
int id2 = id1 + ;
// cout << id1 << id2 << endl;
// cout << u << v << endl;
if(g[u][v] != inf && 1.0*g[u][v]*t <= mid)
solver.add(i, id1, );
}
x = fmales[i].r, y = fmales[i].c, t = fmales[i].t;
u = idx(x, y);
solver.add(i+N, sink, );
for(int j = ; j < n; j++) for(int k = ; k < m; k++) {
if(maze[j][k] == '#') continue;
int v = idx(j, k);
int id1 = *N+v*;
int id2 = id1 + ;
if(g[u][v] != inf && 1.0*g[u][v]*t <= mid)
solver.add(id2, i+N, );
}
}
// bug(1)
return solver.getAns() == N;
}
int main() {
// in cin >> n >> m >> N >> M; for(int i = ; i < n; i++) scanf("%s", maze[i]);
int ok = ;
int r, c, t;
scanf("%d%d%d", &r, &c, &t);
r--, c--;
if(N-M == ) {
fmales.pb(Node(r, c, t));
} else if(M-N == ) {
males.pb(Node(r, c, t));
} else {
ok = ;
}
for(int i = ; i < N; i++) {
scanf("%d%d%d", &r, &c, &t);
r--, c--;
males.pb(Node(r, c, t));
}
for(int i = ; i < M; i++) {
int r, c, t;
scanf("%d%d%d", &r, &c, &t);
r--, c--;
fmales.pb(Node(r, c, t));
} if(!ok) {
puts("-1");
return ;
}
N = max(N, M);
calDist();
LL L = , R = (LL)1e15;
// cout << check(R) << endl;
//bug(1)
while(R-L > ){
LL mid = (L+R)>>; if(check(mid)) R = mid;
else L = mid+;
}
if(R != (LL)1e15) {
printf("%lld\n", R);
} else puts("-1");
return ;
}
G1, G2, G3 Inversions problem
题意：给定长度为n的排列，及k，表示每次可以选取一个区间[li, ri]将其中的数位置反转，求进行k次后逆序对的个数的期望值。
分析：
G1 由于n <= 6, k <= 4, 所以可以直接dp，dp[perm][m]表示排列为perm时，进行m次操作后逆序对的期望值，或者直接模拟每次操作也行。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT;
const int maxn = ; int a[maxn];
int l[maxn], r[maxn];
double ans;
int n, k, cnt; int getInv(int *a) {
int res = ;
for(int i = ; i <= n; i++) for(int j = i+; j <= n; j++)
if(a[i] > a[j]) res++;
return res;
}
void rev(int *src, int *tar, int l, int r) {
for(int i = ; i <= n; i++) tar[i] = src[i];
reverse(tar+l, tar+r+);
}
void dfs(int y, int *src) {
int tar[maxn];
if(y == k) {
for(int i = ; i <= n; i++) tar[i] = src[i];
ans += getInv(tar);
return;
}
for(int i = ; i < cnt; i++) {
rev(src, tar, l[i], r[i]);
dfs(y+, tar);
}
}
int main() {
// in
cin >> n >> k;
for(int i = ; i <= n; i++)
scanf("%d", a+i); for(int i = ; i <= n; i++)
for(int j = i; j <= n; j++)
l[cnt] = i, r[cnt++] = j;
dfs(, a);
for(int i = ; i < k; i++)
ans /= cnt;
printf("%.12f\n", ans);
return ;
}
G2 n <= 30, k <= 200, 数据增大之后肯定不能计算最终排列中逆序对的个数，然后求期望。
可以考虑原排列中x, y dp[x][y][k]表示进行k次操作之后，x, y在原数组中的元素依然能保持原顺序的概率。
这样选取区间[l, r]，转移时4种情况，
1) 区间不反转x 或 y --------- y < l || x > r || (x < l && y > r)
2) 区间仅覆盖x----------------l <= x && x <= r && y >r
3) 区间仅覆盖y----------------l <= y && y <= r && x < l
4) 区间覆盖x和y---------------l <= x && x < y && y <= r
复杂度O(n^4*k)
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
#define INF 0x0f0f0f0f0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT; const int maxn = + ;
const int maxm = ;
double dp[maxn][maxn][maxm]; int a[maxn];
int n; int main() {
// in
int m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%d", a+i);
}
double ans = 0.0;
for(int i = ; i < maxn; i++) for(int j = ; j < maxn; j++)
dp[i][j][] = ;
for(int k = ; k <= m; k++)
for(int x = ; x <= n; x++) for(int y = x+; y <= n; y++) {
double &res = dp[x][y][k];
for(int l = ; l <= n; l++) for(int r = l; r <= n; r++)
if((l > y) || (l > x && r < y) || r < x)
res += dp[x][y][k-];
else if(l <= x && x <= r && y > r)
res += dp[r+l-x][y][k-];
else if(l <= y && y <= r && x < l)
res += dp[x][r+l-y][k-];
else if(l <= x && y <= r) res += -dp[r+l-y][r+l-x][k-];
res *= 2.0/(n+)/n;
}
for(int i = ; i <= n; i++) for(int j = i+; j <= n; j++)
if(a[i] > a[j]) ans += dp[i][j][m];
else ans += -dp[i][j][m];
printf("%.12f\n", ans);
return ;
}
G3 <= 200，k <= (int)1e9, G3的做法是在上面进行改进的，主要是针对转移部分，计算出转移到dp[x'][y'][k-1]的数目。复杂度O(n^3*k)
因为结果会收敛趋于稳定，所以k可取min(k, 1000)，但是
改进后代码还是TLE on test 38。估计优化还不够， 对比他人的代码，冗余运算太多。
上一下代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
#define INF 0x0f0f0f0f0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT; const int maxn = + ;
const int maxm = ;
double dp[maxn][maxn][maxm]; int a[maxn];
int n; int main() { int m;
scanf("%d%d", &n, &m);
m = min(m, );
for(int i = ; i <= n; i++) {
scanf("%d", a+i);
}
double ans = 0.0;
for(int i = ; i < maxn; i++) for(int j = ; j < maxn; j++)
dp[i][j][] = ;
for(int k = ; k <= m; k++)
// int k = 1;
for(int x = ; x <= n; x++) for(int y = x+; y <= n; y++)
{
double &res = dp[x][y][k]; //completely not cover [x, y],
res += dp[x][y][k-]*((n-y)*(n-y+)/+(x-)*x/+(y-x-)*(y-x)/);
// cout << ((n-y)*(n-y+1)/2+(x-1)*x/2+(y-x-1)*(y-x)/2) << endl;
// cout << res << endl;
//cover x, not cover y,
for(int l = ; l < y; l++) {
if((l<<)-x > && (l<<)-x < y) {
int cnt = min(y-(l<<)+x, y-x);
cnt = min(cnt, min((l<<)-x, x));
assert(cnt >= );
res += dp[(l<<)-x][y][k-]*cnt;
} if((l<<|)-x > && (l<<|)-x < y) {
int cnt = min(y-(l<<|)+x, y-x);
cnt = min(cnt, min((l<<|)-x, x));
assert(cnt >= );
res += dp[(l<<|)-x][y][k-]*cnt;
} }
//cover y, not cover x,
for(int l = x+; l <= n; l++) {
if((l<<)-y > x && (l<<)-y <= n) {
int cnt = min(n+-(l<<)+y, n+-y);
// cout << cnt << endl;
cnt = min(cnt, min((l<<)-y-x, y-x));
assert(cnt >= );
// bug(1)
res += dp[x][(l<<)-y][k-]*cnt;
}
// cout << res << endl;
if((l<<|)-y > x && (l<<|)-y <= n) {
int cnt = min(n+-(l<<|)+y, n+-y);
cnt = min(cnt, min((l<<|)-y-x, y-x));
assert(cnt >= );
res += dp[x][(l<<|)-y][k-]*cnt;
}
// cout << res << endl;
}
// cout << res << endl;
//cover [x, y].
for(int l = ; l <= n; l++) {
if((l<<)-x > && (l<<)-x <= n
&&(l<<)-y > && (l<<)-y <= n) { int cnt = min(n+-(l<<)+y, n+-y);
cnt = min(cnt, min((l<<)-y, y));
cnt = min(cnt, min(n+-(l<<)+x, n+-x));
cnt = min(cnt, min((l<<)-x, x));
assert(cnt >= );
// cout << cnt << endl;
res += (-dp[(l<<)-y][(l<<)-x][k-])*cnt;
}
if((l<<|)-x > && (l<<|)-x <= n
&&(l<<|)-y > && (l<<|)-y <= n) {
int cnt = min(n+-(l<<|)+y, n+-y);
cnt = min(cnt, min((l<<|)-y, y));
cnt = min(cnt, min(n+-(l<<|)+x, n+-x));
cnt = min(cnt, min((l<<|)-x, x));
assert(cnt >= );
res += (-dp[(l<<|)-y][(l<<|)-x][k-])*cnt;
}
}
res *= 2.0/(n+)/n;
}
for(int i = ; i <= n; i++) for(int j = i+; j <= n; j++)
if(a[i] > a[j]) ans += dp[i][j][m];
else ans += -dp[i][j][m];
printf("%.12f\n", ans);
return ;
}