21.3.18 考试小记

发布于 2018-03-21  2.61k 次阅读


T1

给出n个点,求这些点的任意子集的凸包的点数最大值,保证任意三点不共线。

考试时先写了2^n暴力,之后就开始搞DP。考虑我们转移时需要哪些信息才能判断合法性。我们需要知道当前凸壳的起点,当前点以及当前点上一个点。那么,我们的状态数是O(n^3)的,复杂度就决定于转移的复杂度。考试时直接写的裸转移O(n^4),但是积分可知这样的做法常数很小,本地造的纯随机数据n=250时依然小于400ms,交上去以后拿到了67分。之后,如果我们把叉积时候一堆重载去掉,又可以快很多。接着,因为我们同一个三元组的叉积判断了O(n)次,涉及到了很多无用的计算,所以我们把这些东西预处理出来,就可以用300ms左右的时间AC了这道题。(呵呵,期望50 实际100)

当然,我的这种做法还有一个复杂度上的比较显然的优化,对于每一个O(n^2)枚举的点对,都可以把中间O(n)个状态按照邻边的极角排序,代价是O(nlogn),然后,O(n)枚举每一个后继状态,以O(logn)的代价二分合法的极角范围,然后我们就有了总时间复杂度O(n^3logn)的优秀算法,但是考场上我只是想了想,担心调不出来所以没敢打。

回归正解的做法,我们可以先把O(n^2)条边拽出来按照极角排序,然后枚举每一个点作为凸包最上面的点的情况,设f[i][j]为当前情况下,上一个点为i,当前点为j的最大经过的点数,mx[i]为在i处结束的环的最大长度。我们可以通过将枚举的点的mx设为1,其余置为-inf作为初始条件,然后按照极角顺序枚举每一条边,例如我们枚举到边(j->i),那么就可以有f[j][i]=mx[j]+1,同时用f[j][i]更新mx[i]即可,复杂度是严格的O(n^3)。我也没有真正的去写这个算法,只是听考拉讲了讲之后又重新YY了一遍,感觉这个做法的常数可能没有什么可以优化的地方。

 

T2

题意略。

考场上想到了比较靠谱的线段树做法,但是最后对0取max的地方不太会搞,所以还是暴力55滚粗。

正解使用了平衡树+启发式合并,不过如果还是要用线段树做的话也没啥问题。

假设我们还是使用二分答案的做法,设二分的答案为t,每个点被干掉的时间是f[x],那么二分的答案要满足如下式子:

$$\sum_{v} max((t+dep[u])-(f[v]+dep[v]),0)  >= d[u] $$

平衡树里维护f[x]+dep[x],以及区间和,之后二分就好了。

如果想去掉二分的log,我们可以直接在平衡树上跑二分。每次如果当前点不能满足,就往右儿子跳,否则往左儿子跳,最后可以求出来选出的v的个数以及减去的东西的和,这样我们只要移项做除法并向上取整,就可以得到当前点的答案了。

 

T3

[UPD  22.3.18  7:43]补完了。

考试的时候根本没看出来这题让干啥,呵呵了。实际上,这道题就是给你一个长为n的序列A,求出满足P*P=A的满足[1,n-1]对称的字典序最小的P以及所有方案数,其中"*"为循环卷积。

明确了题意,就来考虑循环卷积的性质。首先,如果把P看作一个n次多项式,那么如果直接乘起来会得到一个2倍长度的序列,而如果进行的是循环卷积的话,相当于是把下标>=n的位置的系数加到前面的对应位置。求值的过程,相当于是我们带入了满足x^n=1的x,而满足这玩意的x就是单位复数根。补充一点单位复数根的定义:

$$e^{ui}=cos(u)+sin(u)i \; , \; \omega _{n}=e^{\frac{ 2 \pi }{n}i}$$

那么,我们可以暴力n^2进行DFT,求出原式的点值表达,因为点值的运算非常可搞,所以对求出来的点值进行复数开方,再插值回去就可以得到要求的多项式。但是,复数开方有两个结果,而我们不知道该选哪个,所以又该枚举了。2^n的枚举不能接受,由于奇怪的对称性(其实是不会解释),枚举只要枚举到一半就好了,另一半必须选对应的那个根。之后插出来对应的多项式,判是否可行就做完了。

 

 

本文隐藏内容 登陆 后才可以浏览


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974