最短步数恰好为 N，按顺序保留第 1 到第 N 枚硬币不翻即可得到字典序最小方案。
OJ: luogu
题目 ID: P1146
难度:普及-
标签:构造数学
日期: 2026-06-18 21:04
题意
有 N 枚硬币，初始全部正面朝上。
每次可以翻转恰好 N-1 枚硬币，要求把所有硬币都变成反面朝上，并输出一个最短操作序列。
如果有多种最短方案，输出操作字典序最小的一种。
思路
先看一个可以直接验证想法的朴素解：
小数据时，可以把每种状态当成一个点，用 BFS 搜全 0 到全 1 的最短路。
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int all = (1 << n) - 1;
vector<int> dist(1 << n, -1), pre(1 << n, -1), op(1 << n, -1);
queue<int> q;
q.push(0);
dist[0] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == all) break;
for (int keep = 0; keep < n; keep++) {
int flip_mask = all ^ (1 << keep);
int v = u ^ flip_mask;
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
pre[v] = u;
op[v] = keep;
q.push(v);
}
}
vector<int> path;
for (int cur = all; cur != 0; cur = pre[cur]) {
path.push_back(cur);
}
reverse(path.begin(), path.end());
cout << path.size() << '\n';
for (int state : path) {
for (int i = 0; i < n; i++) {
cout << ((state >> i) & 1);
}
cout << '\n';
}
return 0;
}真正的关键是证明最短步数恰好是 N。
因为每次操作等价于“保留 1 枚硬币不翻”，设总共做了 k 步。
如果第 i 枚硬币有 c_i 次没被翻，那么它被翻了 k-c_i 次，而这个数必须是奇数。
由奇偶性可以推出：
k不可能是奇数；k为偶数时，每个c_i都必须是奇数；- 所以
k = c_1 + ... + c_n >= N。
另一方面，第 1 到第 N 步分别保留第 1 到第 N 枚硬币不翻，就刚好能在 N 步后让每枚硬币都被翻 N-1 次，最终全部变成反面。
而且这种保留顺序对应的操作串字典序最小，因此就是答案。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
cout << n << '\n';
for (int step = 1; step <= n; step++) {
for (int i = 1; i <= n; i++) {
int bit;
if (step & 1) {
bit = (i <= step ? 0 : 1);
} else {
bit = (i <= step ? 1 : 0);
}
cout << bit;
}
cout << '\n';
}
return 0;
}复杂度
主解只需要输出一个 N × N 的状态表，时间复杂度
总结
这题的关键不是搜索，而是用奇偶性先卡出最短步数，再做字典序最小的构造。