丽泽普及2022交流赛day14
A
题面
一个 \(1\dots n\) 的排列 \(p\) 和一个 \(1\dots n-1\) 的排列 \(q\) 满足
对排列 \(I=1,2,\dots,n\) 进行 \(n-1\) 次交换:
- 交换 \(I[q[i]]\) 与 \(I[q[i]+1]\) .
做完操作后满足 \(I=p\) .
给定 \(p\),计数 \(q\),答案对 \(10^9+7\) 取模 .
题解
一个 \((q,q+1)\) 交换过后显然左右就不可能再交流了 .
于是每个区间的答案可以拆成俩区间,考虑区间 dp .
丢一下柿子,需要组合数学知识:
\]
B
题面
在 \(n\times n\) 每个方格上随机地填入 \(1\) 到 \(m\) 之间的正整数(每个方格填的数互不相同),然后随机地选出 \(k\) 个数字,把它们出现在棋盘上的方格涂黑 .
设有 \(R\) 行被整行涂黑,\(C\) 列被整列涂黑,则得到 \(2^{R+C}\) 分 .
求期望得分 .
题解
枚举 \(R,C\) 算概率 .
显然涂黑格子数为 \(x = Rn+Cn-RC\) .
算一个局面的超集概率是容易的 .
考虑 \(2^{R+C}\) 的组合意义,于是把所有概率加起来就凑出这个贡献了 .
大力算,概率是古典概型,俩组合数相除即可 .
upd. 社论
C
题面
题解
中序遍历,最长不下降子序列 .
D
题面
一个序列 \(a\) .
一个区间 \([l,r]\) 是好的,当且仅当存在 \(k\in[l,r]\),使得对于任意 \(i\in[l,r]\),有 \(a_k \mid a_i\) .
求序列最长好子串 .
题解
这个条件等价于区间 \(\gcd\) 在区间中存在 .
俩 \(\log\) 解法比较好想,枚举左端点二分右端点即可 . 但这玩意涉及一个世界难题——判断数是否在区间中 .
于是考虑枚举 \(a_k\),左右分别二分出最长子串,就是 \(1\) 个 \(\log\) 了 .
upd. 题解好像错了,st 表区间 \(\gcd\) 询问复杂度是带 \(\log\) 的,所以实际复杂度可能是小常数俩 \(\log\) .
Keven_He 你个暴力优化艹过去的不要评论了!!/fn
upd. 反转了,用三区间合并(Sqrt Tree)似乎可以靠谱一 \(\log\) .
upd. 可以记区间 \(\min\) 和区间 \(\gcd\) 然后随便二分做 .
st 表区间 \(\gcd\) 预处理复杂度是一个 \(\log\) 的证明可以看 OI-wiki .
最新文章
- column css3 列宽
- POJ2104 —— K-th number
- 004医疗项目-逆向工程-pojo类的创建和对应xml的生成
- javascript的队列,优先队列,循环队列
- 【MySql】赶集网mysql开发36条军规
- Hibernte继承映射
- Spring MVC注解冲突
- Lua table使用
- Android中自定义View的MeasureSpec使用
- 【字典树】【贪心】Codeforces 706D Vasiliy's Multiset
- Summation of primes
- css样式清零及常用类
- python书籍推荐:Head First Python(中文版)
- bootstrap模态框手动关闭遮盖层不消失
- React使用Styled-Componets来添加样式
- openssl内核升级
- Android-Failed to open zip file
- 20155218 《网络对抗技术》 MAL_恶意代码分析
- jQuery 时间控件推荐
- 记第一场atcoder和codeforces 2018-2019 ICPC, NEERC, Northern Eurasia Finals Online Mirror