蚯蚓 - 题目列表

蚯蚓

GitHub跳转原题关系图返回列表

三队列维护「未切 / 小段 / 大段」+ 全局偏移量消化集体加 q：每秒 O(1) 取出最长蚯蚓，把 O(m(n+m)) 的模拟压到 O((n+m)log(n+m))。

OJ: roj

题目 ID: 3035

难度:提高+/省选-

标签:队列模拟

创建: 2026-10-01 11:18

更新: 2026-10-07 13:50

形式化题目

给定 $n$ 个非负整数 $a_1, \dots, a_n$ （蚯蚓长度）与参数 $m, q, p$ （ $p = u/v \in (0,1)$ 为有理数）。重复执行 $m$ 轮，每轮：

取当前所有数中的最大值 $x$ 并记录（并列时任取一个）；
把 $x$ 替换成两个新数 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ ；
除这两个新数外，其余所有数增加 $q$ 。

要求输出两组数：

第 $t, 2t, 3t, \dots$ 轮记录下的 $x$ （共 $\lfloor m/t \rfloor$ 个，按时间顺序）；
$m$ 轮结束后全部 $n + m$ 个数从大到小排序中，排名 $t, 2t, 3t, \dots$ 的数。

两行各自输出，即使一行没有数也要输出一个空行。

正解

思路

朴素做法与两个瓶颈。 直接按题意模拟：每秒扫描全部蚯蚓找最大值切开，再给其余蚯蚓集体加 $q$ 。找最大值可用堆，但"集体加 $q$ "若逐只执行，每秒 $O(n+m)$ ，总复杂度 $O(m(n+m))$ ，在 $m = 7 \times 10^6$ 下完全不可行。优化要同时解决两件事：找最大值的代价和集体加 q 的代价。

第一步：用全局偏移量消灭"集体加 q"。 注意到"其余蚯蚓每秒加 $q$ "对所有旧蚯蚓一视同仁，只有每秒新切出的两只例外。于是不必真实修改任何长度：维护一个偏移量 $\Delta$ ，规定"蚯蚓的真实长度 = 队列里存的值 $+ \Delta$ "，每秒结束时 $\Delta \mathrel{+}= q$ ；刚切出的两只本来不该参与本秒加长，就让它们入队时存"历史值 = 真实长度 $- \Delta - q$ "，把即将发生的这一次 $+q$ 预先扣掉。此后它们与全体蚯蚓一起随 $\Delta$ 虚拟增长。这样集体加 q 变成一次加法。

第二步：证明切出序列单调，用三个队列取代堆。 把蚯蚓分成三类，各放一个降序队列：

队列	装什么	初始内容
$Q_0$	从未被切过的蚯蚓	初始 $n$ 只，从大到小排序
$Q_1$	历次切出的小段 $\lfloor px \rfloor$	空
$Q_2$	历次切出的大段 $x - \lfloor px \rfloor$	空

设第 $i$ 秒被切蚯蚓长度为 $x_i$ 。关键结论：被切长度每秒至多涨 $q$ ，即 $x_{i+1} \leqslant x_i + q$ ——因为第 $i$ 秒切掉最长的那只后，剩下的每只长度都不超过 $x_i$ ，加 $q$ 后不超过 $x_i + q$ ，而新切出的两段不超过 $x_i$ 。由此可证三个队列保持降序（对队列里的存储值论证，注意存储值 = 真实长度 $- \Delta$ ）：

$Q_1$ ：设第 $i$ 秒入队的小段存储值为 $c_i = \lfloor p x_i \rfloor - \Delta_i - q$ 。由 $x_{i+1} \leqslant x_i + q$ 得 $p x_{i+1} \leqslant p x_i + pq \leqslant p x_i + q$ （ $p < 1$ ），两边取下取整得 $\lfloor p x_{i+1} \rfloor \leqslant \lfloor p x_i \rfloor + q$ ，于是 $c_{i+1} \leqslant c_i$ ；
$Q_2$ ：大段存储值 $d_i = x_i - \lfloor p x_i \rfloor - \Delta_i - q$ ，则 $d_{i+1} - d_i = (x_{i+1} - x_i) - (\lfloor p x_{i+1} \rfloor - \lfloor p x_i \rfloor) - q \leqslant q - 0 - q = 0$ ；
$Q_0$ ：初始排序一次后自然降序。

于是

\text{全局最长} = \max(Q_0 \text{队首},\ Q_1 \text{队首},\ Q_2 \text{队首})

三个队首就是每秒的全部候选，取最大后 popleft，切成的两段 append 回 $Q_1$ 、 $Q_2$ 队尾——每秒只做 3 次比较、2 次入队、1 次偏移加法，彻底不需要堆。

主循环每秒的工作量是常数，最后把三个队列展开、加 $\Delta$ 、排序输出第二行。

用样例 $n=3,\ m=7,\ q=1,\ p=1/3$ 走一遍三队列的状态（只看前三秒）：

秒	取出并切开	$Q_0$ （真实值）	$Q_1$ （真实值）	$Q_2$ （真实值）	$\Delta$
初始	—	3, 3, 2	空	空	0
1	$3 \to 1, 2$	4, 3	1	2	1
2	$4 \to 1, 3$	4, 3	1, 1	2, 3	2
3	$4 \to 1, 3$	3	1, 1, 1	2, 3, 3	3

每个队列从左到右都保持降序，所以每一秒的最长蚯蚓只会出现在三队首：第 2 秒候选是 $Q_0$ 队首 $4$ 、 $Q_1$ 队首 $1$ 、 $Q_2$ 队首 $2$ ，取出 $4$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:22
# update_at: 2026-10-01 11:22

import sys
from collections import deque

NEG = -1 << 62  # 空队哨兵：保证含哨兵的 max 一定落在非空队列上


def pop_max(queues: list[deque]) -> int:
    """从三个降序单调队列的队首中取出当前最长的蚯蚓长度。"""
    candidates = [q[0] if q else NEG for q in queues]
    pick = candidates.index(max(candidates))
    return queues[pick].popleft()


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n, m, q = int(next(data)), int(next(data)), int(next(data))
    u, v, t = int(next(data)), int(next(data)), int(next(data))

    # 三个队列分别装：未切过的蚯蚓、切出的 ⌊px⌋ 段、切出的 x-⌊px⌋ 段。
    # 队首存真实值（含此后累积的 q），单调递减；队尾存"没长过"的历史值。
    initial = sorted((int(next(data)) for _ in range(n)), reverse=True)
    queues = [deque(initial), deque(), deque()]
    cut_lengths: list[int] = []  # 每一秒被切断蚯蚓（切断前）的长度

    offset = 0  # 全局偏移：除最近切出的两只外，每只蚯蚓每秒都长 q
    for second in range(1, m + 1):
        x = pop_max(queues) + offset
        left = x * u // v    # ⌊px⌋，历史值（含累积的 q）
        right = x - left
        # 新蚯蚓从下一秒开始长：历史值要倒扣本秒之后的 q（含即将累加的这一次）
        queues[1].append(left - offset - q)
        queues[2].append(right - offset - q)
        offset += q
        cut_lengths.append(x)

    final = sorted(
        (w + offset for qu in queues for w in qu),
        reverse=True,
    )  # m 秒后所有蚯蚓的真实长度：三个降序队列拼接后归并，从大到小

    # 两行各占一行输出，没有数的行也要输出空行
    out = [cut_lengths[i] for i in range(t - 1, len(cut_lengths), t)]
    print(' '.join(map(str, out)))
    out = [final[i] for i in range(t - 1, len(final), t)]
    print(' '.join(map(str, out)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:16
 * update_at: 2026-10-06 15:16
 */
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;

// 蚯蚓（NOIP2016 / roj 3035）：三队列 + 全局偏移量，O((n+m)log(n+m))
// 队列存"历史值"，真实长度 = 存储值 + 全局偏移 delta，
// 这样"其余蚯蚓集体加 q"就折叠成一次 delta += q。

const int MAXN = 100005;   // 初始蚯蚓数上限 n <= 1e5
const int MAXM = 7000005;  // m <= 7e6，q1/q2 每秒最多各进 1 只

// 三个降序队列（证明见题解）：队首即每秒全局最长的三个候选
int q0[MAXN];  // 从未被切过的蚯蚓，初始从大到小排序
int q1[MAXM];  // 历次切出的小段 floor(p*x)，入队次序保证存储值不增
int q2[MAXM];  // 历次切出的大段 x - floor(p*x)，同理不增
int head0 = 0, tail0 = 0;  // q0 队首/队尾下标
int head1 = 0, tail1 = 0;
int head2 = 0, tail2 = 0;

// 快速输出：t=1 时两行合计可达约 1.4e7 个数，printf 太慢
char obuf[1 << 16];
int opos = 0;
void flush_out() { fwrite(obuf, 1, opos, stdout); opos = 0; }
void write_char(char c) {
    if (opos == (int)sizeof(obuf)) flush_out();
    obuf[opos++] = c;
}
void write_ll(ll x) {  // 本题长度非负，按非负处理
    if (opos > (int)sizeof(obuf) - 16) flush_out();
    char tmp[24];
    int len = 0;
    do { tmp[len++] = '0' + x % 10; x /= 10; } while (x);
    while (len) obuf[opos++] = tmp[--len];
}

int main() {
    ll n, m, q, u, v, t;
    scanf("%lld %lld %lld %lld %lld %lld", &n, &m, &q, &u, &v, &t);
    for (int i = 0; i < n; i++) scanf("%d", &q0[i]);
    sort(q0, q0 + n, greater<int>());  // q0 保持降序
    tail0 = n;

    ll delta = 0;  // 全局偏移量：真实长度 = 存储值 + delta
    bool first = true;  // 第一行控制数字间空格
    for (ll second = 1; second <= m; second++) {
        // 三个队首候选，空队列用哨兵 INT_MIN，保证选到非空队列
        int c0 = (head0 < tail0) ? q0[head0] : INT_MIN;
        int c1 = (head1 < tail1) ? q1[head1] : INT_MIN;
        int c2 = (head2 < tail2) ? q2[head2] : INT_MIN;
        ll x;  // 本秒被切蚯蚓的真实长度
        if (c0 >= c1 && c0 >= c2) { x = c0 + delta; head0++; }
        else if (c1 >= c2)        { x = c1 + delta; head1++; }
        else                      { x = c2 + delta; head2++; }

        ll left = x * u / v;   // 小段 floor(p*x)，x*u 最大约 1.5e18，用 ll
        ll right = x - left;   // 大段
        // 新切的两只不参与"本秒"加 q：历史值先倒扣 q，随后 delta 自增
        q1[tail1++] = left - delta - q;
        q2[tail2++] = right - delta - q;
        delta += q;

        if (second % t == 0) {  // 第一行：第 t, 2t, ... 秒被切前的长度
            if (!first) write_char(' ');
            first = false;
            write_ll(x);
        }
    }
    write_char('\n');  // 没有数也要输出空行

    // 第二行：m 秒后共 n+m 只，三个降序队列归并，输出排名 t, 2t, ... 的真实长度
    first = true;
    int i0 = head0, i1 = head1, i2 = head2;
    for (ll rank = 1; rank <= n + m; rank++) {
        int c0 = (i0 < tail0) ? q0[i0] : INT_MIN;
        int c1 = (i1 < tail1) ? q1[i1] : INT_MIN;
        int c2 = (i2 < tail2) ? q2[i2] : INT_MIN;
        ll val;
        if (c0 >= c1 && c0 >= c2) { val = c0 + delta; i0++; }
        else if (c1 >= c2)        { val = c1 + delta; i1++; }
        else                      { val = c2 + delta; i2++; }
        if (rank % t == 0) {
            if (!first) write_char(' ');
            first = false;
            write_ll(val);
        }
    }
    write_char('\n');
    flush_out();
    return 0;
}

复杂度

时间复杂度：主循环 $m$ 轮、每轮 $O(1)$ ，加上末尾一次排序，总计 $O\bigl((n+m)\log(n+m)\bigr)$ ；本题 $n + m \leqslant 7.1 \times 10^6$ 。
空间复杂度：三个队列共存 $n + m$ 个长度值， $O(n+m)$ 。

总结

这道题的正解由两个观察拼成：集体加 $q$ 折进一个偏移量（真实长度 = 存储值 + $\Delta$ ），切出的小段、大段各自的存储值随时间不增（被切长度每秒至多涨 $q$ ，配上下取整与偏移量的整数推导，见思路），于是三个降序队列的队首就覆盖了每秒的"全局最大"候选。它把"每秒找最大"从堆的 $O(\log)$ 降到 3 次比较，把"每秒集体加 q"从 $O(n+m)$ 降到 1 次加法，总复杂度 $O((n+m)\log(n+m))$ ，瓶颈只剩最后的排序。

实现上有两个容易踩的坑：

输出两行必须各占一行，没有数的行也要输出一个空行（直接省略会 WA）；
新切出的两段不参与"本秒"加 $q$ ，入队的历史值要倒扣 $-q$ ；随后 $\Delta$ 自增，语义保持"真实长度 = 存储值 + $\Delta$ "。

本题也是"生成序列有序"思想的代表题：新产生的元素不大于之前产生的元素，队列就比堆更合适。

图示解析

以样例（ $n=3,\ m=7,\ q=1,\ p=1/3,\ t=1$ ）完整展示 $m$ 秒内每一秒三个队列队首的竞争与被切蚯蚓的流向，"切出段如何落队、其余如何随 $\Delta$ 增长"一目了然：

秒	三队首候选（ $Q_0, Q_1, Q_2$ ）	被切长度	切成	全局最长落在
1	$3,\ \varnothing,\ \varnothing$	3	1, 2	$Q_0$
2	$4,\ 1,\ 2$	4	1, 3	$Q_0$
3	$4,\ 2,\ 3$	4	1, 3	$Q_0$
4	$\varnothing,\ 3,\ 4$	4	1, 3	$Q_2$
5	$\varnothing,\ 4,\ 5$	5	1, 4	$Q_2$
6	$\varnothing,\ 5,\ 5$	5	1, 4	$Q_1$ / $Q_2$ 并列
7	$\varnothing,\ 5,\ 6$	6	2, 4	$Q_2$

可以看到初始蚯蚓被 $q$ 持续养大、在前三秒连续领先； $Q_0$ 耗尽后， $Q_2$ 中的大段接棒成为最长， $Q_1$ 的小段永远垫底。被切长度 $3,4,4,4,5,5,6$ 每秒至多涨 $q=1$ ，正对应单调性证明里的 $x_{i+1} \leqslant x_i + q$ 。 $m$ 秒后第二行输出 = 三个队列全部元素加最终 $\Delta = 7$ 后归并排序的第 $t, 2t, \dots$ 名。

蛐蛐国最近蚯蚓成灾了！

隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有 n 只蚯蚓，第 i 只蚯蚓的长度为 $a\_i$ ，所有蚯蚓的长度都是非负整数，即可能存在长度为0的蚯蚓。

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只，将其切成两段。

若有多只最长的，则任选一只。

神刀手切开蚯蚓的位置由有理数 p 决定。

一只长度为 x 的蚯蚓会被切成两只长度分别为 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ 的蚯蚓。

特殊地，如果这两个数的其中一个等于0，则这个长度为0的蚯蚓也会被保留。

此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加一个非负整数 q 。

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。

蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m 秒才能到来。

蛐蛐国王希望知道这 m 秒内的战况。

具体来说，他希望知道：

m 秒内，每一秒被切断的蚯蚓被切断前的长度，共有 m 个数。
m 秒后，所有蚯蚓的长度，共有 n+m 个数。

输入格式

第一行包含六个整数 n,m,q,u,v,t，其中：n,m,q 的意义参考题目描述；u,v,t 均为正整数；你需要自己计算 p=u/v（保证 0

第二行包含 n 个非负整数，为 $a\_1,a\_2,…,a\_n$ ，即初始时 n 只蚯蚓的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。

输出格式

第一行输出 ⌊m/t⌋ 个整数，按时间顺序，依次输出第 t 秒，第 2t 秒，第 3t 秒，……被切断蚯蚓（在被切断前）的长度。

第二行输出 ⌊(n+m)/t⌋ 个整数，输出 m 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 t，第 2t，第 3t，……的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。

即使某一行没有任何数需要输出，你也应输出一个空行。

请阅读样例来更好地理解这个格式。

数据范围

$1 \le n \le 10^5$ ,
$0 \le a\_i \le 10^8$ ,
$0 < p < 1$ ,
$0 \le q \le 200$ ,
$0 \le m \le 7\*10^6$ ,
$0 < u < v \le 10^9$ ,
$1 \le t \le 71$

输入样例：

text

1
23 7 1 1 3 1
3 3 2

输出样例：

text

1
23 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2

样例解释

样例中，在神刀手到来前：3只蚯蚓的长度为3,3,2。

1秒后：一只长度为3的蚯蚓被切成了两只长度分别为1和2的蚯蚓，其余蚯蚓的长度增加了1。最终4只蚯蚓的长度分别为(1,2),4,3。括号表示这个位置刚刚有一只蚯蚓被切断。

2秒后：一只长度为4的蚯蚓被切成了1和3。5只蚯蚓的长度分别为：2,3,(1,3),4。

3秒后：一只长度为4的蚯蚓被切断。6只蚯蚓的长度分别为：3,4,2,4,(1,3)。

4秒后：一只长度为4的蚯蚓被切断。7只蚯蚓的长度分别为：4,(1,3),3,5,2,4。

5秒后：一只长度为5的蚯蚓被切断。8只蚯蚓的长度分别为：5,2,4,4,(1,4),3,5。

6秒后：一只长度为5的蚯蚓被切断。9只蚯蚓的长度分别为：(1,4),3,5,5,2,5,4,6。

7秒后：一只长度为6的蚯蚓被切断。10只蚯蚓的长度分别为：2,5,4,6,6,3,6,5,(2,4)。

所以，7秒内被切断的蚯蚓的长度依次为3,4,4,4,5,5,6。

7秒后，所有蚯蚓长度从大到小排序为6,6,6,5,5,4,4,3,2,2。

来源

《算法竞赛进阶指南》
acwing 可能含有视频讲解

蚯蚓

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析