UOJ Logo LazyJazz的博客

博客

NOIP Simulation Round #1 (万圣节欢乐赛) 题解

2017-11-01 07:47:38 By LazyJazz

万圣节的入场券

from LazyJazz,题解 by LazyJazz

不知道Communist Party是什么的同学可以自己去查一查

作为NOIP级别的比赛的第一题肯定很水啦,不过我还是精心构造了部分分的:

算法一

由于 $x$ 比较小,你可以暴力枚举 $x$ 的值,然后再一个一个判断是否能正好甄别出一个“另类”的数,然后输出就好了

总时间复杂度取决于你判断素数的方法的复杂度,大概在$O(n^2 \cdot x)-O(n \cdot x)$之间

期望得分:30分。

算法二

所以我们可以枚举每个数,每次求出除该数以外的数的GCD作为候选 $x$ 值,找出一个出现次数最多的候选 $x$,可以证明这就是 $x$ 的值。

然后扫一遍判断一下就好了,实现过程需要素数筛筛出 $1500000$ 以内的所有素数,这个范围 $O(n)$ 和 $O(n log log n)$ 都可以

时间复杂度:$O(n^2log n)$

期望得分:60分

算法三

仔细思考发现,我们只要求常数组GCD就可以找出 $x$ 了

找出 $x$ 后同算法二

时间复杂度:$O(nlogn)$

期望得分:100分

万圣节的积木

from LazyJazz,题解 by LazyJazz

这本来是一道NOIP题的,后来不再是了……

不过我送给你们95分了呢!

算法一

我们先来看子任务1,$n \leq 20$ 的数据范围,暴力枚举每个关节是否需要分割,然后判断稳定性就好了,需要卡卡常数

时间复杂度:$O(2^n \cdot n^2)$

期望得分:30分

算法二

选手:我会算出所有子段是否稳定然后DP!

善良的LazyJazz:恭喜你,你有60分了!

时间复杂度:$O(n^3)$

期望得分:60分

算法三

选手:我会算出所有子段是否稳定然后DP!

善良的LazyJazz:恭喜你,你有60分了!

选手:我可以从上到下递推着算出所有子段是否稳定!

友善的LazyJazz:恭喜你,你有95分了!

时间复杂度:$O(n^2)$

期望得分:95分

算法三点一

选手:我会算出所有子段是否稳定然后DP!

善良的LazyJazz:恭喜你,你有60分了!

选手:我可以从上到下递推着算出所有子段是否稳定!

友善的LazyJazz:恭喜你,你有95分了!

选手:我可以算出,对于所有的 $i∈[1,n]$,取靠近底端的前 $i$ 层是否稳定!然后找出最长的不稳定跨度的长度!

邪恶的LazyJazz:万圣节快乐,95分!

我们来考虑这样一件事:如果靠近底端的前 $i$ 层稳定,且靠近底端的前 $j(j > i)$ 层也稳定,那么从第 $i+1$ 到第 $j$ 层这个子结构一定稳定,否则前提不成立。

所以不需要DP了,找出最大的 $L$,表示存在$i(i+L \leq n)$,保证靠近底端的前 $i$ 层稳定,且靠近底端的前 $i+L$ 层也稳定即可

本题最开始的时候到这里就结束了,后来LazyJazz辛苦工作一下午,写出了一份10kB的标程后,世界就变了样……如果不想看满分做法,请跳过算法四

时间复杂度:$O(n^2)$

期望得分:95分

算法四

根据算法三点一,我们发现只要我们求出所有的前若干层的稳定性即可得解!

所以我们考虑先算出从上往下(注意:这次是从顶部往下考虑)前 $i$ 层的重心在第 $i+1$ 层上的落点,得到一个允许的重心落点活动范围(即去掉顶端若干层后,重心位置变化值的范围)

然后我们发现,如果从上到下数第 $i$ 块的覆盖范围的中点是 $M_i=\frac{L_i+R_i}{2}$,质量为 $W_i=R_i-L_i$,偏移量(我们称积木中心位置乘质量为偏移)为 $D_i=M_i \cdot W_i$,分别求出各个位置的质量前缀和和偏移量前缀和

\begin{equation} preW_i=\sum^{i}_{j=1}W_j, preD_i=\sum^{i}_{j=1}D_j \end{equation}

那么从上往下前 $i$ 块积木的重心应该是 $F_i=\frac{preD_i}{preW_i}$,对于所有 $F_i$ 存在关系 $L_{i+1} \leq F_i \leq R_{i+1}$(重心落在下一层范围内)

于是我们得到重心活动范围限制 $limL_i$ 和 $limR_i$:$limL_i=L_{i+1}-F_i$,$limR_i=R_{i+1}-F_i$

对于任一关节(我们称两层积木接触位置为关节),其上方积木偏移量和为 $devi$ (deviation),质量和为 $mass$,重心活动范围限制为 $[limL,limR]$,上方积木 偏移量和缩减量 $y$ 与 质量和缩减量 $x$,存在限制:

\begin{equation} limL \leq \frac{devi-y}{mass-x}-\frac{devi}{mass} \leq limR \end{equation}

若带入 $x, y$ 后不满足上述不等式约束条件,则在该关节处存在不稳定状态,进而整体结构不稳定

进一步推式子,得到

\begin{equation} limL \leq \frac{mass(devi-y)-devi(mass-x)}{mass(mass-x)} \leq limR \end{equation}

\begin{equation} limL \cdot mass(mass-x) \leq mass(devi-y)-devi(mass-x) \leq limR \cdot mass(mass-x) \end{equation}

\begin{equation} limL \cdot mass(mass-x) \leq devi \cdot x - mass \cdot y \leq limR \cdot mass(mass-x) \end{equation}

\begin{equation} limL \cdot mass^2 - limL \cdot mass \cdot x \leq devi \cdot x - mass \cdot y \leq limR \cdot mass^2 - limR \cdot mass \cdot x \end{equation}

进而,当 $limL \cdot mass^2 - limL \cdot mass \cdot x > devi \cdot x - mass \cdot y$ 时,或 $limR \cdot mass^2 - limR \cdot mass \cdot x < devi \cdot x - mass \cdot y$ 时,结构不稳定

于是我们在每个关节处得到两个判断式

\begin{equation} limL \cdot mass^2 > (devi+limL \cdot mass) x - mass \cdot y \end{equation}

\begin{equation} limR \cdot mass^2 < (devi+limR \cdot mass) x - mass \cdot y \end{equation}

其中 $mass, devi, limL, limR$ 都是常数,可以发现这两个式子化简为 $C > Ax + By$ 或 $C < Ax + By$ 的形式后,其本质为要求对于一组 $(x,y)$,要求点 $(x,y)$ 处于直线 $C = Ax + By$ 的一侧。可以用平衡树动态维护半平面交,并判断点是否在半平面交区域内求解。

实现动态维护半平面交和判断点是否满足条件后,把每个关节的数据带入求解即可。

动态维护半平面交具体实现方法

修改:用平衡树按横坐标排序维护上下凸壳上的顶点,每次插入一条直线后,三分法找出原凸壳出现在新直线限制范围外的顶点,删除原有超限顶点并插入新直线与原凸壳的交点。

查询:对于一组查询 $(x,y)$ 找到以横坐标为标准,上下凸壳上 $x$ 左边的顶点和 $x$ 右边的顶点连成的直线,判断 $(x,y)$ 相对于该直线所处位置即可(若出现在下凸壳下方或上凸壳上方即为不合法,否则合法)。

时间复杂度:$O(n log^2 n)$

期望得分:100分

万圣节的快递

from LazyJazz,题解 by LazyJazz

在题解正文之前,先向SSF信息学(前科技社团)的前辈们致敬!

算法一

对于前10%的测试点,即两个栈内货物顺序固定,需要求出对于一个栈内物品顺序的操作次数

由于 $n \leq 1000$,你只需要暴力模拟访问过程并记录操作次数即可。

时间复杂度:$O(n^2)$

期望得分:10分

算法二

对于前30%的测试点 $na,nb \leq 1$,即两个栈内货物顺序固定,需要快速求出对于一个栈内物品顺序的操作次数

相对于算法一,我们需要找出一个更快的求操作次数的方法

我们考虑把两个栈“顶对顶”对接起来,形成一个数列,有一个指针依次访问了所有的数,那么操作次数就是这个指针的移动距离总和

记录一下每个数在数列中的位置即可得解

时间复杂度:$O(n)$

期望得分:30分

算法三

$na+nb=n$ 表示所有快件可在其所在栈范围内自由排列

将两列火车分开看,每列火车中的一段连续数字合成一整块,按块大小排序即可(贪心思想)

时间复杂度:$O(na \texttt{ } log \texttt{ } na + nb \texttt{ } log \texttt{ } nb)$

期望得分:40分(结合算法二)

算法四

我们先思考一个模型:在一个数字序列中,我们把所有数值相邻的数字对连线,操作数等于总连线长度,通过统计连线的角度考虑,可以继续解决此问题

$na, nb$ 小,枚举所有车厢选择顺序,合算操作次数时处理下车厢与车厢间连线关系,车厢内连线(常数),车厢到对侧列车连线,三种情况即可。

时间复杂度:$O(na! \cdot na^2+nb! \cdot nb^2)$

期望得分:60-80分(结合算法二,算法四,运气好可能能过 $na,nb \leq 10, n \leq 20$ 的点)

算法五

$na, nb, n$ 都比较小,枚举所有车厢选择顺序,用算法二加稍稍处理出跨列车的情况,算出每种排列的操作次数即可

时间复杂度:$O((na! + nb!) \cdot n)$

期望得分:80分(结合之前的算法)

算法六

预处理出同一列车内车厢间连线数,车厢内连线距离,车厢到对侧列车连线数后,状压DP即可

存在预处理 $O(n)$,DP转移 $O(2^{na} \cdot na^2 + 2^{nb} \cdot nb^2)$ 的一组做法,期望得分90分;

和预处理 $O(n+2^{na}\cdot na+2^{nb} \cdot nb)$,DP转移 $O(2^{na}\cdot na+2^{nb} \cdot nb)$ 的一组做法,期望得分100分。

评论

ssdfzhyf
1,2,3,4,5,6-六氯环己烷
yzmor
@ LazyJazz 有测试数据吗???

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。