MOCK NOIP+ 20221203 日志

还是张隽恺一如既往的恶趣味。

明显是嘲讽水平不及他的选手。

简略题解

A – 计数

每一次遇到排列问题,我都试着建出一张 nn 个点 nn 条边的图(xpxx\rightarrow p_x)后在上面思考。遗憾的是本题不能这样做。

记排列 pp 的逆为 p1p^{-1},则有 p=p1(pp1(p1)1=p)p=p^{-1}\lor (p\neq p^{-1}\land (p^{-1})^{-1}=p)

这是显然的:一个置换的逆元就是将其上下两行交换。故而我们可以计算出有多少个 nn 阶排列 p=p1p=p^{-1},则 n!n! 减去计数再除以二即为所求。

易得 p=p1p=p^{-1} 的充要条件是 ppx=xp_{p_x}=x,则可以视作每两个元素一对构成 px=y,py=xp_x=y,p_y=x 的形式,或者 px=xp_x=x。记 f(n)f(n) 表示 p=p1p=p^{-1}nn 阶排列数量,易得转移 f(n)=f(n1)+(n1)f(n2)f(n)=f(n-1)+(n-1)f(n-2),边界有 f(1)=1,f(2)=2f(1)=1,f(2)=2。时间复杂度 O(n)\newcommand\bigO{\operatorname{O}}\bigO(n)

注意:本题条件下不一定存在 22 的乘法逆元,故而记 f(n)f'(n) 表示 f(n)2\frac{f(n)}{2} 来转移。

B – 点分治

可以发现这棵树就是树状数组展开后的样子。有 x (x(0,2n))x\ (x\in(0, 2^n)) 的父亲为 xlowbit(x)x-\operatorname{lowbit}(x)。则两节点 x,yx,ylca=x and 2log2(xy)+1\operatorname{lca}=x\ \operatorname{and}\ 2^{\log_2(x\oplus y)+1},即 nn 位二进制表示的最长公共前缀后补零。则统计固定距离的节点个数,可以钦定给定节点 xx 二进制表示的某一以 11 结尾前缀作为最近公共祖先,后边选若干位置任填 11 即可(应当减去非法情况)。

时间复杂度 O(n+ki)\bigO(n+\sum{k_i})

C – 博弈

L=i=1nliL=\sum_{i=1}^{n}l_i。可知任何一种填完恰好 kk 个格子后游戏结束的方案,出现的概率均为 1Lk\frac{1}{L^{\underline{k}}}

我们枚举在哪一行结束了游戏,记其编号为 ii。假若 1i11\sim i-1 行填写了 k1k_1 个格子(每一行均未填满),记有 f(i1,k1)f(i-1,k_1) 种选择;i+1ni+1\sim n 行填写了 k2k_2 个格子,记有 g(i+1,k2)g(i+1,k_2) 种选择。则一共填写了 s=k1+k2+lis=k_1+k_2+l_i 格;又因为本题权值为拼接字符串表示的十进制数,且是“按照顺序依次填写”,则记 h(s,k)h'(s,k) 表示按序填写 ss 个字符串,择取其中 kk 个以任意顺序摆放拼接,且第 ss 个字符串一定选中的权值总和,答案即为 i=1nk1=0j=1i1lj1k2=0j=i+1nlj1f(i1,k1)g(i+1,k2)(k1+k2)!h(li+k1+k2,li)Lli+k1+k2\sum_{i=1}^{n}\sum_{k_1=0}^{\sum_{j=1}^{i-1}l_j-1}\sum_{k_2=0}^{\sum_{j=i+1}^{n}l_j-1}\frac{f(i-1,k_1)g(i+1,k_2)(k_1+k_2)!h'(l_i+k_1+k_2,l_i)}{L^{\underline{l_i+k_1+k_2}}}

f,gf,g 的计算都是简单的背包,复杂度 O(n3)\bigO(n^3);思考如何快速计算 hh’

场上我试图维护“所有可能的结果字符串”的各项信息,同时直接计算暴力插入一个字串 tit_i 的贡献(记 tit_i 表示的十进制数为 aia_i,则插入后的数可以拆分成 原数更高位×10ti+原数更低位+ai×10原数更低位+原数更低位\text{原数更高位}\times 10^{|t_i|+|\text{原数更低位}|}+a_i\times 10^{|\text{原数更低位}|}+\text{原数更低位},维护每个串在所有位置劈开得到的“高位”和“低位”权值和),但发现式子首项无法用线性方式维护插入 aia_i 之后的贡献。

何钒佑教给我们一更聪明的贡献方法:将每一个字串的贡献独立,写作 ai×10结果串更低位\sum a_i\times10^{|结果串更低位|}。具体地,对于一个由 jj 个串拼接而成的的结果串,我们将其复制成 jj 份;对于第 kk 份,我们预留kk 位作为一个“窗口”。若要将串 tit_i 填入,我们既可以填入窗口右侧,此时对权值积的贡献为 10ti10^{|t_i|};也可以占用窗口本身而计算 ai×低位权值积a_i\times \sum \text{低位权值积};也可以填入窗口左侧,贡献不变。容易验证,它的和不重不漏地计算了每一个串的每一位代价;指数相加结果相乘,它具有结合律。于是记 h(i,j,k,b)h(i,j,k,b) 表示考虑了 t1,,tit_{1},\cdots,t_i,择其中 jj 个拼接,且在窗口下方已经填入 kk 个串,窗口是否被占用(bb)的权值总和;转移时做些处理,就能计算 h(i,j)h'(i,j)

时间复杂度 O(n3)\bigO(n^3),常数大。

D – 最优化

最小费用增广流。

  • 2022年12月16日