用奇偶性先判定奇数 n 无解,偶数 n 固定起点 1 后 DFS 回溯,靠相邻和的素数剪枝找到任意一组解。
OJ: roj
题目 ID: 2110
难度:普及-
标签:搜索回溯python
创建: 2026-10-08 07:30
更新: 2026-10-08 07:30
形式化题目
给定整数
由于条件只依赖相邻关系,
正解
思路
第一步:先用奇偶性判定什么时候无解。
奇偶交替的环要求奇数个数与偶数个数相等。而
为奇数:一定无解,不需要搜索; 为偶数( ):都有解(随仓数据 10 个点验证)。
这一步不只是"优化":若跳过它直接穷举,
第二步:破掉环的旋转对称。
数字
第三步:DFS 回溯 + 即时剪枝。
按位置
递归的出口不是"填满就成功",而要把最后一个数和 true,避免继续搜索整棵树。
最后,输出时把起点 4 3 2 5 6 1。
代码
#!/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 07:30
# update_at: 2026-10-08 07:30
import sys
MAX_N = 30 # 题面上限 n <= 30
MAX_SUM = 2 * MAX_N - 1 # 相邻两数之和的上界 n + (n-1) = 59
# ISPRIME[s]:相邻两数之和 s 是否为素数,下标即和本身;59 以内试除足够快
ISPRIME: list[bool] = [s > 1 and all(s % d for d in range(2, int(s ** 0.5) + 1))
for s in range(MAX_SUM + 1)] # 素数表 60 项
def find_ring(n: int) -> list[int] | None:
"""找一条以 1 开头、候选递增的首个素数链;无解返回 None。
n 为奇数时无解:n >= 4 的相邻和都是奇素数,故环上相邻两数必须一奇一偶、
奇偶交替,而奇数 n 的 1..n 中奇数比偶数多一个,必有"奇+奇"相邻,和为偶且 > 2。
"""
if n % 2:
return None
path = [1] # 固定起点为 1,破掉环的旋转对称
used = [False] * (n + 1)
used[1] = True
def dfs() -> bool:
"""在链尾接一个未用过的数,使相邻和为素数;能否接成完整素数环。"""
if len(path) == n:
return ISPRIME[path[-1] + path[0]] # 只剩尾首闭合这一对要检查
for v in range(2, n + 1):
can_place = not used[v] and ISPRIME[path[-1] + v]
if not can_place:
continue
used[v] = True
path.append(v)
if dfs(): # 只要任意一组解,成功信号层层上传
return True
path.pop() # 失败回溯:撤销 v
used[v] = False
return False
return path[:] if dfs() else None
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data, 0)
ring = find_ring(n) if 1 <= n <= MAX_N else None
if ring is None:
return # 奇数 n 无解:与数据约定一致,输出为空
# 输出时把起点 1 挪到末尾:环无起点,等价读法,与题面样例 `4 3 2 5 6 1` 一致
print(*ring[1:] + ring[:1])
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-08 07:30
* update_at: 2026-10-08 07:30
*/
// 一本通 2110《【例5.1】素数环》
// 题意:把 1..n 排成一个环,使相邻两数之和(含首尾这一对)均为素数,输出任意一组解。
// 数据范围:4 <= n <= 30,time 1000 ms / memory 64 MB。
//
// 关键结论(先判有无解,再搜索):
// n >= 4 时相邻两数之和至少为 1+2=3,不可能是素数 2,故相邻和都是奇素数,
// 于是环上每对相邻数必须一奇一偶 => 环上奇偶必须交替。
// n 为奇数时 1..n 中奇数比偶数多一个,环上必然出现"奇+奇",其和为偶数且 > 2,
// 不是素数 => 奇数 n 无解。偶数 n(n=4..30)都有解(本地逐点实测)。
// 正因如此先对奇数直接空输出,否则 n=29 的穷举会指数级变慢。
// 偶数 n 用 DFS 回溯:固定 a0=1 破掉"环的旋转对称",候选值递增枚举,
// 每放一个数就立即判定相邻和是否为素数,找到第一组解就层层返回。
#include <cstdio>
typedef long long ll;
const int MAXN = 30; // 题面上限 n <= 30
const int PMAX = 2 * MAXN + 1; // 相邻两数之和最大为 n+(n-1) = 59
bool is_prime[PMAX + 1]; // is_prime[s]:相邻两数之和 s 是否为素数
bool used[MAXN + 1]; // used[v]:数字 v 是否已经放进环里
int ring[MAXN]; // ring[0..n-1]:以 1 开头的素数链
ll n; // 输入的环长
// 埃氏筛:预处理 0..PMAX 的素数标记,使相邻和判定变成 O(1)
void build_prime_table() {
for (int s = 0; s <= PMAX; ++s) is_prime[s] = true;
is_prime[0] = false;
is_prime[1] = false;
for (int p = 2; p * p <= PMAX; ++p) {
if (!is_prime[p]) continue;
for (int s = p * p; s <= PMAX; s += p) is_prime[s] = false;
}
}
// ring[0..len-1] 已填好且链上相邻和均为素数,尝试填第 len 个位置;
// 找到一个完整素数环返回 true。len 从 1 开始(ring[0]=1 已固定)。
bool dfs(int len) {
if (len == n) return is_prime[ring[len - 1] + ring[0]]; // 只剩尾首闭合要检查
for (int v = 2; v <= n; ++v) {
if (used[v]) continue;
if (!is_prime[ring[len - 1] + v]) continue; // 相邻和不是素数,当前分支已死,剪枝
used[v] = true;
ring[len] = v;
if (dfs(len + 1)) return true; // 只要任意一组解,成功信号层层上传
used[v] = false; // 失败回溯:撤销 v 的占用
}
return false;
}
int main() {
if (scanf("%lld", &n) != 1) return 0;
if (n < 1) return 0; // 题面范围外,防御性退出
if (n > MAXN) return 0; // 数组按题面上限静态开,超范围直接退出
build_prime_table();
if (n % 2 != 0) return 0; // 奇数 n 无解:数据约定无解时输出为空,不打印任何内容
ring[0] = 1; // 固定起点消除旋转重复
used[1] = true;
if (!dfs(1)) return 0;
// 输出时把起点 1 挪到末尾:环没有起点,这是同一个环的另一种读法,
// 与题面样例 `4 3 2 5 6 1`(n=6)以及随仓数据的读法一致。
for (int i = 1; i < n; ++i) printf("%d ", ring[i]);
printf("%d\n", ring[0]);
return 0;
}复杂度
- 时间:最坏理论上界仍是
,但奇偶约束加上"相邻和是素数"的即时剪枝把有效状态 压缩到常数级, 时找到首解只需几十个搜索结点,远小于 1000 ms。 - 空间:递归深度
, used/ring数组,素数表 ,总计 。
总结
- 核心观察是奇偶性:
的相邻和只可能是奇素数,所以环必须奇偶交替, 奇数 直接无解。 - 有解时用"固定起点 + 即时素数剪枝 + 找到即返回"的 DFS,规模小到可以直接搜索。
- 两个易错点:末位与首位的闭合检查、以及失败分支必须恢复
used[v]。 - 数据与无解约定:随仓素材里带数据生成脚本
data.py,说明data/是自造数据 而非官方数据,题面也可能来自网络重建,与官方原题的出题意图可能有偏差。其 10 个点覆盖,其中 为奇数(无解),其 .out是 0 字节空文件——即数据发布方对"无解"的约定是不输出任何内容,而不是输出-1或提示文字,本题解遵循该约定。另外std.cpp用"固定末位为 1、首位从 2 起递增" 的搜索序,本题解用"固定首位为 1、候选递增",输出的是同一个环的不同读法;已实测两者 对这 10 个点(含样例)逐字节一致,故与随仓data/完全兼容。