感觉这题递归的思想挺值得借鉴的。
特判 \(n = 3\)。
首先根据样例不难猜测最小次数为 \(n\)。事实上最小次数下界为 \(n\),因为设 \(x\) 为当前相邻元素相同对数,不难发现除第一次操作外 \(x\) 最多增加 \(2\),而终态中 \(x = 2n - 2\)。我们尝试构造能达到下界的方案。
手玩几组数据发现,有一个看起来很通用的解法,使得只左移两位。例如 \(n = 8\)(O
代表空位):
OOBABABABABABABABA
此时我们把最右边的 AB
移到左边去:
ABBABABABABABABOOA
然后把不是左端点的最左侧的 BA
移到右边去:
ABBAOOBABABABABBAA
此时中间的 BABABABA
恰好转化为 \(n = 4\) 的子问题,并且能在只左移两位的前提下排好序:
ABBAAAAABBBBOOBBAA
我们把左边的 BB
移到右边去,再把右边的 AA
移到左边去:
AAAAAAAABBBBBBBBOO
做完了!
事实上这个可以推广到任意 \(n \ge 8\) 的情况。\(n < 8\) 时我们手玩或者暴搜求出方案,然后打表即可。
code
// Problem: P6892 [ICPC2014 WF] Baggage
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6892
// Memory Limit: 1 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
vector<pii> ans;
void dfs(int l, int r) {
if (r - l + 1 == 6) {
ans.pb(l + 1, l - 2);
ans.pb(l + 4, l + 1);
ans.pb(l + 2, l - 4);
return;
}
if (r - l + 1 == 8) {
ans.pb(l + 5, l - 2);
ans.pb(l + 2, l + 5);
ans.pb(l - 1, l + 2);
ans.pb(l + 6, l - 1);
return;
}
if (r - l + 1 == 10) {
ans.pb(l + 7, l - 2);
ans.pb(l + 2, l + 7);
ans.pb(l + 5, l + 2);
ans.pb(l - 1, l + 5);
ans.pb(l + 8, l - 1);
return;
}
if (r - l + 1 == 12) {
ans.pb(l + 9, l - 2);
ans.pb(l + 6, l + 9);
ans.pb(l + 1, l + 6);
ans.pb(l + 5, l + 1);
ans.pb(l - 1, l + 5);
ans.pb(l + 10, l - 1);
return;
}
if (r - l + 1 == 14) {
ans.pb(l + 7, l - 2);
ans.pb(l + 4, l + 7);
ans.pb(l + 11, l + 4);
ans.pb(l + 2, l + 11);
ans.pb(l + 8, l + 2);
ans.pb(l - 1, l + 8);
ans.pb(l + 12, l - 1);
return;
}
ans.pb(r - 2, l - 2);
ans.pb(l + 2, r - 2);
dfs(l + 4, r - 4);
ans.pb(l - 1, r - 5);
ans.pb(r - 1, l - 1);
}
void solve() {
int n;
scanf("%d", &n);
dfs(1, n * 2);
for (pii p : ans) {
printf("%d to %d\n", p.fst, p.scd);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
打表代码:
code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
int n, a[110];
vector<pii> ans;
void dfs(int d) {
if (d > n / 2) {
bool flag = 1;
for (int i = 0; i < n / 2; ++i) {
flag &= (a[i] == 1);
}
for (int i = n / 2; i < n; ++i) {
flag &= (a[i] == 2);
}
if (flag) {
for (pii p : ans) {
printf("%d to %d\n", p.fst - 1, p.scd - 1);
}
}
return;
}
int x = -1;
for (int i = 0; i <= n; ++i) {
if (!a[i] && !a[i + 1]) {
x = i;
break;
}
}
for (int i = 0; i <= n; ++i) {
if (a[i] && a[i + 1]) {
ans.pb(i, x);
swap(a[i], a[x]);
swap(a[i + 1], a[x + 1]);
dfs(d + 1);
ans.pop_back();
swap(a[i], a[x]);
swap(a[i + 1], a[x + 1]);
}
}
}
void solve() {
scanf("%d", &n);
n <<= 1;
for (int i = 2; i <= n + 1; ++i) {
a[i] = ((i & 1) ? 1 : 2);
}
dfs(1);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}