2024年4月8日发(作者：)

NOIP 2012简要题解

王赢绪

东北师大附中

高二二班

499167119@

2012年11月19日

分数分布：

Day 1：

Problem

Vigenère密码（vigenere）

国王游戏（game）

开车旅行（drive）

Contest

100

100

70

Current

100

100

100

Day 2：

Problem

同余方程（mod）

借教室（classroom）

疫情控制（blockade）

Contest

100

90

50

Current

100

100

100

题解：

Day 1：

Problem 1 Vigenère密码（vigenere）

这是一道模拟题，我的做法的先把密钥都换成大写或者小写。然后对输入的加密文章进

行处理，如果当前对应的密钥位置超过了密钥的总长度，则把当前位置转回1即可，并且注

意加密文章的大小写问题。时间复杂度为O(n+m)，其中n和m分别为两个字符串的长度。

Problem 2国王游戏（game）

这道题的主要考察点是高精度乘法除法以及贪心算法的应用。这是USACO 2007年某

次月赛的改编题。我们不难观察出必存在一种最优的安排方案，是按照每个人左右手两个数

的乘积由小到大排序后计算得来，对于乘积相同的我们可以不考虑他们的顺序。

Problem 3开车旅行（drive）

这道题我只能想到用平衡树然后倍增维护每个点往前走2的次幂到达哪，以及需要的路

程为多少。具体实现是这样的，我们首先按照站点倒序的顺序进行处理，那么显然每个点离

它最近的那个点一定是它高度值的前驱或者后继（如果存在的话），接下来我们考虑每个点

的次近点，比如最近点为前驱，那么显然次近点为前驱的前驱或者后继，而如果最近点为后

继，则次近点为后继的后继或者前驱。所以我们可以花O(nlogn)的时间处理完成每个点的最

近点及次近点。

接下来由于我们已经有了每个点可以到达的最近点及次近点，那么我们可以处理出每个

点走2的次幂以后，A走过的路程为多少，B走过的路程为多少，以及此时所在的位置。这

一步处理的时间复杂度也为O(nlogn)。

对于给定询问的X

0

，我们可以利用倍增的方式进行处理，将2的次幂从16降到0，对

于当前的2

i

，如果往前走2

i

的地点存在并且加上这段距离也不超过X

0

，我们则前进，否则

不进行处理。算完2的0次幂以后我们再试探一下A能否再往前走一站，如果能的话则走。

每次询问的时间复杂度为O(logn)，总时间复杂度为O((n+m)logn)，其中n为站点数，m为

询问总数。

Day 2：

Problem 1同余方程（mod）

题目所求为关于x的同余方程：ax≡1

(

modb

)

的最小整数解。我们不妨设

ax=by+1

，

则有

ax−by=1

，接下来用扩展欧几里得算法解决。

Problem 2借教室（classroom）

这道题显然可以用线段树对每个操作进行处理，但在实际测试中这仅能得到90分。对

于更快的算法，我们可以通过二分解决。显然这道题的答案存在单调性，我们对原序列进行

差分处理。设原序列中的数为

a

i

，差分序列中

s

i

=a

i

−a

i−1

。则有

a

i

=

∑

s

j

。对于将

[

L,R

]

中

j=1

i

的所有数都减小

d

，等价于

s

L

减去

d

，

s

R+1

加上

d

。将当前的

k

个操作处理完成后，我们发

现如果存在一个

a

i

<0

则说明当前的操作是不合法的。这样做的时间复杂度为O(nlogn)。而

我们主要把时间浪费在了对s数组的操作以及还原上，我们可以发现对于当前的

k

如果合法，

那么我们可以不必进行还原，在下次操作时直接从

k+1

进行操作即可。这样做虽然时间复

杂度仍为O(nlogn)，但最大测试数据0.3s即可出解。

Problem 3疫情控制（blockade）

这道题主要算法就是贪心以及倍增和二分答案。首先我们对树进行处理，记录每个点2

的次幂的father是谁，以及每个点到达根节点的距离是多少。我们发现对于当前的点，在给

定的时间内只能往上走，因为往下走能看守的点会减少并且浪费时间。往下走的充要条件是

到达了根节点，然后从根节点退下一格，到达另一个叶子。我们预处理每个节点如果看守住

了，相当于看守住了最靠近根节点的哪个节点。我们发现如果一个点只有一个儿子，那么看

守它的儿子也就相当于看守了它。

接下来我们考虑对于给定的时间k，如何检验它是否合法。我们把每一个有军队的节点

向靠近根节点的方向走，直到不能走为止。如果一个军队没有走到根节点，那么他显然只能

去看守最后到达的那个节点，这已经是最优方案。接下来我们考虑对于到达根节点的所有点

中，我们记录每个点的两个属性：一是他来自哪里，二是他还能走多长时间的路。接下来的

贪心策略是如果一个点的剩余路程不足以使得他回到他来自的哪个节点，我们则把他退回

去，并且删掉这样的点。接下来我们把剩余到达根节点的点按照剩余路程从小到大排序，记

为数组A，把根节点的叶子节点中没有被覆盖的节点取出，并且按照到达根节点的距离进行

从小到大排序，记为数组B。最后我们把两个数组进行归并，用A中小的去覆盖B中小的，

如果B可以被完全覆盖则当前的k合法，否则不合法。时间复杂度为O(nlognlogAns)。