先手第一步之后局面被「两端取较大者」完全确定,答案写成交错和;再把同侧连取整段压成一次「区间内第一个小于 t 的位置」线段树查询,O(n log n) 求出全部起点。
OJ: roj
题目 ID: 1750
难度:提高+/省选-
标签:数据结构线段树前缀和python
创建: 2026-10-08 01:34
更新: 2026-10-08 01:34
形式化题目
- 第
轮:先手在环上任意选一个位置 ,取走 ; - 第
轮( ):只能取那些"旁边至少有一个空位"的数;若有多个可选,则必须取其中最大的那个。
对每个
注意题面的关键措辞是"有多个时,选较大的"——这不是策略,而是规则。所以只要第一步定了,整局就是唯一确定的,本题是一个"模拟 + 求所有起点"的题,不是博弈题。
正解
观察一:第一步之后,局面完全确定
取走
把剩余的那段弧从
(下标模
序列
观察二:答案是一个交错和
记
剩余
解出
问题转化为:对每个起点
观察三:同侧会连取一整段
设当前剩余区间为
- 若
:取走 ,左指针右移一位,下一步比较 与 ;只要仍 就继续从左边取。 - 若
:对称地从右边取。
也就是说,一次"连取"会取走从当前端点开始的一整段连续元素,直到遇到第一个比对面端点小的元素为止(或两个指针相遇)。整局就是在两侧之间交替做若干次这样的连取。
于是每个起点只需要
| 方向 | 要查询的量 |
|---|---|
| 左侧连取 | |
| 右侧连取 |
查询用区间最小值线段树实现:某结点的最小值
一段的交错和 求出
取走整段时,段内各元素在全局取数序列里的符号是
定义交错前缀和
其中
- 左侧段取走
,以 开头的交错和为 ; - 右侧段取走
,以 开头的交错和为 。
每段
实现细节
- 破环成链:把环复制成长度
的数组 ( )。起点 对应的弧就是下标区间 ,两个指针初值 、 。 特判:先手直接取走唯一的数,答案就是 (此时 ,代码里的循环天然不进入)。 - 64 位整数:
、 ,先手总分可达约 ,C++ 必须用 long long(Python 天然大整数,无此问题)。 - 查询的边界:左侧连取时若
内没有比 小的元素,说明两个指针在 相遇,取 ;右侧连取对称地取 。 - 符号方向:交错前缀和相减后要乘
把"全局奇偶"归到"段内奇偶",这一层最容易写反。
样例核对
| 第一步 | 剩余弧 | 第 |
||||
|---|---|---|---|---|---|---|
| 取 |
||||||
| 取 |
||||||
| 取 |
输出 3 / 3 / 4,与题面样例一致。
代码
#!/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()/**
* 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;
}复杂度
设所有起点的连取段数总和为
- 预处理:破环成链
,交错前缀和 ,线段树建树 ; - 每个起点按段结算,每段一次线段树查询
,段内交错和 。
总时间
实测耗时(本仓库随附数据,10 组,最大一组
| 最大测例 | 说明 | |
|---|---|---|
main.cpp(g+±16 -O2) |
约 0.19 s | 远低于 1 s 限时 |
main.py(CPython) |
约 1.3 s | 同一算法,纯标准库 |
对比:直接对每个起点做
总结
本题的题面写得很"博弈",但规则本身就是贪心:“有多个时选较大的” 意味着第一步之后整局确定,没有任何决策空间。识别出这一点后,题目变成"对每个起点求一个确定过程的交错和"。
三个把
- 交错和恒等式:剩余部分两人得分之和已知、之差就是交错和
,于是 ,把"求两人总分"压成"求一个交错和"。 - 连取整段:双指针每一步只在"较大的一侧"取数,因此同侧会连续取走一整段,直到遇到第一个比对面端点小的元素。这把手数从
降到 ,而段数在实践中很小。 - 交错前缀和 + 线段树:段内符号交替,用
一次减法得到整段的交错和;段边界用"区间内第一个小于 的位置"查询,线段树下降 。
三者的分工很清晰:第 1 条消掉一半的规模,第 2 条消掉手数,第 3 条消掉定位成本。只做其中一两条都过不了
数据说明
本题随仓库附带的 data/(problem1.in ~ problem10.in)是自造数据:原题(一本通 1750)未提供公开测试数据,本仓库的生成脚本 data.py 按题面数据范围分层构造,覆盖
- 边界:
(含 )、 ; - 题面样例:
; - 子任务:
随机、 、随机数据; - 规模:
锯齿结构、 随机、 随机且值域接近 。
所有点均要求