- 1H1B通过率95%，平均薪资170k，还有坑位保我狗命吗？
- 2数据可视化 - Flask构建Web界面（一）_在flask基础上设计一个交互界面
- 3java new list map_java中Map和List初始化的两种方法
- 4【信息系统安全/计算机系统安全】期末复习（HITWH）_hit网络信息安全期末试题
- 5kubernetes中无法访问集群外数据库问题分析及解决_k8s应用连接不到数据库
- 6操作系统基础篇_段页式管理中,怎样访问内存,取得某一条数据或指令
- 7微信H5页面跳转小程序，wx-open-launch-weapp总结_h5使用wx-open-launch-weapp标签字体大小调整
- 8用批处理对MySQL进行数据操作
- 9es使用java来查询文档（基于es7.8）_java查询es文档
- 10从亚马逊跳槽谷歌，我后悔了
CF # 1477 简要题解_cf1477b
赞
踩
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
