Div. 2 CF Round #829 題解 _生活百科

F 沒看所以擺了 .
看拜月教教主 LHQ 在群里代打恰錢 /bx
目錄

A. Technical Support (*800)
B. Kevin and Permutation (*800)
C. Make Nonzero Sum (C1 *1300, C2 *1500)
D. Factorial Divisibility (*1600)
E. Wish I Knew How to Sort (*2000)

A. Technical Support (*800)SoyTony 強啊 .
維護一個計數器，掃一遍遇到 \(\tt Q\) 加一，遇到 \(\tt A\) 減一，每次要小于 0 了就賦成 0 ，看一下最后計數器是否等于 0 即可 .
正確性顯然 .
B. Kevin and Permutation (*800)構造比較顯然，不太好說，直接放代碼 .

int main(){	int T, n; scanf("%d", &T);	while (T--)	{scanf("%d", &n);for (int i=n; i>=1; i--){if (i & 1 ^ 1) printf("%d ", 1+(i-1)/2);else printf("%d ", 1+i/2+n/2);}puts("");	}	return 0;}

C. Make Nonzero Sum (C1 *1300, C2 *1500)C1, C2 是一樣的 .
首先任何一種拆分方案都可以化成等價的只用長度為 1 和 2 的區間的方案 .
就是對于偶數，兩兩分，對于奇數再分一個 1 出來即可 .
這樣就證明了用 1, 2 構造方案如果構不出來一定無解 .
【Div. 2 CF Round #829 題解】然后先求一下序列之和然后貪心地選一些不相鄰的幸運元素乘上 \(-1\) 即可完成構造 .
聽 SoyTony 說似乎比較難寫？那我放下代碼 .

const int N = 222222;int n, a[N];int main(){	int T; scanf("%d", &T);	while (T--)	{scanf("%d", &n); int s = 0;for (int i=1; i<=n; i++) scanf("%d", a+i), s += a[i];int k=0;string ans;char tmp[114514];for (int i=1; i<=n; i++){if ((s * a[i+1] > 0) && (i != n)){sprintf(tmp, "%d %d\n", i, i+1); ++k; ++i; s -= 2 * a[i];}else{sprintf(tmp, "%d %d\n", i, i); ++k;}ans += tmp;}if (s){puts("-1"); continue;}else printf("%d\n%s", k, ans.c_str());	}	return 0;}

D. Factorial Divisibility (*1600)感性理解一下，直接暴力合并判斷 .
具體的，

const int N = 522222;int n, k, a[N], z[N];int main(){	scanf("%d%d", &n, &k);	for (int i=1; i<=n; i++) ++z[read<int>()];	for (int i=1; i<k; i++)	{z[i+1] += z[i] / (i+1);if (z[i] % (i+1)){puts("No"); return 0;}	}	puts("Yes");	return 0;}

E. Wish I Knew How to Sort (*2000)令序列中有 \(c\) 個 \(0\)，目前前 \(c\) 個數有 \(x\) 個 \(1\)，然后要排序就需要 \(x\) 次有效交換 .
減少一個 \(1\) 的概率是 \(\dfrac{x^2}{\dbinom n2}\)
令 \(dp_i\) 還剩 \(i\) 次有效交換的的期望，則
\[dp_{i-1}=\frac{i^2}{\frac{n(n-1)}{2}}\times f_i+\frac{\frac{n(n-1)}{2}-i^2}{\frac{n(n-1)}{2}}\times dp_{i-1}+1\]移項，經過化簡可以得到答案是 \(\displaystyle\dbinom n2\sum_{i=1}^x\dfrac1{i^2}\) .
暴力算一下就是 \(\Theta(n)\) 的 .