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 构造方案如果构不出来一定无解 .
然后先求一下序列之和然后贪心地选一些不相邻的幸运元素乘上 \(-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)\) 的 .
标签：main,frac,int,题解,scanf,829,Div,800,dp From： https://www.cnblogs.com/CDOI-24374/p/16830167.html