【LGR-060】洛谷10月月赛 I
A - 打字练习
出题:memset0
送分模拟题,按题意模拟即可。
需要注意的是对退格键的判断,如果光标已经在行首,则直接忽略被读入的退格键。
B - 小猪佩奇爬树
出题:_QAQ
维护所有相同节点颜色的链并,若不构成一条链则显然答案为 $ 0 $ 。
若仅包含 $ 1 $ 个节点,则枚举所有子树大小进行统计。
否则即为链的 $ 2 $ 个端点所对子树大小的乘积。
C - 小猪佩奇玩游戏
出题:_QAQ & SPJ:memset0
容易发现可以将 $ {1,2,\dots,n} $ 进行分组,不同组别的答案是独立的。
举个栗子,对于 $ {1,2,3,4,5,6,7,8,9} $ ,可以将数字分为 $ {1},{3,9},{2,4,8},{5},{6},{7} $
容易发现这些组别之间互不干扰且互不影响,所以只需要计算每个组别独立的期望值并进行相加即可
那么最终答案即为
\[
\sum_{i=1}^{\infty} f_i \times g_i
\]
其中 $ f_i $ 表示大小为 $ i $ 的组别个数, $ g_i $ 表示大小为 $ i $ 的组别期望删除多少次,我们分别来计算
先来计算 $ f_i $ ,显然大小至少为 $ i $ 的组别个数为 $ \sqrt[i]{n} $
对于 $ 1 $ 个大小为 $ x $ 的组别,其为在大小为 $ y $ 的组别中出现 $ \lfloor \frac{x}{y} \rfloor $ ,所以可以考虑直接容斥计算,复杂度为 $ O(\log n^2) $
显然 $ i $ 最多只能取到 $ \log n $ ,所以 $ f_i $ 便很轻松地算出来了
考虑怎么算 $ g_i $ ,其实等价于给定数列 $ {1,2,\dots,i} $ ,每次删除 $ 1 $ 个数及其倍数
我们考虑一个等价类问题,枚举所有关于 $ i $ 的排列, $ x $ 会产生贡献当且仅当 $ x $ 的前面没有 $ x $ 的因子,那么根据概率的独立性, $ x $ 产生贡献的概率为 $ \frac{1}{\sigma(x)} $ ,因此有
\[
g_i=\sum_{x=1}^i \frac{1}{\sigma(x)}
\]
总复杂度为 $ O(T \log^2 n) $
D - 赛车游戏
出题:memset0
一道有意思的图论题。
对于一个点 $ u $ ,若不存在 $ 1 \rightarrow u $ 的路径或 $ u \rightarrow n $ 的路径,那么这个点对答案没有影响,可以直接忽略。
剩下的图一定是一个 DAG。因为如果有环,必定可以形成多条起点到终点的路径,使得无解。
考虑如何给一个 DAG 赋边权:由于每条 $ 1 \rightarrow n $ 的路径长度是相同的,那么每条 $ 1 \rightarrow i (i \in [1,n]) $ 的路径长度也是相同的。设为 $ dis_i $ ,跑差分约束即可。
时间复杂度即 SPFA 的时间复杂度 $ O(nm) $ ,实际上常数因子非常小。
此题的思路和代码都非常清新,只是 SPJ 和构造数据非常恶心,出题人表示体验极差。
E - 小猪佩奇学数学
出题:_QAQ
原式等价于
\[
\sum_{i=0}^n \binom n i \times p^{i} \times \frac{i-i\bmod k}{k} \bmod 998244353
\]
即
\[
\sum_{i=0}^n \binom n i \times p^{i} \times \frac{i}{k} -\sum_{i=0}^n \binom n i \times p^{i} \times \frac{i \bmod k}{k}\bmod 998244353
\]
考虑前半部分式子
\[
\sum_{i=0}^n \binom n i \times p^{i} \times \frac{i}{k}
\]
根据
\[
\frac{m}{n}\binom n m = \binom {n-1} {m-1}
\]
所以该式子等价于
\[
\frac{1}{kn} \sum_{i=1}^n \binom {n-1} {i-1} \times p^{i}
\]
即
\[
\frac{p}{kn} \sum_{i=0}^{n-1} \binom {n-1} {i} \times p^{i-1} \times 1^{n-i}
\]
根据二项式定理,即
\[
\frac{p}{kn}(p+1)^{n-1}
\]
对于后半部分式子容易发现 $ k \leq 2^{20} $ ,显然的思路是将数字按照对 $ k $ 的模数进行讨论
\[
\frac{1}{k}\sum_{i=0}^n \binom n i \times p^{i} \times (i \bmod k) \bmod 998244353
\]
即
\[
\frac{1}{k}\sum_{t=0}^{k-1} t\sum_{i=0}^n \binom n i \times p^{i} \times [i \bmod k = t] \bmod 998244353
\]
由单位根反演
\[
[i \bmod k = t]=\frac{1}{k}\sum_{c=0}^{k-1} w_k^{{(i-t)} \times c}
\]
代入原式,有
\[
\frac{1}{k}\sum_{t=0}^{k-1} t\sum_{i=0}^n \frac{1}{k}\sum_{c=0}^{k-1} w_k^{(i-t) \times c}\binom n i \times p^{i} \bmod 998244353
\]
即
\[
\frac{1}{k^2}\sum_{t=0}^{k-1} t\sum_{c=0}^{k-1}w_k^{-t \times c}\sum_{i=0}^n \binom n i w_k^{i \times c} \times p^{i} \bmod 998244353
\]
发现后半部分很像二项式定理,即
\[
\sum_{i=0}^n \binom n i w_k^{i \times c} \times p^{i}=\sum_{i=0}^n \binom n i w_k^{i \times c} \times p^{i} \times 1^{n-i}=(w_k^cp+1)^n
\]
那么原式等价于
\[
\frac{1}{k^2}\sum_{t=0}^{k-1} t\sum_{c=0}^{k-1}w_k^{-t \times c} (w_k^cp+1)^n \bmod 998244353
\]
发现后半部分为关于 $ w_k^{-t} $ 的 $ k-1 $ 次多项式,可以暴力多项式插值,但是这样太慢了
类似我们考虑将 $ w_k^{tc} $ 看作 $ w_k^{\binom {t+c}{2}-\binom t 2 - \binom c 2} $
那么原式等价于
\[
\frac{1}{k^2}\sum_{t=0}^{k-1} t^c\sum_{c=0}^{k-1}w_k^{-\binom {t+c}{2}+\binom t 2+\binom c 2} (w_k^cp+1)^n \bmod 998244353
\]
可以看作卷积的形式,那么只需要一次 NTT 就可以带走了,复杂度为 $ O(k \log k+k \log n) $
F - 美德的讲坛
出题:Isonan
算法1
我会爆搜!
复杂度 $ O(2^nq) $ ,期望得分 $ 20' $ 。
算法2
设 $ x $ 的最高位为 $ mx $ ,即 $ mx\in \mathbb{N},2^{mx}\le x < x^{mx+1} $ 。
我们把 $ a_i $ 按照 $ \lfloor{a_i\over 2^{mx}}\rfloor $ 分组。
容易发现组内两两异或和都是 $ < x $ 的。
对于 $ x=2^k,k\in \mathbb{N} $ 的部分分,我们发现分完组以后跨组的异或和全是 $ \ge x $ 的。
我们只要找到最大的组输出就行了。
复杂度 $ O(n+q) $ ,期望得分 $ 20' $ 。
算法3
对于一般情况,我们发现相邻组之间是有可能产生 $ < x $ 的异或和的。
那么我们的问题变成了:
现在有两组点,左边每个点有一个权值 $ a_i $ ,右边每个点有一个权值 $ b_i $ 。现在要在左右各选出一些点,使得两两异或和 $ < x $ 。
我们发现这个东东有点二分图的味道。那么是不是可以网络流呢?!
我们用如下方法建图:
源点向左边所有点连边,流量为 $ 1 $ 。
当 $ a_i\oplus b_j\ge x $ 时,左边点 $ i $ 向右边 $ j $ 连边,流量为 $ \infty $ 。
右边所有点向汇点连边,流量为 $ 1 $ 。
我们考虑这个图的最小割的意义。
如果 $ a_i\oplus b_j\ge x $ ,那么 $ i,j $ 之中必定要删掉一个。一个割表示的就是一个删除一些数字,使得剩下数字两两异或和均 $ < x $ 的方案。
那么我们要求的就是总点数-最小割。
复杂度 $ O(n^2q) $ ,期望得分 $ 30' $ 。
算法4
我们发现连边可以用 $ trie $ 树优化。
复杂度 $ O(n\sqrt{n}lognq) $ ,实现得好能得 $ 50' $ 。
(不是很会分析复杂度,大概是这样吧)
算法5
由于最大流=最小割,我们考虑从最大流的角度入手。
我们发现这个图的最大流也就是保留 $ a_i\oplus b_j\ge x $ 的边时,该二分图的最大匹配。
我们可以把这个问题搬到 $ trie $ 树上解决。
把所有数丢到 $ trie $ 树上。
设 $ solve(a,b,dep) $ 为 $ trie $ 树上以 $ a,b $ 为根的子树之间进行匹配,两棵子树的最大深度均为 $ dep $ 。
以下用 $ a0,a1,b0,b1 $ 表示 $ a/b $ 的左 $ / $ 右子树,用 $ |a| $ 表示 $ a $ 中点数。
当 $ x $ 在 $ dep $ 这一位上是 $ 1 $ 时,只有 $ a0 $ 和 $ b1 $ , $ a1 $ 和 $ b0 $ 可以匹配。
此时答案就是 $ solve(a0,b1,dep-1)+solve(a1,b0,dep-1) $ 。
当 $ x $ 在 $ dep $ 这一位上时 $ 0 $ 时, $ a0 $ 和 $ b1 $ , $ a1 $ 和 $ b0 $ 一定可以匹配。
当
\[
|a0| < |b1|\\
|a1| < |b0|
\]
或
\[
|a0|>|b1|\\
|a1|>|b0|
\]
时,答案显然是 $ \min(|a|,|b|) $ 。
否则,以
\[
|a0| < |b1|\\
|a1|>|b0|
\]
为例。
我们发现我们只需要额外考虑 $ a1 $ 和 $ b1 $ 的匹配。
答案即为 $ \min(solve(a1,b1,dep-1),b1-a0,a1-b0)+a0+b0 $ 。
这样基本就做完了。
我们发现单次修改的时候只会有 $ log $ 个节点被改动,每次只要把这些位置上的 $ solve $ 重新计算就好了。可以类似记搜解决。
复杂度 $ O((n+q)log^2V) $ ,期望得分 $ 100' $ 。
最新文章
- php N 维数组的读取、设置、删除
- jquery时间控件datepicker
- Spring事务:传播行为与隔离级别
- mysql 蠕虫复制
- nyoj 孪生素数
- 【C#】list 去重(转载)
- Druid数据库连接池
- hive内group by取第一条数据,Hive中row_number的使用
- 1.RN环境搭建,创建项目,使用夜神模拟调试
- springboot nginx 配置
- cs231n笔记 (一) 线性分类器
- JavaScript——this
- vue-cli 构建项目在IE中无法运行解决方式(build之后可运行)
- Vue的理解:Vue.js新手入门指南----转
- 学习致用九---centos7.2+vim vundle
- 012-Go ORM框架之Gorm测试
- vim golang 插件
- Vcenter 和ESXi License过期解决办法
- 《Python黑帽子:黑客与渗透测试编程之道》 网络基础
- SQLite菜鸟教程
热门文章
- 送书『构建Apache Kafka流数据应用』和『小灰的算法之旅』和『Java并发编程的艺术』
- Unity Shader 屏幕后效果——摄像机运动模糊(速度映射图实现)
- jQuery 源码分析(二) 入口模块
- mysql-5.7.23-winx64 解压版详细安装教程
- Hystrix工作流程解析
- 【maven】搭建maven私服--基于CentOS7.6+docker
- synchronized和volatile使用
- Mac OSX(Mac OS10.11) 安装 pwntools 失败的最新解决方案
- LeetCode——Employees Earning More Than Their Managers
- Linux-CentOS-Nginx安装