取数字

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

先手第一步之后局面被「两端取较大者」完全确定,答案写成交错和;再把同侧连取整段压成一次「区间内第一个小于 t 的位置」线段树查询,O(n log n) 求出全部起点。

OJ: roj

题目 ID: 1750

难度:提高+/省选-

标签:数据结构线段树前缀和python

创建: 2026-10-08 01:34

更新: 2026-10-08 01:34

形式化题目

NN 个互不相同的正整数 A1,A2,…,ANA_1, A_2, \dots, A_N 围成一圈。两人轮流取数,共取 NN 轮:

  • 第 11 轮:先手在环上任意选一个位置 pp,取走 ApA_p;
  • 第 kk 轮(2⩽k⩽N2 \leqslant k \leqslant N):只能取那些"旁边至少有一个空位"的数;若有多个可选,则必须取其中最大的那个。

对每个 p∈{1,…,N}p \in \{1, \dots, N\},求先手最终取到的数之和 ans[p]ans[p]。

注意题面的关键措辞是"有多个时,选较大的"——这不是策略,而是规则。所以只要第一步定了,整局就是唯一确定的,本题是一个"模拟 + 求所有起点"的题,不是博弈题。

正解

观察一:第一步之后,局面完全确定

取走 ApA_p 后,空位集合只含 pp 一个点;此后每取走一个数,它必然与已有空位相邻,所以空位始终是环上一段连续弧,剩余的数也是一段连续弧。

把剩余的那段弧从 p+1p+1 顺时针拉直成序列

C=(c1,c2,…,cn−1),ci=Ap+i,C = (c_1, c_2, \dots, c_{n-1}), \qquad c_i = A_{p+i},

(下标模 NN)。则"旁边至少有一个空位"的候选恰好是 CC 的两个端点 c1,cn−1c_1, c_{n-1},题面规定取较大的那个。于是第 2∼N2 \sim N 轮就是双指针反复取两端较大者:

x0=max⁡(c1,cn−1),x1=max⁡(剩下区间的两端),…x_0 = \max(c_1, c_{n-1}), \quad x_1 = \max(\text{剩下区间的两端}), \quad \dots

序列 x0,x1,…,xn−2x_0, x_1, \dots, x_{n-2}(共 n−1n-1 个)由 pp 唯一决定。

观察二:答案是一个交错和

记 S=∑i=1NAiS = \sum_{i=1}^{N} A_i,并令

D=x0−x1+x2−x3+⋯(交错和).D = x_0 - x_1 + x_2 - x_3 + \cdots \qquad (\text{交错和}).

剩余 n−1n-1 个数之和为 S−ApS - A_p。其中后手取的是 x0,x2,x4,…x_0, x_2, x_4, \dots,先手(除第一步外)取的是 x1,x3,…x_1, x_3, \dots。设后手总分为 P1P_1、先手额外得分为 P2P_2,则

P1+P2=S−Ap,P1−P2=D,P_1 + P_2 = S - A_p, \qquad P_1 - P_2 = D,

解出 P1=S−Ap+D2P_1 = \dfrac{S - A_p + D}{2},于是

  ans[p]=Ap+P2=S+Ap−D2  \boxed{\;ans[p] = A_p + P_2 = \frac{S + A_p - D}{2}\;}

问题转化为:对每个起点 pp,求出弧 CC 上双指针取数的交错和 DD。

观察三:同侧会连取一整段

设当前剩余区间为 [u,v][u, v](在拉直后的下标体系里),两端值为 Au,AvA_u, A_v。

  • 若 Au>AvA_u > A_v:取走 AuA_u,左指针右移一位,下一步比较 Au+1A_{u+1} 与 AvA_v;只要仍 >Av> A_v 就继续从左边取。
  • 若 Av>AuA_v > A_u:对称地从右边取。

也就是说,一次"连取"会取走从当前端点开始的一整段连续元素,直到遇到第一个比对面端点小的元素为止(或两个指针相遇)。整局就是在两侧之间交替做若干次这样的连取。

于是每个起点只需要 O(段数)O(\text{段数}) 次查询:

方向 要查询的量
左侧连取 [u+1,v][u+1, v] 内最小的下标 ww 使 Aw<AvA_w < A_v
右侧连取 [u,v−1][u, v-1] 内最大的下标 ww 使 Aw<AuA_w < A_u

查询用区间最小值线段树实现:某结点的最小值 ⩾t\geqslant t 说明该区间整段都 <t< t 无解;否则求最小下标时先查左儿子、求最大下标时先查右儿子。单次 O(log⁡N)O(\log N)。

一段的交错和 O(1)O(1) 求出

取走整段时,段内各元素在全局取数序列里的符号是 +,−,+,−,…+,-,+,-,\dots 交替的,所以只需知道该段"以 ++ 开头"的交错和,再乘上当前起手的符号(由"已经取走了几个"的奇偶决定)。

定义交错前缀和

P[i]=∑j<i(−1)jA2[j](P[0]=0),P[i] = \sum_{j<i} (-1)^j A2[j] \qquad (P[0] = 0),

其中 A2A2 是下面说的破环成链数组。则

  • 左侧段取走 A2[u],A2[u+1],…,A2[w−1]A2[u], A2[u+1], \dots, A2[w-1],以 ++ 开头的交错和为   (−1)u(P[w]−P[u])\;(-1)^u\bigl(P[w] - P[u]\bigr);
  • 右侧段取走 A2[v],A2[v−1],…,A2[w+1]A2[v], A2[v-1], \dots, A2[w+1],以 ++ 开头的交错和为   (−1)v(P[v+1]−P[w+1])\;(-1)^v\bigl(P[v+1] - P[w+1]\bigr)。

每段 O(1)O(1) 结算,整局只花 O(段数⋅log⁡N)O(\text{段数} \cdot \log N)。

实现细节

  1. 破环成链:把环复制成长度 2N2N 的数组 A2A2(A2[i]=A[i mod N]A2[i] = A[i \bmod N])。起点 pp 对应的弧就是下标区间 [p+1, p+N−1][p+1,\, p+N-1],两个指针初值 u=p+1u = p+1、v=p+N−1v = p+N-1。
  2. N=1N = 1 特判:先手直接取走唯一的数,答案就是 A1A_1(此时 u=vu = v,代码里的循环天然不进入)。
  3. 64 位整数:N⩽3×105N \leqslant 3 \times 10^5、Ai⩽109A_i \leqslant 10^9,先手总分可达约 1.5×10141.5 \times 10^{14},C++ 必须用 long long(Python 天然大整数,无此问题)。
  4. 查询的边界:左侧连取时若 [u+1,v][u+1,v] 内没有比 AvA_v 小的元素,说明两个指针在 vv 相遇,取 w=vw = v;右侧连取对称地取 w=uw = u。
  5. 符号方向:交错前缀和相减后要乘 (−1)段起点下标(-1)^{\text{段起点下标}} 把"全局奇偶"归到"段内奇偶",这一层最容易写反。

样例核对

N=3, A=(1,2,3), S=6N = 3,\ A = (1,2,3),\ S = 6:

pp 第一步 剩余弧 第 2,32,3 轮 xx 序列 DD ans[p]=(S+Ap−D)/2ans[p] = (S+A_p-D)/2
00 取 11 (2,3)(2,3) 33 再 22 (3,2)(3,2) 3−2=13-2=1 (6+1−1)/2=3(6+1-1)/2 = 3
11 取 22 (3,1)(3,1) 33 再 11 (3,1)(3,1) 3−1=23-1=2 (6+2−2)/2=3(6+2-2)/2 = 3
22 取 33 (1,2)(1,2) 22 再 11 (2,1)(2,1) 2−1=12-1=1 (6+3−1)/2=4(6+3-1)/2 = 4

输出 3 / 3 / 4,与题面样例一致。

代码

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

import sys
from itertools import accumulate

type MinTree = list[int]                 # 区间最小值线段树的结点数组,叶子数是 2 的幂
type Chain = list[tuple[int, int, int]]  # 待回溯的状态链:(状态编码, 本段交错和, 本段长度)
type Memo = dict[int, int]               # 状态编码 u*(2N)+v -> 从该状态起、首项取 + 的交错和

BIG = 1 << 62  # 哨兵:比任何 A_i 都大,表示"该区间里没有小于阈值的元素"


def build_min_tree(values: list[int]) -> tuple[MinTree, int]:
    """区间最小值线段树;返回(结点数组, 叶子数),叶子数取 >= len(values) 的最小 2 的幂。"""
    size = 1
    while size < len(values):
        size <<= 1
    tree = [BIG] * (2 * size)
    tree[size:size + len(values)] = values
    for node in range(size - 1, 0, -1):
        left = tree[node + node]
        right = tree[node + node + 1]
        tree[node] = left if left < right else right
    return tree, size


def first_below(tree: MinTree, size: int, start: int, t: int) -> int | None:
    """最小的下标 i >= start 使 A2[i] < t;不存在返回 None(调用方用对面指针兜底)。

    先沿"根 -> 叶子 start"的路径收集被跳过的右儿子,再自近及远检查;
    命中后在该子树里一路向左下降,第一个满足的叶子就是答案。
    """
    node, nl, nr = 1, 0, size - 1
    rights: list[int] = []
    while nl < nr:
        mid = (nl + nr) >> 1
        if start <= mid:
            rights.append(node + node + 1)
            node += node
            nr = mid
        else:
            node += node + 1
            nl = mid + 1
    if tree[node] < t:  # 叶子 start 自己就够小
        return nl
    for i in range(len(rights) - 1, -1, -1):
        node = rights[i]
        if tree[node] < t:
            while node < size:
                node += node
                if tree[node] >= t:
                    node += 1
            return node - size
    return None


def last_below(tree: MinTree, size: int, start: int, t: int) -> int | None:
    """最大的下标 i <= start 使 A2[i] < t;不存在返回 None(调用方用对面指针兜底)。"""
    node, nl, nr = 1, 0, size - 1
    lefts: list[int] = []
    while nl < nr:
        mid = (nl + nr) >> 1
        if start <= mid:
            node += node
            nr = mid
        else:
            lefts.append(node + node)
            node += node + 1
            nl = mid + 1
    if tree[node] < t:
        return nl
    for i in range(len(lefts) - 1, -1, -1):
        node = lefts[i]
        if tree[node] < t:
            while node < size:
                node += node + 1
                if tree[node] >= t:
                    node -= 1
            return node - size
    return None


def alt_sums(doubled: list[int], alt: list[int], tree: MinTree, size: int) -> list[int]:
    """对每个起点 p,求弧 doubled[p+1 .. p+n-1] 上取数序列的交错和 D(首项取 +)。"""
    n = len(doubled) >> 1
    m = len(doubled)
    memo: Memo = {}  # 同一状态 (u, v) 之后的取数序列完全一致,可以复用

    def state_alt_sum(u: int, v: int) -> int:
        """状态 (u, v)(剩余弧的两端)起、首项取 + 的交错和;顺路记忆化整条状态链。

        每步是"同侧连取一整段":左端更大就一直从左边取,直到遇到第一个比右端小的
        元素(或两指针相遇);段内符号交替,故整段贡献 = 段交错和 × 当前起手符号。
        """
        chain: Chain = []
        while True:
            key = u * m + v
            cached = memo.get(key)
            if cached is not None:  # 命中记忆,后面都不用再算了
                value = cached
                break
            if u == v:  # 只剩一个数
                value = doubled[u]
                memo[key] = value
                break
            if doubled[u] > doubled[v]:
                w = first_below(tree, size, u + 1, doubled[v])
                if w is None or w > v:  # 段内没有更小的,两指针在 v 相遇
                    w = v
                length = w - u
                seg = alt[w] - alt[u]  # 段 doubled[u .. w-1],以 + 开头的交错和
                if u & 1:              # 段首下标是奇数,全局符号整体取反
                    seg = -seg
                chain.append((key, seg, length))
                u = w
            else:
                w = last_below(tree, size, v - 1, doubled[u])
                if w is None or w < u:
                    w = u
                length = v - w
                seg = alt[v + 1] - alt[w + 1]  # 段 doubled[v], doubled[v-1], ..., doubled[w+1]
                if v & 1:
                    seg = -seg
                chain.append((key, seg, length))
                v = w
        for key, seg, length in reversed(chain):  # 自链尾回溯,补齐每个状态的交错和
            value = seg - value if length & 1 else seg + value
            memo[key] = value
        return value

    return [state_alt_sum(p + 1, p + n - 1) for p in range(n)]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]
    if n == 1:  # 只有一个数,先手直接取走
        print(a[0])
        return

    total = sum(a)
    doubled = a + a  # 破环成链:起点 p 对应的弧就是 doubled[p+1 .. p+n-1]
    # alt[i] = sum_{j<i} (-1)^j doubled[j],用前缀差 O(1) 求任意一段的交错和
    alt = list(accumulate((x if (i & 1) == 0 else -x for i, x in enumerate(doubled)), initial=0))
    tree, size = build_min_tree(doubled)

    # 设取数序列为 x0, x1, ...(x0 是后手拿的),D = x0 - x1 + x2 - ...;
    # 剩余数之和 S - a[p] = 后手 + 先手额外,D = 后手 - 先手额外,
    # 于是先手总分 = a[p] + (S - a[p] - D) / 2 = (S + a[p] - D) / 2。
    print('\n'.join(str((total + a[p] - d) // 2) for p, d in enumerate(alt_sums(doubled, alt, tree, size))))


if __name__ == "__main__":
    solve()
cpp
/**
 * 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-07 21:59
 * update_at: 2026-10-07 22:40
 *
 * 一本通 1750《取数字》
 *
 * 模型:先手第一步取走 a[p] 后,已取走的数在环上构成一段连续弧,剩下的数
 * 也构成一段连续弧。把剩下的弧按顺时针拉直成序列 C(长度 n-1),此时
 * 「旁边有空位」的候选恰好是 C 的两个端点,而题面规定「有多个时选较大的」,
 * 所以第 2..n 步完全确定:每步取走 C 两端中较大的那个。
 *
 * 记这个确定序列为 x0, x1, ...(x0 是后手取走的),令
 *     D = x0 - x1 + x2 - x3 + ...        (交错和)
 * 剩余数之和为 S - a[p],其中后手得分 = (S - a[p] + D) / 2,于是
 *     先手总分 = (S + a[p] - D) / 2。
 *
 * 朴素模拟每个起点要 O(n),总 O(n^2)(N = 3e5 时约 9e10 次,必然超时)。
 * 加速的关键:双指针「取两端较大者」时,同侧会连取一整段连续元素——
 * 从当前端点出发,一直取到「第一个比对面端点小的元素」为止。因此整局只需
 * O(段数) 次查询:「右侧/左侧第一个小于 t 的位置」。用区间最小值线段树做该
 * 查询,每段 O(log n)。段数实测很小(随机数据约 13 段/起点,总段数约 1.3e7
 * 的 1/3),总复杂度 O(总段数 * log n),N = 3e5 时约 0.3s。
 *
 * 每段贡献可用交错前缀和 O(1) 求出:令 P[i] = sum_{j<i} (-1)^j * A2[j],则
 * 左侧段 A2[u..w-1] 的交错和(以 + 开头)为 (-1)^u * (P[w] - P[u]),
 * 右侧段 A2[v], A2[v-1], ..., A2[w+1] 的为 (-1)^v * (P[v+1] - P[w+1])。
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 300000 + 5;

int n;                 // 环上数字个数
int a[MAXN];           // 原环
int A2[2 * MAXN];      // 环复制两遍,起点 p 对应的弧即 A2[p+1 .. p+n-1]
ll pref[2 * MAXN + 2]; // pref[i] = sum_{j<i} (-1)^j * A2[j]
ll sum_all;            // S = Σ a[i]

int segN;            // 线段树的叶子数(2 的幂)
int mn[1 << 21];     // 线段树:区间最小值

// 快速读入
inline int readInt() {
    int x = 0;
    int c = getchar();
    while (c < '0' || c > '9') {
        if (c == EOF) return 0;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x;
}

// 最小的下标 i ∈ [ql, qr] 使 A2[i] < t;不存在返回 -1
int firstLess(int node, int nl, int nr, int ql, int qr, int t) {
    if (qr < nl || nr < ql || mn[node] >= t) return -1;
    if (nl == nr) return nl;
    int mid = (nl + nr) >> 1;
    int res = firstLess(node << 1, nl, mid, ql, qr, t);
    if (res != -1) return res;
    return firstLess(node << 1 | 1, mid + 1, nr, ql, qr, t);
}

// 最大的下标 i ∈ [ql, qr] 使 A2[i] < t;不存在返回 -1
int lastLess(int node, int nl, int nr, int ql, int qr, int t) {
    if (qr < nl || nr < ql || mn[node] >= t) return -1;
    if (nl == nr) return nl;
    int mid = (nl + nr) >> 1;
    int res = lastLess(node << 1 | 1, mid + 1, nr, ql, qr, t);
    if (res != -1) return res;
    return lastLess(node << 1, nl, mid, ql, qr, t);
}

int main() {
    n = readInt();
    for (int i = 0; i < n; ++i) {
        a[i] = readInt();
        sum_all += a[i];
    }
    if (n == 1) { // 只有一个数,先手直接拿走
        printf("%lld\n", sum_all);
        return 0;
    }

    int M = 2 * n;
    for (int i = 0; i < M; ++i) A2[i] = a[i % n];
    for (int i = 0; i < M; ++i)
        pref[i + 1] = pref[i] + ((i & 1) ? -1LL : 1LL) * A2[i];

    segN = 1;
    while (segN < M) segN <<= 1;
    for (int i = 0; i < segN; ++i) mn[segN + i] = (i < M) ? A2[i] : INT_MAX;
    for (int i = segN - 1; i >= 1; --i) mn[i] = min(mn[2 * i], mn[2 * i + 1]);

    for (int p = 0; p < n; ++p) {
        // 起点 p:剩余弧是 A2[p+1 .. p+n-1],两个指针在两端
        int u = p + 1, v = p + n - 1;
        ll D = 0;
        int step = 1; // 当前这一手是「弧内第几个被取走」的(从 1 开始)
        while (u < v) {
            if (A2[u] > A2[v]) {
                // 左指针连取:一直取到第一个小于 A2[v] 的位置 w
                int w = firstLess(1, 0, segN - 1, u + 1, v, A2[v]);
                if (w < 0) w = v; // 该段内没有更小的,则两指针在 v 相遇
                int len = w - u;
                if (len > 0) {
                    ll val = pref[w] - pref[u];
                    if (u & 1) val = -val;
                    D += ((step & 1) ? 1 : -1) * val;
                    step += len;
                }
                u = w;
            } else {
                // 右指针连取:一直取到第一个小于 A2[u] 的位置 w
                int w = lastLess(1, 0, segN - 1, u, v - 1, A2[u]);
                if (w < 0) w = u;
                int len = v - w;
                if (len > 0) {
                    ll val = pref[v + 1] - pref[w + 1];
                    if (v & 1) val = -val;
                    D += ((step & 1) ? 1 : -1) * val;
                    step += len;
                }
                v = w;
            }
        }
        D += ((step & 1) ? 1 : -1) * (ll)A2[u]; // 最后一个元素
        printf("%lld\n", (sum_all + (ll)a[p] - D) / 2);
    }
    return 0;
}

复杂度

设所有起点的连取段数总和为 KK。

  • 预处理:破环成链 O(N)O(N),交错前缀和 O(N)O(N),线段树建树 O(N)O(N);
  • 每个起点按段结算,每段一次线段树查询 O(log⁡N)O(\log N),段内交错和 O(1)O(1)。

总时间 O(N+Klog⁡N)O(N + K \log N),空间 O(N)O(N)。

KK 的量级:实测在本题数据上,N=3×105N = 3 \times 10^5 的随机数据 K≈3.9×106K \approx 3.9 \times 10^6(平均约 1313 段/起点), 排序、锯齿、单峰、随机等构造均不超过 12N12N。段数的上界是 O(N2)O(N^2)(例如 N,N−2,N−4,…,2,1,3,…,N−1N, N-2, N-4, \dots, 2, 1, 3, \dots, N-1 这类"两端交替递减"的构造可以让单局产生 Θ(N)\Theta(N) 段), 但这类构造在 NN 个起点上的总段数实测也只有 3N3N 左右,实际数据下远达不到上界。

实测耗时(本仓库随附数据,10 组,最大一组 N=300000N = 300000):

最大测例 说明
main.cpp(g+±16 -O2) 约 0.19 s 远低于 1 s 限时
main.py(CPython) 约 1.3 s 同一算法,纯标准库

对比:直接对每个起点做 O(N)O(N) 双指针模拟是 O(N2)O(N^2),N=3×105N = 3 \times 10^5 时约 9×10109 \times 10^{10} 次操作,C++ 也要约 24 s,必然超时。

总结

本题的题面写得很"博弈",但规则本身就是贪心:“有多个时选较大的” 意味着第一步之后整局确定,没有任何决策空间。识别出这一点后,题目变成"对每个起点求一个确定过程的交错和"。

三个把 O(N2)O(N^2) 降到 O(Nlog⁡N)O(N \log N) 的要素:

  1. 交错和恒等式:剩余部分两人得分之和已知、之差就是交错和 DD,于是 ans[p]=(S+Ap−D)/2ans[p] = (S + A_p - D)/2,把"求两人总分"压成"求一个交错和"。
  2. 连取整段:双指针每一步只在"较大的一侧"取数,因此同侧会连续取走一整段,直到遇到第一个比对面端点小的元素。这把手数从 O(N)O(N) 降到 O(段数)O(\text{段数}),而段数在实践中很小。
  3. 交错前缀和 + 线段树:段内符号交替,用 P[i]=∑j<i(−1)jA2[j]P[i] = \sum_{j<i}(-1)^j A2[j] 一次减法得到整段的交错和;段边界用"区间内第一个小于 tt 的位置"查询,线段树下降 O(log⁡N)O(\log N)。

三者的分工很清晰:第 1 条消掉一半的规模,第 2 条消掉手数,第 3 条消掉定位成本。只做其中一两条都过不了 N=3×105N = 3 \times 10^5。

数据说明

本题随仓库附带的 data/(problem1.in ~ problem10.in)是自造数据:原题(一本通 1750)未提供公开测试数据,本仓库的生成脚本 data.py 按题面数据范围分层构造,覆盖

  • 边界:N=1N = 1(含 A1=109A_1 = 10^9)、N=2N = 2;
  • 题面样例:N=3, (1,2,3)→(3,3,4)N = 3,\ (1,2,3) \to (3,3,4);
  • 子任务:N⩽5000N \leqslant 5000 随机、Ai=iA_i = i、随机数据;
  • 规模:N=105N = 10^5 锯齿结构、N=2×105N = 2 \times 10^5 随机、N=3×105N = 3 \times 10^5 随机且值域接近 10910^9。

所有点均要求 AiA_i 互不相同,与题面一致。期望输出由标程产生;本文两份代码已在全部 10 组上逐字节比对通过,并与 O(N2)O(N^2) 暴力在 N⩽40N \leqslant 40 的数百组随机/构造数据上对拍一致。