闲言
赛时A-D, C2卡了很久，思路有点糊了，其实还好，D感觉更简单，很容易看出，切了。
A
前面的Q至少后面要有一个A对应。
用cnt来记，是Q就cnt , 是A就cnt = max(cnt-1, 0)
B
其实我乱搞构造的，证明的话可以看cf官方题解，大概就是先反证法证明答案不大于[n/2]，再证明[n/2]可构。
n/2, n, n/2-1, n-1, ...
分奇偶稍微讨论下即可
代码语言：javascript复制for (int i = 0, t = n / 2 n % 2; i < n; i = 2, t--) a[i] = t;
for (int i = 1, t = n; i < n; i = 2, t--) a[i] = t;
for (int x : a) cout << x << ' ';
cout << 'n';C
首先，若|x|==1的个数为奇数位，显然是不可构的。
然后，可以贪心的让每两个非0数，和为0。
当[1,1]，取区间[1, 2]；
当[1,-1]，取区间[1,1]；
有0也是一样的，分类讨论“端点”两数是否相等与中间的0的个数即可。
注意后缀0即可。
我的代码并不简洁，跑了两边一样的，一次统计res，一次过程中输出结果，可以存在vector中
代码语言：javascript复制cnt0 = last = lastp = 0;
for (int i = 0; i < n; i ) {
if (!a[i])
cnt0 ;
else {
if (!last) {
if (i) cout << lastp 1 << ' ' << i << 'n';
last = a[i];
lastp = i;
cnt0 = 0;
continue;
}
if (cnt0 % 2 == 0 && a[i] == last || cnt0 % 2 && a[i] != last)
cout << lastp 1 << ' ' << i 1 << 'n';
else {
cout << lastp 1 << ' ' << lastp 1 << 'n'
<< lastp 2 << ' ' << i 1 << 'n';
}
cnt0 = 0;
last = a[i 1];
lastp = i 1;
i ;
}
}
if (!a[n - 1]) cout << lastp 1 << ' ' << n << 'n';D
注意到n! = n(n-1)!
考虑记录cnt，从小到大递推求能否令cnt[x]有值即可
并且因为是相加，所以，cnt不能有余项，都需要是整除
代码语言：javascript复制for (int &x : a) cin >> x, cnt[x] ;
for (int i = 1; i < x; i ) {
if (cnt[i] % (i 1)) {
cout << "Non";
return;
}
cnt[i 1] = cnt[i] / (i 1);
}
if (cnt[x])
cout << "Yesn";
else
cout << "Non";E
想要达到sorted的状态，需要前面为0，后面为1
先统计下0的个数cnt0，再统计前cnt0位上1的个数
每次的有效操作就是把前面的1与后面的0交换
这个操作的概率是p = frac{2(g-k)^2}{n(n-1)}
i为前cnt0位上的1的数量
f[i] = 1 f[i]·(1-p) f[i-1]·p
化简得
f[i] = frac{1}{p} f[i-1]
代码语言：javascript复制LL tot = n * (n - 1) / 2 % P, ans = 0;
for (LL i = cnt; i >= 1; i--) ans = (ans tot * qpm(i * i, P - 2) % P) % P;
cout << ans << 'n';F
将移动床的操作变化为移动空格的操作。
将原问题就可以转变为一个建立虚拟原点的最短路问题。
代码语言：javascript复制bool ok(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m) return false;
return true;
}
void add(int x, int y, int u, int c) {
if (!ok(x, y)) return;
int v = x * m y;
ver[idx] = u, w[idx] = c, ne[idx] = h[v], h[v] = idx ;
}
// 建图
for (int i = 0; i < n; i )
for (int j = 0; j < m; j ) {
int u = i * m j;
if (g[u] == 'L')
add(i - 1, j 1, u, p), add(i 1, j 1, u, p), add(i, j 2, u, q);
else if (g[u] == 'R')
add(i - 1, j - 1, u, p), add(i 1, j - 1, u, p), add(i, j - 2, u, q);
else if (g[u] == 'U')
add(i 1, j - 1, u, p), add(i 1, j 1, u, p), add(i 2, j, u, q);
else if (g[u] == 'D')
add(i - 1, j - 1, u, p), add(i - 1, j 1, u, p), add(i - 2, j, u, q);
else if (g[u] == '.')
ver[idx] = u, ne[idx] = h[n * m], h[n * m] = idx ;
}
dijkstra(n * m);
for (int i = 0; i < n; i )
for (int j = 0; j < m; j ) {
int u = i * m j;
if (j < m - 1) res = min(res, d[u] d[u 1]);
if (i < n - 1) res = min(res, d[u] d[u m]);
}
