询问 [i,j] 的奇偶性等于前缀异或 S_{i-1} xor S_j,定出全部 x_i 等价于把 n+1 个前缀点连通,答案是该完全图的最小生成树。
OJ: roj
题目 ID: 1711
难度:提高
标签:最小生成树图论primpython
创建: 2026-10-07 18:05
更新: 2026-10-07 18:05
形式化题目
有
形式化地:把每个区间
正解
思路
第一步:把"区间和"换成"前缀异或"。 令前缀异或
由于
于是一次询问
第二步:哪些
一组询问能确定全部
图 中每个点都与点 连通。
第三步:连通的最小代价 = 最小生成树。 要求
第四步:为什么用朴素 Prim。 边数是
以样例为例,
| 询问 | 边 | 权 |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 2 | ||
| 2 | ||
| 1 |
graph LR 0 -- 1 --- 1 2 -- 2 --- 0 3 -- 3 --- 0 1 -- 2 --- 2 1 -- 2 --- 3 2 -- 1 --- 3
取边
易错点。
- 答案是
条边(生成树)的权之和,最大为 , 必须用 64 位整数。 - 边权可以为
,此时"不询问"和"询问"代价相同,生成树照常可以取零权边, 算法不需要为 做任何特判;全零数据答案为 。 - 点集是
个( 也算一个点),只连 个点会漏掉 或 的信息。
代码
Python 版(用 array 存平铺矩阵,Prim 的松弛走切片,避免
#!/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-07 17:46
# update_at: 2026-10-07 18:05
import sys
from array import array
from collections.abc import Iterator
from itertools import islice
BIG = 2 * 10**9 # 哨兵:比单条费用的上限 10^9 大,且放得进 int32;本题是完全图,不会真的取到
type Weights = array # 平铺的 (n+1)×(n+1) 对称邻接矩阵,w[a*V+b] 是边 (a,b) 的权
def build_weights(n: int, data: Iterator[int]) -> Weights:
"""把输入的三角形费用摊成对称邻接矩阵:边 (a,b)(a<b)的权是题面的 c[a+1][b]。"""
V = n + 1
w = array('i', [BIG]) * (V * V) # 单条费用 <= 10^9,int32 够用,矩阵只要 16 MB
for i in range(1, n + 1):
row_len = n + 1 - i # 题面第 i 行有 n+1-i 个费用
row = array('i', islice(data, row_len))
w[(i - 1) * V + i:i * V] = row # 上三角:w[i-1][j] = c[i][j]
start = i * V + i - 1 # 下三角 w[j][i-1](j ≥ i)的首个下标
w[start:start + len(row) * V:V] = row # 按列步长 V 写入,保持矩阵对称
return w
def mst(w: Weights, V: int) -> int:
"""完全图上跑朴素 Prim:每轮取未入树的最近点,并用切片整体松弛,返回总权。"""
dist = [BIG] * V # dist[u] = 未入树的点 u 到当前树的最小边权
dist[0] = 0 # 点 0 是前缀和 S_0 = 0,从它出发
unused = list(range(V))
total = 0
for _ in range(V):
v = min(unused, key=dist.__getitem__) # 未入树的最近点
unused.remove(v)
total += dist[v]
dist[:v] = map(min, dist[:v], w[v::V]) # u < v:矩阵第 v 列
dist[v + 1:] = map(min, dist[v + 1:], w[v * V + v + 1:(v + 1) * V]) # u > v:第 v 行
return total
def solve() -> None:
# 先把 2·10^6 个整数压进 array:这样分词产生的字节对象能立刻释放,
# 否则它们会和 16 MB 的矩阵同时驻留,峰值内存多出约 110 MB。
nums = array('i', map(int, sys.stdin.buffer.read().split()))
n = nums[0]
print(mst(build_weights(n, islice(nums, 1, None)), n + 1))
if __name__ == "__main__":
solve()C++ 版(同一算法,朴素 Prim):
/**
* 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 17:46
* update_at: 2026-10-07 18:05
*/
// 最小花费:询问区间 [i,j] 的和的奇偶性 = 前缀异或 S_{i-1} xor S_j,
// 要把每个 x_i 定下来,就必须把全部前缀点 S_0..S_n 连成一块(S_0 = 0 已知),
// 于是答案就是 n+1 个点、边 (i-1,j) 权为 c[i,j] 的完全图的最小生成树。
// 稠密图用朴素 Prim,O(n^2)。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 2005; // n 的上限 2000,点数 V = n+1 <= 2001
const ll INF = 4000000000000000000LL; // 4×10^18,比最大可能答案(2000 * 10^9)大得多
int V; // 点数 = n+1,前缀点为 0..n
int w[MAXN * MAXN]; // 平铺的对称邻接矩阵,w[a*V+b] = 边 (a,b) 的权,a<b 时为 c[a+1][b]
ll minDist[MAXN]; // minDist[u] = 未入树的点 u 到当前生成树的最小边权
char used[MAXN]; // used[u] = 点 u 是否已进入生成树
// fread 缓冲的快速读入:最大输入约 22MB,逐个 scanf 会超时
static char buf[1 << 16];
static size_t bufLen = 0, bufPos = 0;
// 取下一位字符,缓冲空了就补一次
static inline int nextChar() {
if (bufPos == bufLen) {
bufLen = fread(buf, 1, sizeof(buf), stdin);
bufPos = 0;
if (bufLen == 0) return -1;
}
return buf[bufPos++];
}
// 读一个非负整数(本题费用 0 <= c <= 10^9,用 int 就够)
int readInt() {
int c = nextChar();
while (c != -1 && (c < '0' || c > '9')) c = nextChar();
int x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = nextChar();
}
return x;
}
int main() {
int n = readInt();
V = n + 1;
// 题面第 i 行给的是 c[i][j] (i <= j <= n),它正是前缀点 i-1 与 j 之间的边权
for (int i = 1; i <= n; ++i) {
int a = i - 1;
for (int j = i; j <= n; ++j) {
int cost = readInt();
w[a * V + j] = cost; // 上三角
w[j * V + a] = cost; // 对称的下三角
}
}
for (int u = 0; u < V; ++u) {
minDist[u] = INF;
used[u] = 0;
}
minDist[0] = 0; // 从点 0 出发
ll ans = 0;
for (int step = 0; step < V; ++step) {
int v = -1; // 未入树点中离树最近的那个
for (int u = 0; u < V; ++u)
if (!used[u] && (v == -1 || minDist[u] < minDist[v])) v = u;
used[v] = 1;
ans += minDist[v];
// 用新入树的 v 松弛其余未入树点
for (int u = 0; u < V; ++u)
if (!used[u] && w[v * V + u] < minDist[u]) minDist[u] = w[v * V + u];
}
printf("%lld\n", ans);
return 0;
}复杂度
- 时间:建图读入
;朴素 Prim 是 轮,每轮 找点、 松弛, 共 次基本操作。 - 空间:平铺的对称邻接矩阵
个整数, C++ 用 int约 16 MB(放得下 int),Python 用array('q')约 32 MB; 其余辅助数组。 - Python 侧风险:C++ 限时 1000 ms,纯 Python 的
常数偏大, 时本解法实测约 2 s(松弛已压到切片 + min的 C 层,只剩找最近点是的 C 层扫描),可能 TLE;但算法与 C++ 同阶,没有降级成暴力。 读入用 sys.stdin.buffer.read().split()一次性分词,峰值内存约 150 MB, 在 256 MB 限制内。
总结
- 区间异或 → 前缀异或 → 图上一条边:这是本题唯一的建模步骤,
与边 的对应关系是整个解法的支点。 - “能确定”= “连通”:充分性靠沿路径累乘异或,必要性靠"连通块整体异或 1"的对称性论证; 这一步把信息论问题翻译成纯图论问题。
- 最小连通 = 最小生成树:任何连通子图含生成树,任何生成树都连通,两边夹逼即答案。
- 稠密图选 Prim:
条边不值得排出来, 的朴素 Prim 最省事, 也正好用"一维平铺矩阵 + 对称填表"避开三角形的下标换算。
数据说明
本题素材源目录里带有数据生成脚本 data.py,其建模与上文一致
(n+1 个点的完全图最小生成树,边 data.py 的建模为准;
std.cpp 与本解法的建模一致(已用真实 data/ 逐点核对输出)。