Pku Campus 2018 Solution

Preface

2018年pku acm校赛圆满落幕啦!其中DF是我出的题。

以下是校赛的非正式意识流题解。

Solution

A

列出线性规划式子,转为对偶型。
观察对偶型的线性规划式子,发现这是一个差分约束系统问题。
于是就可以用最短路求解。因为该图的特殊性,这种做法的时间复杂度为$O(N)$
事实上,我们可以证明,每一天要么花费$0$小时,要么花费$7$小时,然后直接DP或贪心即可。

B

设郭神的初始资金为$1$元,$f(i)$表示恰好在第$i$天卖出时可获得资金的期望,$g(i)$表示恰好在第$i$天买入时所得份额数的期望。

对所求式子进行变形,发现数列$\{g(i)V_i\}$为数列$\{\frac{f(i)}{n-i}\}$的前缀和,故$g(i)$可在常数时间求出。

对于$f$,可以使用分治。其中,计算区间$[l,r]$时,$[l,m]$对$[m+1,r]$的贡献可通过数列$\{\frac{g(i)}{n-i}\}$与${r_i}$的卷积进行计算。
在分治过程中用FFT求卷积,需要进行常数优化以保证不会超时。

总时间复杂度$O(Nlog^2N)$

C

记文档长度为$N$。直接KMP会超时,因为最多会进行$O(N)$次替换,每次替换最大长度$200$。
对$S$串构造KMP自动机,并预处理自动机每个节点插入$T$串任意一段后到达的节点。
插入$T$串过程中可能会再次匹配$S$,这种情况下,预处理出回退多少个节点。
而后不断处理文档,遇到要替换时,回退$len(S)$个节点后根据预处理结果处理插入$T$。
总时间复杂度$O(N+ST^2)$

D

预处理计算出字符串两两之间的编辑距离。所有字符串为节点,字符
串的编辑距离为节点之间的边权,构成一个无向带权完全图。将所有边从
小到大排序,用Kruskal算法求最小生成树。每增加一条边时,都会合并两
个类,这时,只需检查合并后的类是否满足条件:这一类的字符串两两之
间的编辑距离严格小于这一类的字符串与其他类中的字符串之间的编辑距
离。将类$G$划分成若干(>=1)个子类,记满足条件的方案总数为$F(G)$。若
不满足条件,由乘法原理,合并后的类方案总数为

若满足条件,则新增了1种方案:也就是不对其作任何划分。合并后的类方
案总数为

E

Rank
全都是直角。
奇数个点:
把$n-1$的答案最右边的角上剪一个角,最优解为$n-2$个直角。
多边形内角和为$180(n-2)$,$90$度角只能为$90$或$270$度,若有$n$个直角,假设$x$个$90$度,则

与$n$为奇数矛盾;
若有$n-1$个直角,则剩余的那个角一定是$90$的倍数,且既不是$90$也不是$270$,那只能是$180$或$360$,都与题意矛盾。

F

考虑$f[i]$恒等于$i+1$的情况,可以证明方案总是为$(n+1)^{n-1}$。
证明:拓展一个位置$n+1$,令$f[n+1]=1$。
这样构成了$n+1$的环,问题等价于放$n$个取值为$[1,n+1]$的数,并且$n+1$位置上没有数。
由对称性知答案为$\frac{(n+1)^n}{n+1}=(n+1)^{n-1}$。
把原问题拆成若干条链,利用乘法原理计算总方案数即可。

G

先只考虑 $S[L, R]$,实质等价于求出由$X_i$($i=L…R$)组成的向量组 张成的子空间$W$的维度 $dimW$, 答案即为 $p^{dimW}$ 。
求解子空间的维度可以转换为维护子空间的基的问题,于是,可以通过类似高斯消元的方法,动态构造一个向量组的基:
依次向当前基中添加向量,记 $F[i]$ 为最大的非零分量下标为第 $i$ 个分量的向量。

对于待添加向量 $X_k$ ,从第一个分量开始枚举,如果 $X_k$ 的第 $i$ 个分量非零,则通过减去$F [i]$ 的若干倍消去这一分量,如果 $F [i] $为空,则证明当前待添加分量与现有基线性无关,可以并入基中。
重复此过程,可获得向量组的一组基。求基时间复杂度 $O(d^3)$。
接下来分析如何快速得到向量序列区间上的一组基:当没有修改操作时,可以采用分块算法,每次合并至多 $O(sqrt{N})$ 组基:合并方式为将基向量数量较少的一组基暴力添加至另一组基里即可,时间复杂度$O(d^3 )$。
故分块算法的初始化复杂度为 $O(d^2 N)$,询问时间复杂度为 $O(d^3\sqrt{N})$。
考虑用线段树维护子区间上的基,逐层暴力合并基即可。由于长度为 $N$ 的线段树
至多 $2N$ 个子区间,所以建树复杂度为 $O(d^2 N)$,询问时间复杂度为 $O(d^3logN)$。
题目中询问的是Synchronicity 值, 进行一些推导: 假设 $A$,$B$ 是两个子空间,
$|A \oplus B| = p^{dimA} + p^{dimB} - 2 p^{dim(A \cap B)}$ 。由维度公式可知 $dim(A \cap B) = dimA + dimB - dim(A + B)$。
而两个子空间之和的维度等价于求解两组基的并,依旧可以采用直接合并基解决。
修改操作只需要对线段树上某条路径的所有节点进行基合并操作即可,时间复杂度
$O(d^3 logN)$。线段树实现不好可能会超时。

H

求最大质因子$X$,输出$2147483647/X$即可。

I

设所填的最大正整数为$k$。
求一种填充方案等价于:求出$n$个集合$S_1,S_2,…,S_n$,使得$S_i$都是${1,2,3,…,k}$的子集,且任意$i≠j$,$S_j$都不是$S_i$的子集。
必要性:如果存在一种符合规则的方案,将第i列的所有数字构成集合$S_i$。对于第i行第j列的数字$x$,有$x∈S_j$,且第$i$列没有$x$,即$x$不属于$S_i$,所以有$S_j$不是$S_i$的子集。
充分性:方阵的第$i$行第$j$列填上集合$(S_j / S_i)$中的任意一个数字。
对于第$i$行第$j$列的数字$x$,显然第$i$列没有数字$x$,第$j$行也没有数字$x$(反证,如果第$j$行第$p$列有数字$x$,则说明$x∈(S_p / S_j)$,然而$x∈S_j$,产生矛盾)。
现要最小化$k$,即取最小的k使得$C(k, [k / 2])>=n$。

J

设$N$,$d$的答案为$f(N,d)$,注意到$f$关于$N$是积性函数,问题化作求解$f(p^n,d)$。
注意$p=2$与$p>2$时,需要分别讨论。
$p>2$时,$f(p^n,d)$的答案与$p%4$、$d$有关。
$p=2$时,$f(p^n,d)$的答案只与$d$有关。

K

本题给定了有限种操作,我们考虑设计一些状态并确定状态之间的转移关系,然后可以通过两步之间的转移矩阵应用快速幂矩阵乘法得到$T$次的转移矩阵。
下面我们来研究在上述状态下的转移情况,我们用转移矩阵$A[i][j]$表示从状态i到状态j的可能操作数:
对于状态$0$,由于我们要求的是第一次达到目标的次数,所以对于在规定次数之前时刻,如果已经达到目标,则这样的结果应该被排除,所以$A[0][j]=0$。
对于操作 1 、 2 ,可以将任意一条边变为与之前不同的状态(开或关),那么处于状态i的任意一种显示屏形式,可通过操作 1 、 2 改变其与目标不同的i条边中任意一条变为状态$i-1$,共有$i$种选择;同样的可以通过改变与目标相同的$N-i$条边(设 $N$ 为总边数)中的任意一条变为状态$i+1$(对于边界情况如i=N时自然不会变到$i=N+1$) ,共有$N-i$种选择。
对于操作 3 、 4 、 5 ,首先,我们能发现这三个操作都改变了两条边,而且包含了任意改变两条边的操作。类似之前的讨论,我们发现,当我们改变的两条边都是与目标相同的时,从状态i变为$i-2$,此时改变的边共有$(N-i)(N-i-1)/2$种取法;当改变的两条边都是与目标不同时,状态从$i$变为$i+2$,共有$i(i-1)/2$种取法;当改变的两条边一条与目标相同,一条与目标不同时,状态不变,共有$i(N-i)$种取法。
综上,我们能得出转移矩阵满足:
$A[0][j]=0$,$A[i][i-1]=i$,$A[i][i+1]=N-k$,
$A[i][i-2]=i(i-1)/2$,$A[i][i+2]=(N-i)(N-i-1)/2$,$A[i][i]=i(N-i)$,其余均为 $0$ 。
得到转移矩阵以后,我们的目标就是计算$e11 * A^T$,即表示从初始状态经过$T$时刻后第一次变为目标的方法数,其中$e11$为只有状态$11$为$1$其余为$0$的行向量。这可以通过预处理矩阵快速幂算法得到。
由于有多组询问,需要预处理$A^{2^k}$,然后在处理询问时,根据$T$的二进制将$e11$乘以$A^{2^k}$。如果不做预处理,可能会超时。