Pku Campus 2018 Solution

Solution

Pku Campus 2018 Solution
PREFACE
2018年北京大学acm校赛非正式意识流题解。排版和公式显示暂时有点问题，等有空的时候再回来处理一下(facepalm

SOLUTION
A

列出线性规划式子，转为对偶型。
观察对偶型的线性规划式子，发现这是一个差分约束系统问题。
于是就可以用最短路求解。

0 .. n 共 n+1 个点
源点 vs = 0 终点 vt = n - 6
连边
(i+1 , i) 边权 = 0
(max(i - 7, 0), i) 边权 = W[i] （W为读入的数组）

求解最短路，因为该图的特殊性，这种做法的时间复杂度为O(N)
事实上，我们可以证明，每一天要么花费0小时，要么花费7小时，然后直接DP或贪心即可。

B

设郭神的初始资金为1元，f(i)表示恰好在第i天卖出时可获得资金的期望，g(i)表示恰好在第i天买入时所得份额数的期望。
$f(0)=1$
$g(i)=\sum_{j=0}^{i-1} 1/(n-j)f(j)1/Vi$
$f(i)=\sum{j=1}^{i-1} 1/(n-j)g(j)Vi*r{i-j}$
对所求式子进行变形，发现数列${g(i)V_i}$为数列${f(i)/(n-i)}$的前缀和，故g(i)可在常数时间求出。
对于f，可以使用分治。其中，计算区间[l,r]时，[l,m]对[m+1,r]的贡献可通过数列${g(i)/(n-i)}$与${r_i}$的卷积进行计算。
在分治过程中用FFT求卷积，需要进行常数优化以保证不会超时。
总时间复杂度$O(NlogN*logN)$

C

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

D

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

E

Rank
全都是直角。
奇数个点：
把n-1的答案最右边的角上剪一个角，最优解为n-2个直角。
多边形内角和为180(n-2)，90度角只能为90或270度，若有n个直角，假设x个90度，则
180(n-2)=90x+270(n-x)
n-2x=-4
与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位置上没有数。
由对称性知答案为(n+1)^n/(n+1)=(n+1)^(n-1)。
把原问题拆成若干条链，利用乘法原理计算总方案数即可。

G

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

H

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

I

设所填的最大正整数为k。
求一种填充方案等价于：求出n个集合S1,S2,…,Sn，使得Si都是{1,2,3,…,k}的子集，且任意i≠j，Sj都不是Si的子集。
必要性：如果存在一种符合规则的方案，将第i列的所有数字构成集合Si。对于第i行第j列的数字x，有x∈Sj，且第i列没有x，即x不属于Si，所以有Sj不是Si的子集。
充分性：方阵的第i行第j列填上集合(Sj \ Si)中的任意一个数字。对于第i行第j列的数字x，显然第i列没有数字x，第j行也没有数字x（反证，如果第j行第p列有数字x，则说明x∈(Sp \ Sj)，然而x∈Sj，产生矛盾）。
现要最小化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)。如果不做预处理，可能会超时。