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 的区间的方案 .
【Div. 2 CF Round #829 题解】就是对于偶数，两两分，对于奇数再分一个 1 出来即可 .
这样就证明了用 1, 2 构造方案如果构不出来一定无解 .
然后先求一下序列之和然后贪心地选一些不相邻的幸运元素乘上 \(-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)\) 的 .