专栏文章

题解：P1943 Local Maxima

PPengzt
P1943题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8k2cz
此快照首次捕获于
2025/12/01 22:19
3 个月前
此快照最后确认于
2025/12/01 22:19
3 个月前
查看原文

P1943 Local Maxima

Problem
求一个排列的期望的前缀最值个数。
Sol
法一：
我们分段计算贡献。
对于第 pp 位，贡献的期望为：
∑i=pnAi−1p−1(n−p)!n!\sum_{i = p}^{n} \frac{A_{i-1}^{p-1}(n-p)!}{n!} =∑i=pn(i−1)!(n−p)!n!(i−p)!=\sum_{i = p}^{n} \frac{(i-1)!(n-p)!}{n!(i-p)!}
先提出 n,pn, p：
=(n−p)!n!∑i=pn(i−1)!(i−p)!=\frac{(n-p)!}{n!}\sum_{i = p}^{n} \frac{(i-1)!}{(i-p)!}
发现是两个与 nn，ii 相关的排列数，且差为 p,p−1p, p-1。可以考虑化为组合数。
=(n−p)!(p−1)!n!∑i=pn(i−1i−p)=\frac{(n-p)!(p-1)!}{n!}\sum_{i = p}^{n} \binom{i-1}{i-p}
然后 ∑i≥0(i+ki)=∑i≥0(i+kk)=(n+k+1k+1)\sum_{i\ge0}\binom{i+k}{i}=\sum_{i\ge0}\binom{i+k}{k}=\binom{n+k+1}{k+1}
=(n−p)!(p−1)!n!(np)=\frac{(n-p)!(p-1)!}{n!}\binom{n}{p} =1p=\frac{1}p
因此答案为 ∑i1i\sum_{i} \frac1i。
法二：
DP。令 fif_i 表示长为 ii 的排列的答案。考虑插入第 i+1i+1 个数。
如果插入位置在最后，局部最大值应 +1+1。如果插入的位置不在最后，前面的部分可以看成一个排列，然后最后一个数没有贡献。因此有转移：fi+1=1i+1(fi+1+ifi)=fi+1i+1f_{i+1}=\frac1{i+1}(f_i+1+if_{i})=f_i+\frac1{i+1}。通项即为 ∑i1i\sum_i \frac 1i。
分段打表即可。
Code
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld table[] = { 0, 17.38845852, 18.08160569, 18.48707079, 18.77475286, 18.99789641, 19.18021797, 19.33436865, 19.46790004, 19.58568308, 19.69104359, 19.78635377, 19.87336515, 19.95340786, 20.02751583, 20.09650870, 20.16104722, 20.22167184, 20.27883026, 20.33289748, 20.38419077, 20.43298094, 20.47950095, 20.52395271, 20.56651233, 20.60733432, 20.64655504, 20.68429536, 20.72066301, 20.75575433, 20.78965588, 20.82244570, 20.85419440, 20.88496606, 20.91481902, 20.94380656, 20.97197744, 20.99937641, 21.02604466, 21.05202014, 21.07733795, 21.10203056, 21.12612812, 21.14965861, 21.17264813, 21.19512099, 21.21709989, 21.23860610, 21.25965951, 21.28027880, 21.30048150, 21.32028413, 21.33970222, 21.35875041, 21.37744254, 21.39579168, 21.41381019, 21.43150976, 21.44890151, 21.46599594, 21.48280306, 21.49933236, 21.51559288, 21.53159322, 21.54734158, 21.56284577, 21.57811324, 21.59315112, 21.60796620, 21.62256500, 21.63695374, 21.65113837, 21.66512462, 21.67891794, 21.69252359, 21.70594661, 21.71919184, 21.73226392, 21.74516732, 21.75790635, 21.77048513, 21.78290765, 21.79517774, 21.80729910, 21.81927530, 21.83110975, 21.84280579, 21.85436662, 21.86579531, 21.87709487, 21.88826817, 21.89931800, 21.91024707, 21.92105799, 21.93175328, 21.94233539, 21.95280669, 21.96316948, 21.97342598, 21.98357835, 21.99362868, 22.00357901, 22.01343131, 22.02318748, 22.03284940, 22.04241885, 22.05189759, 22.06128733 };
int n;
int main() {
	scanf("%d", &n);
	int B = 20000000;
	ld ans = table[n / B];
	for (int i = n / B * B + 1; i <= n; i++) ans += (ld)1 / i;
	printf("%.8Lf\n", ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...