26.3.18 考试小记


T1

考试的时候尝试感性的用枚举倍数来搞,无果。实际上,这道题的很大一部分是可以感性证明的。一维情况下的约数个数之和,其实等价于每个数倍数个数之和。扩展到二维,我们枚举的是点对的乘积,如果还是直接乘起来而不加约束条件的话一定会重复计算。例如,8会在两个数分别是1的倍数和8的倍数时枚举到,也会被分别是2和4的倍数枚举,因此,我们需要限制两数必须保证互质。扩展到三维,同样是这样,所以答案有了如下转换:

$$\sum_{i=1}^{A} \sum_{j=1}^{B} \sum_{k=1}^{C} d(ijk) = \sum_{(i,j)=(i,k)=(j,k)=1} \lfloor \frac{A}{i} \rfloor \lfloor \frac{B}{j} \rfloor \lfloor \frac{C}{k} \rfloor $$

接下来,考虑处理这三个互质关系,我们同样是采用感性证明的方法,而不是像平常一样直接上反演的套路。首先i可以直接枚举,我们可以先处理j、k的互质关系,也就是枚举j、k的公因数是t的倍数,里面乘上mu来容斥,这样就能保证j、k互质了,现在一共是O(n^2)的枚举量。对于内层i、j以及i、k的互质关系,可以直接枚举,需要调和级数的复杂度,那么总复杂度就是O(n^2ln(n)),写一写式子就是这样的:

$$\sum_{i=1}^{A} \lfloor \frac{A}{i} \rfloor \sum_{t=1} ^{min(B,C)} \mu(t) \; \sum_{j=1,(i,j)=1} ^{\lfloor \frac{B}{t} \rfloor } \lfloor \frac{B}{jt} \rfloor \; \sum_{k=1,(i,k)=1} ^{\lfloor \frac{C}{t} \rfloor } \lfloor \frac{C}{kt} \rfloor $$

 

 

T2

考场上用到了和正解相似的性质,但是我只用这玩意去状压,而没有从组合数学的角度来搞一搞。。。

首先,不考虑不合法的方案,答案就是长度为i的不下降序列的方案数乘上(n-i)!。考虑不合法的方案,就是在长度为i+1的时候已经变成了不下降的序列,那么我们只要用上面的玩意减掉长度为i+1的方案数乘上(n-i-1)!,再乘上(i+1)表示从这i+1个数里面随便选一个都会不合法。

关于方案数,可以设f[i][j]表示前i个元素强制以i结尾且长度为j的方案数,有O(n^2)个状态,转移的代价可以用树状数组优化到O(logn),算法总时间复杂度O(n^2logn)。

 

T3

一眼二分+半平面交,考场AC。首先考虑如何将边数优化到O(n)。通过观察可以发现,每次删掉连续的点一定比不连续的限制性更强,画一下马上就能看出来了,那么我们可以直接隔x个连一次边,然后跑半平面交。注意,一定要加上外面的四个框框,否则根本就不对(详见这篇文章)。

 

声明:Narcissus' Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 26.3.18 考试小记


Narcissus | HZOIer | zhuohaoyu1228@gmail.com