第二场NOIP模拟赛将于 11 月 6 日举行，欢迎校内外同学参加

比赛一共包含三道题目，将采用与上一场相同的形式，时间段。不出意外的话，记Rating。

比赛时间

北京时间2017年11月06日 15:30~20:30

出题阵容

三道题全部由 xjr 同学提供

验题人：wzj52501

比赛难度

比赛难度大概和NOIP提高组接近，据验题人称，难度略低于上一场

UPD：比赛已经结束！

恭喜获得前 5 名的选手！

1. Mer
2. wujiuwu
3. oscar
4. wyx
5. AKEE

万圣节的入场券

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分。

大家好，我是LazyJazz！

作为一个OJ，不能不办比赛。是不是？对不对？

所以就由我来带给大家一场娱乐赛。

这个比赛以LazyJazz的万圣Party为主题！

希望大家玩的开心！！！

比赛时间

北京时间2017年11月01日 15:30~20:30

出题阵容

LazyJazz，LazyJazz，LazyJazz

都是我，TAT

验题人：wzj52501

比赛难度

比赛难度大概和NOIP提高组接近

UPD：比赛已经结束！

恭喜获得前 5 名的选手！

1. ssdfzhyf
2. xjr
3. wyx
4. FYH_SSGSS
5. wxg123