状态图是一棵树：把第 k 个环的桥递归成 T_k = T_{k-1} + T_{k-1}，在树上用 O(n^2) 的区间 DP 求起点到终点距离。
OJ: luogu
题目 ID: P9229
难度:提高
标签:树形结构动态规划递推区间 DP状压 BFS
创建: 2026-10-02 15:07
更新: 2026-10-03 11:28
形式化题目
给定一个
一步操作可以翻转
也就是
求把
注意题面里
，所以 的长度是 ，环的数量是 。样例 中 ，环有 个， 的状态串长度是 。
正解
思路
一、把游戏画成一张图
把每个状态
先算一下边数。第
点数
二、树的递归结构
第
关键观察是
- 两份拷贝各自内部的结构，恰好就是
； - 跨份边只有翻转第
位这一种，它要求 的长度 后缀，所以全图只有一条这样的边，且两个端点在同一「位置」。
于是
以
graph TD A000["000"] --- A100["100"] A100 --- A110["110"] A110 --- A010["010"] A110 --- A111["111"] A111 --- A101["101"] A101 --- A001["001"] A111 --- A011["011"]
图中最长的一条链是 010 挂在 110 下、011 挂在 111 下。可以把它读成两份 000,100,110,010 与 111,101,001,011）用 110 — 111 这条边拼起来。本例中
用 110 与 111；整个 0110 与 0111（它要求 1110，此时不能直接翻第 1110 走到桥头 0110，第 0111。
三、答案的分解
全
其中「桥头」就是
四、在
即取
的后 位（桥头）； 可以看作 （整段越界）； 不是 的子串，需要单独处理。
在
跨桥式子的含义是：从
同理定义两个单点距离：
当
最终答案
五、状态数与实现
- 递归时层数
每次减一； - 只要「同侧」下降，
不变；一旦跨桥，就会把一侧下标拉到 ，此后该侧不再变化。
实现上把
以
| 桥头 |
|||
|---|---|---|---|
| 0 | — | 0 | 0 |
| 1 | 1 |
0 | 1 |
| 2 | 11 |
3 | 1 |
| 3 | 011 |
4 | 1 |
核对：011 的父节点正是 111，翻转第
代码
cpp
```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-02 15:07
* update_at: 2026-10-02 15:07
*/
// P9229 简单九连环
//
// 把 n+1 个环的所有状态看成图的点，一次环的上下是一次翻转，这张图是一棵树。
// 记 T_k 为“只看前 k 个环、规则仍用整串 s”的状态树，则 T_k 由两棵 T_{k-1}
// 拼成，中间用第 k 个环那条边相连；连接点恰是 t_1..t_{k-1} 等于 s 的长度
// k-1 后缀的那个状态。
//
// 设 W(k,p) 表示状态 t_i = s[p-k+i]（s 上以 p 结尾的一段，越界当 0 看）。
// 树内距离可以递归：
// G(k,p1,p2) = dist_{T_k}(W(k,p1), W(k,p2))
// s[p1]==s[p2]（同侧）: G(k,p1,p2) = G(k-1,p1-1,p2-1)
// 否则（跨桥） : G(k,p1,p2) = G(k-1,p1-1,n) + 1 + G(k-1,n,p2-1)
// A(k,p) = dist_{T_k}(0^k, W(k,p))
// s[p]==0: A(k,p) = A(k-1,p-1)
// s[p]==1: A(k,p) = A(k-1,n) + 1 + G(k-1,p-1,n)
// X(k,p) = dist_{T_k}(W(k,p), 1^k)
// s[p]==1: X(k,p) = X(k-1,p-1)
// s[p]==0: X(k,p) = G(k-1,p-1,n) + 1 + X(k-1,n)
//
// 起点 0^{n+1} 到终点 1^{n+1} 必然经过第 n+1 个环那条桥，桥的两端在 T_n 中
// 分别是 0^n 与 1^n（都对应 t_1..t_n = s），于是
// 答案 = A(n,n) + 1 + X(n,n)。
//
// 沿 A、X 两条链，每层只产生一个 G 查询；这些查询的 (p1,p2) 再向下展开，
// 总状态数是 O(n^2) 的。实现：先自上而下收集每层要用的 (p1,p2)，再自下而上
// 逐层按上式计算数值。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MOD = 1000000007;
const int maxn = 2005;
const int OFF = 3; // 打包下标时的偏移，保证 -1 也能编码
const int SHIFT = 12; // n <= 2000，12 位足够放下
int n;
char str[maxn];
int c[maxn]; // c[p] = s[p]，p 越界时按 0 处理
inline int ch(int p) {
if (p < 1 || p > n) return 0;
return c[p];
}
// 把 (p1,p2)（可含 -1）打包成非负整数，并统一成 p1 <= p2
inline int pack_pair(int p1, int p2) {
if (p1 > p2) swap(p1, p2);
return ((p1 + OFF) << SHIFT) | (p2 + OFF);
}
inline int key_first(int key) { return (key >> SHIFT) - OFF; }
inline int key_second(int key) { return (key & ((1 << SHIFT) - 1)) - OFF; }
vector<int> layer[maxn]; // layer[k]：第 k 层需要计算的 (p1,p2)，有序去重
vector<int> dp[maxn]; // dp[k][i]：layer[k][i] 对应的 G 值
// 查询已算出的 G(k,p1,p2)
int get_g(int k, int p1, int p2) {
if (k <= 0 || p1 == p2) return 0;
const vector<int> &vec = layer[k];
if (vec.empty()) return 0;
int key = pack_pair(p1, p2);
int lo = 0, hi = (int)vec.size() - 1;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (vec[mid] < key) lo = mid + 1;
else hi = mid;
}
return dp[k][lo];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> (str + 1);
for (int i = 1; i <= n; i++) c[i] = str[i] - '0';
// ---------- 第一步：自上而下收集所有用到的 G 状态 ----------
// A、X 两条链在每层各产生一个 G(k-1, ·, n) 查询
int pa = n, px = n;
for (int k = n; k >= 1; k--) {
if (ch(pa) == 1) {
layer[k - 1].push_back(pack_pair(pa - 1, n));
pa = n;
} else {
pa = pa - 1;
}
if (ch(px) == 0) {
layer[k - 1].push_back(pack_pair(px - 1, n));
px = n;
} else {
px = px - 1;
}
}
// 把每层状态沿递推式向下展开
for (int k = n; k >= 1; k--) {
sort(layer[k].begin(), layer[k].end());
layer[k].erase(unique(layer[k].begin(), layer[k].end()), layer[k].end());
const vector<int> cur = layer[k];
for (int i = 0; i < (int)cur.size(); i++) {
int p1 = key_first(cur[i]);
int p2 = key_second(cur[i]);
if (p1 == p2) continue;
if (ch(p1) == ch(p2)) {
layer[k - 1].push_back(pack_pair(p1 - 1, p2 - 1));
} else {
layer[k - 1].push_back(pack_pair(p1 - 1, n));
layer[k - 1].push_back(pack_pair(n, p2 - 1));
}
}
}
sort(layer[0].begin(), layer[0].end());
layer[0].erase(unique(layer[0].begin(), layer[0].end()), layer[0].end());
// ---------- 第二步：自下而上按层计算 G ----------
dp[0].assign(layer[0].size(), 0);
for (int k = 1; k <= n; k++) {
const vector<int> &cur = layer[k];
dp[k].assign(cur.size(), 0);
for (int i = 0; i < (int)cur.size(); i++) {
int p1 = key_first(cur[i]);
int p2 = key_second(cur[i]);
if (p1 == p2) { dp[k][i] = 0; continue; }
if (ch(p1) == ch(p2)) {
dp[k][i] = get_g(k - 1, p1 - 1, p2 - 1);
} else {
ll v = get_g(k - 1, p1 - 1, n);
v = (v + 1 + get_g(k - 1, n, p2 - 1)) % MOD;
dp[k][i] = (int)v;
}
}
}
// ---------- 第三步：沿 A、X 两条链累加 ----------
int sa = 0, sx = 0;
pa = n; px = n;
for (int k = n; k >= 1; k--) {
if (ch(pa) == 0) {
pa = pa - 1; // A(k,p)=A(k-1,p-1)
} else {
sa = (sa + 1 + get_g(k - 1, pa - 1, n)) % MOD; // A(k-1,n)+1+G
pa = n;
}
if (ch(px) == 1) {
px = px - 1; // X(k,p)=X(k-1,p-1)
} else {
sx = (sx + (ll)get_g(k - 1, px - 1, n) + 1) % MOD;
px = n;
}
}
int ans = (sa + 1 + sx) % MOD;
cout << ans << "\n";
return 0;
}text
### 复杂度
- 时间复杂度：$O(n^2 \log n)$（每层排序 + 每次查询二分），$n = 2000$ 时约 $2 \times 10^6$ 个状态，实测 $< 0.2$ s。
- 空间复杂度：$O(n^2)$。
## 暴力解法
### 思路
直接按定义建图：状态用 $n+1$ 位二进制表示，枚举每个状态、每个环判断前置条件，连边后从全 $0$ 状态 BFS 到全 $1$ 状态。状态数 $2^{n+1}$，只适用于 $n \leqslant 15$。
### 代码
```cpp
```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-02 15:07
* update_at: 2026-10-02 15:07
*/
// brute.cpp：小数据暴力解，直接按定义建图跑 BFS，用来对拍验证正解。
//
// 状态 t 用 n+1 位二进制表示（第 i 位表示第 i+1 个环，0 下标）。
// 第 i 个环（1..m）可以翻转，当且仅当 t_1..t_{i-1} 恰好等于 s 的长度 i-1 的后缀。
// 从全 0 状态 BFS 到全 1 状态，最短路长度就是答案。
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 1 << 16; // 支持 n+1 <= 16，即 n <= 15
int n, m;
char str[64];
int req[64]; // req[i]：第 i 个环可翻转时，低位 i-1 位应该是什么
int dist[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n)) return 0;
cin >> (str + 1);
m = n + 1;
// 预处理每个环的“前置条件”：t_1..t_{i-1} == s 的长度 i-1 的后缀
req[1] = 0;
for (int i = 2; i <= m; i++) {
int k = i - 1; // k <= n
int val = 0;
for (int j = 1; j <= k; j++) {
// t_j 对应 s 的第 n-k+j 个字符
if (str[n - k + j] == '1') val |= 1 << (j - 1);
}
req[i] = val;
}
int total = 1 << m;
for (int i = 0; i < total; i++) dist[i] = -1;
queue<int> q;
dist[0] = 0;
q.push(0);
while (!q.empty()) {
int st = q.front(); q.pop();
for (int i = 1; i <= m; i++) {
int k = i - 1;
int low = st & ((1 << k) - 1);
if (low != req[i]) continue;
int ns = st ^ (1 << (i - 1));
if (dist[ns] == -1) {
dist[ns] = dist[st] + 1;
q.push(ns);
}
}
}
cout << dist[total - 1] << "\n";
return 0;
}text
### 复杂度
时间与空间均为 $O(2^n)$。
### 瓶颈
状态数随 $n$ 指数增长，$n = 2000$ 完全无法承受。它同时也是验证正解的实验工具：小数据上正解与暴力必须逐位一致。
## 总结
这道题的背景是九连环，但真正要用的是三条结构观察，层层递进：
1. **状态图是树。** 数一数边：可翻转的状态恰有 $2^{m-i+1}$ 个，求和得 $E = 2^m - 1 = V - 1$，再加连通性，说明图就是树。于是「最少步数」就是树上两点距离。
2. **树可以递归。** 第 $k$ 个环只依赖前 $k-1$ 位，所以 $T_k$ 是两份 $T_{k-1}$ 加上一条唯一的跨份边。答案因此拆成 $A(n,n) + 1 + X(n,n)$。
3. **区间状态 + 树距离递推。** 用 $W(k,p)$（$s$ 上以 $p$ 结尾的长度 $k$ 子串）统一表示桥头、全 $0$ 与全 $1$，得到同侧下移 / 跨桥分解的三组递推，按层 DP 即可在 $O(n^2 \log n)$ 内求出答案。
把「游戏状态」翻译成「树上的点」是本题最关键的一步；一旦看出树的递归结构，剩下的只是把树上距离写成区间下标的递推。