[NOIP2013-普及]小朋友的数字

题目描述

有 $n$ 个小朋友排成一列，每人手上有整数 $a_i$ （可正可负）。特征值 $d_i$ 为前 $i$ 人中连续非空子段和的最大值；分数 $s_1=d_1$ ， $s_i\ (i\ge2)$ 为前面所有人中 $s_j+d_j$ 的最大值。求 $\max s_i$ ，保持符号并将绝对值对 $p$ 取模后输出。

数据范围： $1\le n\le10^6$ ， $1\le p\le10^9$ ， $|a_i|\le10^9$ 。

思路

特征值是前缀最大子段和，用 Kadane 滚动 end_here 并维护历史最大 trait。分数需要前面所有人 score+trait 的最大值，再用一个滚动变量 g 维护。全程四个标量， $O(n)$ 时间、 $O(1)$ 额外空间。注意负数输出保持符号。

参考代码

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#!/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-02 10:18
# update_at: 2026-10-02 10:18

import sys

NEG = -(1 << 62)  # 分数下界的哨兵：|分数| 不可能超过 n·2·10^9


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    p = int(next(data))

    best = NEG        # 全体小朋友分数的最大值（带符号）
    end_here = 0      # 以当前人结尾的最大子段和（Kadane 滚动值）
    trait = NEG       # 特征值：前缀 [1..i] 内的最大子段和
    g = NEG           # 已看过的人中 score_j + trait_j 的最大值

    for i in range(n):
        a = int(next(data))
        end_here = max(end_here + a, a)
        trait = max(trait, end_here)  # 特征值不要求子段以 i 结尾

        # 分数：第 1 个人是自己的特征值；
        # 其他人是前面所有人中「分数 + 特征值」的最大值
        score = trait if i == 0 else g
        best = max(best, score)
        g = max(g, score + trait)

    # 输出保持符号：负数输出 -(|best| mod p)，非负输出 best mod p
    print(best % p if best >= 0 else -(abs(best) % p))


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/**
 * 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:06
 * update_at: 2026-10-06 15:06
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll NEG = -(1LL << 62); // 足够小的哨兵

ll n, p;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p;

    ll best = NEG;      // 所有分数的最大值（带符号）
    ll end_here = 0;    // 以当前位置结尾的最大子段和
    ll trait = NEG;     // 特征值：前缀 [1..i] 的最大子段和
    ll g = NEG;         // 已处理的人中 score_j + trait_j 的最大值

    for (ll i = 0; i < n; ++i) {
        ll a;
        cin >> a;
        end_here = max(end_here + a, a);
        trait = max(trait, end_here); // 特征值不要求子段以 i 结尾

        ll score = trait;
        if (i > 0) score = g; // 第 1 个人特征值，其余取前面 score+trait 的最大值
        best = max(best, score);
        g = max(g, score + trait);
    }

    if (best >= 0)
        cout << (best % p) << "\n";
    else
        cout << -(abs(best) % p) << "\n";

    return 0;
}

[NOIP2013-普及]小朋友的数字

目录

题目描述

思路

参考代码