2020-2021:teams:legal_string:jxm2001:other:结论_3
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:other:结论_3 [2021/07/21 09:35] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:other:结论_3 [2021/08/09 20:50] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| 即 $g\le \frac{\max(a_i)-\min(a_i)}{n-1}$。当 $a_i$ 构成等差序列时有 $\frac {\max(a_i)-\min(a_i)}{n-1}\mid g$，此时有 $\frac {\max(a_i)-\min(a_i)}{n-1}=g$。证毕。 | 即 $g\le \frac{\max(a_i)-\min(a_i)}{n-1}$。当 $a_i$ 构成等差序列时有 $\frac {\max(a_i)-\min(a_i)}{n-1}\mid g$，此时有 $\frac {\max(a_i)-\min(a_i)}{n-1}=g$。证毕。 | ||
| + | |||
| + | ===== 2、数值分配 ===== | ||
| + | |||
| + | 给定序列 $A$，要求构造序列 $B,C$ 使得： | ||
| + | |||
| + | - $a_i=b_i+c_i$ | ||
| + | - 序列 $B$ 非严格单调递增(即不减) | ||
| + | - 序列 $B$ 非严格单调递减(即不增) | ||
| + | |||
| + | 要求最小化 $\sum |b_i|+|c_i|$。则一定存在最优解满足 $b_{i+1}=b_i+\max(a_{i+1}-a_i,0),c_{i+1}=c_i+\min(a_{i+1}-a_i,0)$。具体见 [[https://atcoder.jp/contests/arc123/editorial/2321|证明]]。 | ||
| + | |||
| + | ===== 3、因子个数 ===== | ||
| + | |||
| + | 一个数 $n$ 的因子个数不超过 $O\left(n^{f(n)}\right)$，$f(n)$ 大致递减且 $n$ 比较大时可认为 $f(n)\le \frac 13$，例如 $n\le 10^{18}$ 时因子数至多在 $10^5$ 左右。 | ||
| + | |||
| + | ===== 4、加法运算 ===== | ||
| + | |||
| + | $a+b=a|b+a\And b$ | ||
2020-2021/teams/legal_string/jxm2001/other/结论_3.1626831359.txt.gz · 最后更改: 2021/07/21 09:35 由 jxm2001
