本文主要是介绍CF # 1477 简要题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A
- 求 g c d gcd gcd 即可
B
- 把操作倒过来，容易用线段树维护
C
- 增量构造，每次容易调整为合法解
D
给 m m m 对关系，要求两个排列 p u , p v p_{u},p_v pu,pv 和 q u , q v q_u,q_v qu,qv 的大小关系一样
最大化 p , q p,q p,q 中位置不同的个数
- 考虑这个图的补图，去除一个联通块
若大小为 1 1 1，那么铁定相等了
否则连了边的点之间大小关系是无所谓的
考虑一个菊花图，设根为 u u u，其余点为 v 1 … v k v_1\dots v_k v1…vk
只需要 p u = 1 , q u = k + 1 p_u=1,q_u=k+1 pu=1,qu=k+1
p v i = i + 1 , q v i = i p_{v_i}=i+1,q_{v_i}=i pvi=i+1,qvi=i，这样就实现了错位，且与其它点的大小关系是对的
考虑整一棵 d f s dfs dfs 树出来，我们只需要将其划分成若干菊花依次构造就可以了
E
有两个长为 n , m n,m n,m 的数组 a i , b i a_i,b_i ai,bi，要将其排成一个长为 n + m n+m n+m 的数组
给定一个初始值 w w w，每一次将 w w w 变成 max ( 0 , w + c i − c i − 1 ) \max(0,w+c_i-c_{i-1}) max(0,w+ci−ci−1)（ c 0 = c 1 c_0=c_1 c0=c1）
若干 c i c_i ci 原本是 a a a 中的，则将 a a a 的分数加 w w w，否则 b b b 加 ，求 a − b a-b a−b 分数的最大值
- 每个点的贡献就是 max ( c i − c 1 + k , c i − min j ∈ [ 1 , i ] c j ) \max(c_i-c_1+k,c_i-\min_{j\in [1,i]}c_j) max(ci−c1+k,ci−minj∈[1,i]cj)
我们将这个写成 k + c i − c 1 + max ( 0 , c 1 − k − min j ∈ [ 1 , i ] c j ) k+c_i-c_1+\max(0,c_1-k-\min_{j\in [1,i]}c_j) k+ci−c1+max(0,c1−k−minj∈[1,i]cj)
考虑贪心，枚举一个 a p a_p ap（或 b p b_p bp） 作为第一个，那么一定是 b m , … b 1 b_m,\dots b_1 bm,…b1，然后是 a 1 , … a n a_1,\dots a_n a1,…an
我们将贡献写出来：设 t = a p t=a_p t=ap
( n − m ) k + ( m − n ) t − ∑ i = 1 m max ( 0 , t − k − b i ) + ( n − 1 ) max ( 0 , t − k − min ( a i , b i ) ) + ∑ a i − ∑ b i (n-m)k+(m-n)t-\sum_{i=1}^m\max(0,t-k-b_i)\\+(n-1)\max(0,t-k-\min (a_i,b_i))+\sum a_i-\sum b_i (n−m)k+(m−n)t−∑i=1mmax(0,t−k−bi)+(n−1)max(0,t−k−min(ai,bi))+∑ai−∑bi
( n − m ) k + ( m − n ) t − ∑ i = 1 m max ( 0 , t − k − b i ) + n max ( 0 , t − k − min ( a i , b i ) ) + ∑ a i − ∑ b i (n-m)k+(m-n)t-\sum_{i=1}^m\max(0,t-k-b_i)\\+n\max(0,t-k-\min (a_i,b_i))+\sum a_i-\sum b_i (n−m)k+(m−n)t−∑i=1mmax(0,t−k−bi)+nmax(0,t−k−min(ai,bi))+∑ai−∑bi
注意到这是个关于 t t t 的分段一次函数，我们把所有可能的分段点找出来，用树状数组求和即可
F
有 n n n 个巧克力棍，每个长为 L i L_i Li，每次每根木棍有 L i ∑ L \frac{L_i}{\sum L} ∑LLi 的概率被选中
然后它会被分为两个长为 x , L i − x x,L_i-x x,Li−x 的巧克力棍，其中 x x x 是在 [ 0 , L i ] [0,L_i] [0,Li] 随机的实数
求 max L ≤ K \max L\le K maxL≤K 的期望
- 我们先从简单的问题入手，分析 n = 1 n=1 n=1 的情况
我们不看成将其分成两根，那么问题可以看成随机在 [ 0 , L ] [0,L] [0,L] 切若干刀
注意到我们只需要统计切若干刀任然 max L > K \max L>K maxL>K 的概率，就可以知道答案
下面我们来统计切了 t t t 刀结束了的概率 p t p_t pt，那么 ∑ 1 − p t \sum 1-p_t ∑1−pt 就是答案
我们设 w = K L w=\frac{K}{L} w=LK，然后将 L L L 看成 1 1 1
那么就是有 t + 1 t+1 t+1 个 [ 0 , 1 ] [0,1] [0,1] 的随机变量 x i x_i xi 满足 max ( x i ) ≤ w \max(x_i)\le w max(xi)≤w， ∑ x i = 1 \sum x_i=1 ∑xi=1
看成 t t t 个随机变量， max ( x i ) ≤ 1 , 1 w − 1 ≤ ∑ x i ≤ 1 w \max(x_i)\le 1,\frac 1w-1\le \sum x_i\le \frac 1w max(xi)≤1,w1−1≤∑xi≤w1
我们设 ≤ y \le y ≤y 的概率为 f ( y ) f(y) f(y)，那么求的就是 t ! w t ( f ( 1 w ) − f ( 1 w − 1 ) ) t!w^t\Big(f(\frac 1w)-f(\frac 1w-1)\Big) t!wt(f(w1)−f(w1−1))
对于 f ( y ) f(y) f(y)，我们枚举上界容斥，得到：
f ( y ) = ∑ i = 0 ⌊ y ⌋ ( − 1 ) i ( t i ) ( y − i ) t t ! f(y)=\sum_{i=0}^{\lfloor y\rfloor}(-1)^i\binom ti\frac{(y-i)^t}{t!} f(y)=∑i=0⌊y⌋(−1)i(it)t!(y−i)t
所以说算的就是：
1 − p t = 1 − ( ∑ i = 0 l ( − 1 ) i ( t i ) ( 1 − w i ) t − ∑ i = 0 l − 1 ( − 1 ) i ( t i ) ( 1 − ( i + 1 ) w ) t ) = ∑ i = 1 l ( − 1 ) i − 1 ( ( t i ) + ( t i − 1 ) ) ( 1 − w i ) t = ∑ i = 1 l ( − 1 ) i − 1 ( t + 1 i ) ( 1 − w i ) t 1-p_t=1-\Big(\sum_{i=0}^l(-1)^i\binom ti(1-wi)^t-\sum_{i=0}^{l-1}(-1)^i\binom ti (1-(i+1)w)^t\Big)\\=\sum_{i=1}^l(-1)^{i-1}(\binom{t}{i}+\binom{t}{i-1})(1-wi)^t=\sum_{i=1}^{l}(-1)^{i-1}\binom{t+1}{i}(1-wi)^t 1−pt=1−(∑i=0l(−1)i(it)(1−wi)t−∑i=0l−1(−1)i(it)(1−(i+1)w)t)=∑i=1l(−1)i−1((it)+(i−1t))(1−wi)t=∑i=1l(−1)i−1(it+1)(1−wi)t
现在我们要对 t t t 求和，即需要计算： ∑ t ( t i ) x t = x i ( 1 1 − x ) i + 1 \sum_t \binom{t}{i}x^t=x^i(\frac{1}{1-x})^{i+1} ∑t(it)xt=xi(1−x1)i+1 - 解决多个的问题：
我们设 q i , j q_{i,j} qi,j 表示第 i i i 根，切 j j j 刀，还活着的（存在一段 > K >K >K 的概率）
其中 q i , j = ∑ k = 1 ⌊ L i K ⌋ ( − 1 ) k − 1 ( m + 1 k ) ( 1 − K L i k ) j q_{i,j}=\sum_{k=1}^{\lfloor \frac{L_i}{K}\rfloor}(-1)^{k-1}\binom{m+1}{k}(1-\frac{K}{L_i}k)^j qi,j=∑k=1⌊KLi⌋(−1)k−1(km+1)(1−LiKk)j
设其 E G F EGF EGF 为 Q i ( x ) Q_i(x) Qi(x)，设 p i p_i pi 为总共切 i i i 下还活着的概率， P ( x ) P(x) P(x) 为其 E G F EGF EGF
然后将 Q i ( x ) Q_i(x) Qi(x) 中 x j x^j xj 乘上 ( L i ∑ L ) j (\frac{L_i}{\sum L})^j (∑LLi)j
即 P ( x ) = e x − ∏ i ( e L i ∑ L x − Q i ( x ) ) P(x)=e^x-\prod_i(e^{\frac{L_i}{\sum L}x}-Q_i(x)) P(x)=ex−∏i(e∑LLix−Qi(x))
若要求出答案，我们需要将 P ( x ) P(x) P(x) 换成其 O G F OGF OGF p ( x ) p(x) p(x)，那么答案就是 p ( 1 ) p(1) p(1)
为了得到 p ( x ) p(x) p(x)，我们还需要对 P ( x ) P(x) P(x) 进行化简
exp ( L i L x ) − ∑ t x t t ! ∑ k = 1 ⌊ L i K ⌋ ( − 1 ) k − 1 ( t + 1 k ) ( 1 − K L i k ) t ( L j L ) t = exp ( L i L x ) − ∑ k = 1 ⌊ L i K ⌋ ( − 1 ) k − 1 ( t + 1 k ) ( L i − k K L ) t x t t ! = exp ( L i L x ) − ∑ k = 1 ⌊ L i K ⌋ ( − 1 ) k − 1 t + 1 ( t + 1 − k ) ! k ! ( L i − k K L x ) t \exp(\frac{L_i}{L}x)-\sum_t \frac{x^t}{t!}\sum_{k=1}^{\lfloor\frac{L_i}{K}\rfloor}(-1)^{k-1}\binom{t+1}{k}(1-\frac{K}{L_i}k)^t(\frac{L_j}{L})^t\\=\exp(\frac{L_i}{L}x)-\sum_{k=1}^{\lfloor\frac{L_i}{K}\rfloor}(-1)^{k-1}\binom{t+1}{k}(\frac{L_i-kK}{L})^t\frac{x^t}{t!}\\=\exp(\frac{L_i}{L}x)-\sum_{k=1}^{\lfloor\frac{L_i}{K}\rfloor}(-1)^{k-1}\frac{t+1}{(t+1-k)!k!}(\frac{L_i-kK}{L}x)^t exp(LLix)−∑tt!xt∑k=1⌊KLi⌋(−1)k−1(kt+1)(1−LiKk)t(LLj)t=exp(LLix)−∑k=1⌊KLi⌋(−1)k−1(kt+1)(LLi−kK)tt!xt=exp(LLix)−∑k=1⌊KLi⌋(−1)k−1(t+1−k)!k!t+1(LLi−kKx)t
设 y = L i − k K L x y=\frac{L_i-kK}{L}x y=LLi−kKx，那么就是
exp ( L i L x ) − ∑ k = 1 ⌊ L i K ⌋ ( − 1 ) k − 1 1 k ! y k e y − ∑ k ( − 1 ) k − 1 1 ( k − 1 ) ! y k − 1 e y \exp(\frac{L_i}{L}x)-\sum_{k=1}^{\lfloor\frac{L_i}{K}\rfloor}(-1)^{k-1}\frac{1}{k!}y^ke^y-\sum_{k}(-1)^{k-1}\frac{1}{(k-1)!}y^{k-1}e^y exp(LLix)−∑k=1⌊KLi⌋(−1)k−1k!1ykey−∑k(−1)k−1(k−1)!1yk−1ey
我们将 e L i L x e^{\frac{L_i}{L}x} eLLix 提出来，那么后面都是 e − k K L x e^{\frac{-kK}{L}x} eL−kKx，系数只有 L k \frac{L}{k} kL 种
我们暴力维护系数，复杂度为 O ( n ( L k ) 4 ) \mathcal{O}(n(\frac{L}{k})^4) O(n(kL)4)
注意到 x k x^k xk 和 e − k K L x e^{-\frac{kK}{L}x} e−LkKx 只会有 n n n 的差，所以可以变成 O ( n 2 ( L k ) 2 ) \mathcal{O}(n^2(\frac{L}{k})^2) O(n2(kL)2)
用 n t t ntt ntt 可以优化到 O ( n 2 L log L ) \mathcal{O}(n^2L\log L) O(n2LlogL)
考虑求出 x k e C x x^ke^{Cx} xkeCx 的贡献： ∑ i ≥ 0 ( i + k ) ! C i i ! = k ! ∑ i ≥ 0 ( i + k k ) C i + k = k ! ( 1 1 − C ) k + 1 \sum_{i\ge 0}(i+k)!\frac{C^{i}}{i!}=k!\sum_{i\ge 0}\binom{i+k}{k}C^{i+k}=k!(\frac{1}{1-C})^{k+1} ∑i≥0(i+k)!i!Ci=k!∑i≥0(ki+k)Ci+k=k!(1−C1)k+1
这篇关于CF # 1477 简要题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
