常规操作:先挖坑,再填。

填坑进度条:6/12

Axes of Symmetry

看上去是一道计算几何题,但有一个十分妙的解法。

我们給边和角一个特征值,使得不同的边和角的特征值不同,这样,我们一次把相邻的特征值连接起来(即“角-边-角-…”)得到一个循环数列。

我们可以发现,如果一个位置是对称轴,那么从这个位置断开这个循环数列一定会得到一个会问数列。

这样,我们的问题就转换成了求循环数列中从哪几个位置断开可以得到回文数列。

我们把数列复制一份直接接在后面,如果一个位置\(x\)是回文数列的中间,那么\(x\)为中间的回文数列长度一定满足\(\ge 2*n-1\),至于为什么是\(\ge 2*n-1\)而不是\(\ge 2*n\),从样例就可以看出来。

这样直接计算,在一种第一个位置就对称的图形中会重复计算一条(也可以从样例看出来),但我们直接计算是重复算两遍的,需要 div  \(2\) ,那么多算了一条无所谓,不用管他。

而以\(x\)为中间的回文数列长度,可以用Manacher解决。

边的特征值直接用长度,不需要开方浪费时间,直接用long long存着即可;角的特征值考虑到可能有大于平角的,所以用叉积比较合适。

 


Gas Pipelines


Megalopolis

如果一条路\(x->y(x<y)\)变成公路,那么只会对以\(y\)为根的子树造成影响。

考虑直接用树桩数组维护dfs序。对树重新编号,那么一棵树的dfs序编号一定是连续的一段。

我们每次都对一颗子树的\(l\)和\(r\)分别标记\(+1\)、\(-1\),这样对于一个结点的路径长度,就是他的前缀和。

直接用树状数组来维护标记的修改。

 


Offices

显然求的是补图的联通块个数。

时间卡的比较紧,用链表优化当前未被拓展的结点。

 


Quaternary Balance


Railway


Ridges and Valleys

非常基础的搜索题。

每次暴力搜索一块联通的、高度相同的平地,判断是山峰还是山谷还是什么都不是即可。

时间复杂度\(O(n^2)\)。

官网是时间卡的比较紧,不可能开两个\(1000\times 1000\)的数组,那就用小trick处理一下。

 


Tetris Attack


The Flood


Tourist Attractions

可以发现\(k\)很小。考虑状压dp。

用\(f[i][j]\)表示状态为\(i\),当前最后一个城市为\(j\)的最短路径。

有限制先后的,我们用\(limis[i]\)表示,走到\(i\)之前需要达成的状态。

这样以后,我们用类似于SPFA的方法,转移dp即可。

 


Weights


Queries

莫比乌斯函数性质的基本应用。

莫比乌斯函数有一个性质:

把这个性质拿过来:

$$\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d]$$

可以做变换:

$$\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d]\\
=\sum_{i=1}^{\frac{a}{d}}\sum_{j=1}^{\frac{b}{d}}[gcd(i,j)=1]\\
=\sum_{i=1}^{\frac{a}{d}}\sum_{j=1}^{\frac{b}{d}}\sum_{k|gcd(i,j)}\mu(k)\\
=\sum_{k=1}^{n}\left \lfloor \frac {\frac{a}{d}}{k} \right \rfloor\left \lfloor \frac {\frac{b}{d}}{k} \right \rfloor\mu(k)$$

这样直接计算的复杂度是\(O(T*min(\frac{a}{d},\frac{b}{d}))\),显然还是要TLE的。

考虑\(\left \lfloor \frac {\frac{a}{d}}{k} \right \rfloor\)的取值都不超过\(\sqrt{a/k}\),我们可以枚举\(\left \lfloor \frac {\frac{a}{d}}{k} \right \rfloor\)和\(\left \lfloor \frac {\frac{b}{d}}{k} \right \rfloor\)的结果,这样的话,就可以把时间复杂度降到\(O(T*(\sqrt{\frac{a}{d}}+\sqrt{\frac{b}{d}}))\)。

 



发表评论

电子邮件地址不会被公开。 必填项已用*标注