「防线（秦腾与教学评估）」防线

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

利用至多一个奇数位置的承诺，把破绽定位转化为前缀防具总数奇偶性的 0→1 阶跃，在阶跃上二分出翻转点，再单点计数组数得到件数。

OJ: roj

题目 ID: 3025

难度:提高

标签:二分前缀和奇偶性python

创建: 2026-10-01 10:40

更新: 2026-10-07 13:50

形式化题目

把防线看成一条整数坐标轴。给定 $N$ 组防具，第 $i$ 组由三个整数 $(S_i, E_i, D_i)$ 描述，占据等差数列坐标

S_i,\ S_i + D_i,\ S_i + 2D_i,\ \dots,\ S_i + kD_i \quad (S_i + kD_i \leqslant E_i),

每个坐标上放 1 件防具。位置 $x$ 的防具数等于覆盖 $x$ 的组数。

已知整条防线上至多一个位置的防具数为奇数（0 也算偶数）。求这个位置 $P$ 与该处件数 $C$ ；若不存在这样的位置，输出 There's no weakness.。

例如样例 3 的四组防具为 $[1,10]$ 、 $\{4\}$ 、 $[1,5]$ 、 $[6,10]$ （步长均为 1），位置 4 被前三组同时覆盖，得到 3 件防具，是全防线唯一的奇数位置，输出 4 3。

正解

思路

朴素做法：枚举防线上的每个坐标 $x$ ，再遍历 $N$ 组数出覆盖 $x$ 的组数，挑出奇数位置。这条思路的瓶颈是坐标跨度—— $S_i, E_i$ 可到 $2^{31}-1$ ， $N$ 可到 $2 \times 10^5$ ，逐坐标 × 逐组是 $10^{14}$ 量级；连"防具总数不超过 $10^8$ "的上限也说明逐件累加同样不可行。

换个问法：我们并不需要知道每个位置的件数，只需要找到唯一的奇数位置。题目"至多一个奇数位置"的承诺，恰好把逐位置的信息压缩成一个前缀奇偶性。记

F(x) = \text{位置} \leqslant x \text{的防具总数}.

除破绽 $P$ （件数 $C$ 为奇数）外，所有位置的件数都是偶数，因此

F(x) \bmod 2 = \begin{cases} 0, & x < P \\[2pt] 1, & x \geqslant P \end{cases}

也就是说，判定值 F(x) & 1 是一个在 $P$ 处由 0 翻转为 1、之后恒为 1 的阶跃函数——单调，正是二分答案需要的谓词。

判定的 $O(N)$ 算法：第 $i$ 组对 $F(x)$ 的贡献是区间 $[S_i, \min(E_i, x)]$ 内的等差数列项数

c_i(x) = \left\lfloor \frac{\min(E_i, x) - S_i}{D_i} \right\rfloor + 1 \quad (x \geqslant S_i),

$x < S_i$ 时贡献为 0。于是 F(x) & 1 = 各组贡献求和后取最低位，全程只做整数四则运算，不枚举任何位置或防具。

二分区间：取 lo = min S_i - 1（左侧没有任何防具，判定必为 0）、hi = max E_i。先算 F(hi) & 1：若为 0，说明连总数都是偶数，直接输出 There's no weakness.；若为 1，则在 $[\text{lo}, \text{hi}]$ 上二分——mid 判定为 1 就收右边界，否则收左边界，while hi - lo > 1 结束时 hi 即为第一个翻转点 $P$ 。

以样例 3 展示逐位置防具数与前缀奇偶性的变化：

位置 $x$	覆盖 $x$ 的组	该处件数	$F(x)$	$F(x) \bmod 2$
0	—	0	0	0
1	A, C	2	2	0
2	A, C	2	4	0
3	A, C	2	6	0
4	A, B, C	3	9	1
5	A, C	2	11	1
6	A, D	2	13	1
7 ~ 10	A, D	2	15 ~ 21	1

表中 A~D 依次是四组防具。奇偶性只在 $x = 4$ 处翻转一次：左侧恒为 0，从 4 起恒为 1，与"至多一个奇数位置"的承诺完全对应。二分过程即在这个阶跃上收敛：lo=0, hi=10 → mid=5 判定 1 → hi=5 → mid=2 判定 0 → lo=2 → mid=3 判定 0 → lo=3 → mid=4 判定 1 → hi=4，此时 hi - lo = 1，得到 $P = 4$ 。

最后求 $C$ ： $P$ 已知，同一组的等差数列步长 $\geqslant 1$ ，至多在 $P$ 处放 1 件，所以数出满足 $S_i \leqslant P \leqslant E_i$ 且 $(P - S_i) \bmod D_i = 0$ 的组数即为 $C$ （结果必为奇数，可作自检）。

两处实现细节：题面只保证 $D_i \geqslant 0$ ，而 $D_i = 0$ 时等差数列退化（ $S_i + kD_i$ 恒为 $S_i$ ），代码先把这类组归一成单点组 $(S_i, S_i, 1)$ ；二分下界 lo = min S_i - 1 允许取到 $-1$ ，它只是保证「判定为 0」的哨兵，不会被输出。

代码

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#!/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 10:44
# update_at: 2026-10-01 10:44

import sys


def prefix_parity(groups: list[tuple[int, int, int]], x: int) -> int:
    """位置 x 及其左侧防具总数的奇偶性：1 表示唯一破绽落在 x 或其左侧。"""
    return sum(
        (min(e, x) - s) // d + 1 if x >= s else 0  # 该组在 [S, x] 区间内的件数
        for s, e, d in groups
    ) & 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    T = next(data)

    for _ in range(T):
        n = next(data)
        groups = [(next(data), next(data), next(data)) for _ in range(n)]
        groups = [(s, e if d else s, d or 1) for s, e, d in groups]  # D=0 时退化为单点 S

        lo = min(s for s, _, _ in groups) - 1  # lo 左侧没有任何防具，奇偶性必为 0
        hi = max(e for _, e, _ in groups)
        if prefix_parity(groups, hi) == 0:
            out.append("There's no weakness.")  # 整条防线累计仍是偶数：没有破绽
            continue

        # 奇偶性在破绽 P 处由 0 翻转为 1，且之后恒为 1：二分找第一个翻转位置
        while hi - lo > 1:
            mid = (lo + hi) // 2
            if prefix_parity(groups, mid):
                hi = mid
            else:
                lo = mid
        p = hi

        # 每组等差数列至多在 p 处放一件，直接数出落在 p 上的组数即为该处件数
        count = sum(1 for s, e, d in groups if s <= p <= e and (p - s) % d == 0)
        out.append(f"{p} {count}")

    print("\n".join(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/**
 * 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 14:42
 * update_at: 2026-10-06 14:42
 */
#include <cstdio>
typedef long long ll;

const int MAXN = 200005;

ll S[MAXN]; // 第 i 组防具的起点
ll E[MAXN]; // 第 i 组防具的终点
ll D[MAXN]; // 第 i 组防具的步长，D=0 时归一为 1
int n;      // 当前测试数据的防具组数

// 位置 x 及左侧防具总数的奇偶性：1 表示破绽在 x 或其左侧
ll prefix_parity(ll x) {
    ll total = 0;
    for (int i = 1; i <= n; i++) {
        if (x < S[i]) {
            continue;
        }
        // 第 i 组在 [S_i, min(E_i, x)] 内的等差数列项数
        ll right = E[i] < x ? E[i] : x;
        total += (right - S[i]) / D[i] + 1;
    }
    return total & 1;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            ll s, e, d;
            scanf("%lld %lld %lld", &s, &e, &d);
            if (d == 0) {
                e = s; // 步长为 0 时等差数列退化成单点 S
                d = 1;
            }
            S[i] = s;
            E[i] = e;
            D[i] = d;
        }

        ll lo = S[1] - 1; // lo 左侧没有任何防具，前缀奇偶性必为 0
        ll hi = E[1];
        for (int i = 2; i <= n; i++) {
            if (S[i] - 1 < lo) {
                lo = S[i] - 1;
            }
            if (E[i] > hi) {
                hi = E[i];
            }
        }

        if (prefix_parity(hi) == 0) {
            printf("There's no weakness.\n"); // 总防具数为偶数，无破绽
            continue;
        }

        // 奇偶性在破绽处由 0 翻转为 1，二分找到第一个翻转位置
        while (hi - lo > 1) {
            ll mid = (lo + hi) / 2;
            if (prefix_parity(mid)) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        ll p = hi;

        // 每组等差数列至多在 p 处放一件，数出覆盖 p 的组数即为该处件数
        ll cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (S[i] <= p && p <= E[i] && (p - S[i]) % D[i] == 0) {
                cnt++;
            }
        }
        printf("%lld %lld\n", p, cnt);
    }
    return 0;
}

复杂度

时间复杂度：每次判定 $O(N)$ ，二分区间长度不超过 $2^{31}$ ，至多 32 轮，故每组数据 $O(N \log C)$ ， $C \leqslant 2^{31}$ ； $T$ 组总计 $O(T N \log C)$ ，最坏约 $5 \times 2 \times 10^5 \times 32 \approx 3.2 \times 10^7$ 次整数运算，与标准 C++ 解法同阶。
空间复杂度： $O(N)$ 存放 $N$ 组参数，输入整体一次读入；实测最大峰值 85 MB，低于 $128 \text{ MB}$ 限制。

总结

防线的关键是题面里那句"至多只有一个位置有奇数个防具"。它把"每个位置各是多少"的逐点统计，压缩成前缀防具总数奇偶性的一次 0→1 翻转：判定 F(x) & 1 只需对每组做一次等差数列项数的整数运算，单调性让翻转点可以直接二分出来，定位后再对单点做一次组数统计得到件数。整套做法 $O(N \log C)$ ，既绕开了 $2^{31}$ 的坐标跨度，也从未真正枚举过任何一件防具。

达达学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天…受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。

就如同中二漫画的情节一样，怪兽达达打算毁掉这个世界。

数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。

由于队员们个个都智商超群，很快，行动队便来到了怪兽达达的黑暗城堡的下方。

但是，同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。

防线由很多防具组成，这些防具分成了 N 组。

我们可以认为防线是一维的，那么每一组防具都分布在防线的某一段上，并且同一组防具是等距离排列的。

也就是说，我们可以用三个整数 S， E 和 D 来描述一组防具，即这一组防具布置在防线的 S，S + D，S + 2D，…，S + KD(K∈ Z，S + KD≤E，S + (K + 1)D>E)位置上。

黑化的怪兽达达设计的防线极其精良。如果防线的某个位置有偶数个防具，那么这个位置就是毫无破绽的(包括这个位置一个防具也没有的情况，因为 0 也是偶数)。

只有有奇数个防具的位置有破绽，但是整条防线上也最多只有一个位置有奇数个防具。

作为行动队的队长，lqr 要找到防线的破绽以策划下一步的行动。

但是，由于防具的数量太多，她实在是不能看出哪里有破绽。作为 lqr 可以信任的学弟学妹们，你们要帮助她解决这个问题。

输入格式

输入文件的第一行是一个整数 T，表示有 T 组互相独立的测试数据。

每组数据的第一行是一个整数 N。

之后 N 行，每行三个整数 $S\_i，E\_i，D\_i$ ，代表第 i 组防具的三个参数,数据用空格隔开。

输出格式

对于每组测试数据，如果防线没有破绽，即所有的位置都有偶数个防具，输出一行 "There's no weakness."(不包含引号) 。

否则在一行内输出两个空格分隔的整数 P 和 C，表示在位置 P 有 C 个防具。当然 C 应该是一个奇数。

数据范围

防具总数不多于 $10^8$ ,

$S\_i \le E\_i$ ,

$1 \le T \le 5$ ,

$N \le 200000$ ,

$0 \le S\_i，E\_i，D\_i \le 2^{31}-1$

输入样例：

text

输出样例：

text

1
2
31 1
There's no weakness.
4 3

来源

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

「防线（秦腾与教学评估）」 防线

目录

形式化题目

正解

思路

代码

复杂度

总结

「防线（秦腾与教学评估）」防线