专栏文章
题解：P6892 [ICPC 2014 WF] Baggage
P6892题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miojfeli
- 此快照首次捕获于
- 2025/12/02 20:11 3 个月前
- 此快照最后确认于
- 2025/12/02 20:11 3 个月前
构造题。
首先我们知道达到终态需要满足相邻元素相同的对数为 ，初态为 对，操作过程中除第一次操作外（ 对）其余每次最多产生 对，所以答案的下界为 。考虑如何构造达到下界的方案。
先手模样例，以 为例，按如下步骤置换：
此时，中间的 变成了一个类似的子问题，长度为 。我们继续往下递归，直到中间部分有序：
继续构造。
可以从上例中发现一个更为通用的解法：
考虑 的情况，模拟可以发现，我们无法在左侧拓展 格的条件下完成转移，特判一下即可。
初始时有 个位置，我们每次递归需要隔离出 个位置，我们要保证下一次递归序列有效需满足 。如果 ，则 方案对此序列无效。所以对于 的序列进行递归操作， 的序列直接打表输出方案即可。
CPPvoid work(int l, int r) {
if (r - l + 1 == 8) {
cout << r - 2 << " to " << l - 2 << endl;
cout << l + 2 << " to " << r - 2 << endl;
cout << l - 1 << " to " << l + 2 << endl;
cout << r - 1 << " to " << l - 1 << endl;
} else if (r - l + 1 == 10) {
cout << r - 2 << " to " << l - 2 << endl;
cout << l + 2 << " to " << r - 2 << endl;
cout << r - 4 << " to " << l + 2 << endl;
cout << l - 1 << " to " << r - 4 << endl;
cout << r - 1 << " to " << l - 1 << endl;
} else if (r - l + 1 == 12) {
cout << r - 2 << " to " << l - 2 << endl;
cout << r - 5 << " to " << r - 2 << endl;
cout << l + 1 << " to " << r - 5 << endl;
cout << r - 6 << " to " << l + 1 << endl;
cout << l - 1 << " to " << r - 6 << endl;
cout << r - 1 << " to " << l - 1 << endl;
} else if (r - l + 1 == 14) {
cout << l + 7 << " to " << l - 2 << endl;
cout << l + 4 << " to " << l + 7 << endl;
cout << r - 2 << " to " << l + 4 << endl;
cout << l + 2 << " to " << r - 2 << endl;
cout << r - 5 << " to " << l + 2 << endl;
cout << l - 1 << " to " << r - 5 << endl;
cout << r - 1 << " to " << l - 1 << endl;
} else {
cout << r - 2 << " to " << l - 2 << endl;
cout << l + 2 << " to " << r - 2 << endl;
work(l + 4, r - 4);
cout << l - 1 << " to " << r - 5 << endl;
cout << r - 1 << " to " << l - 1 << endl;
}
return;
}
/*====================*/
void Solve() {
cin >> n;
if (n == 3) {
cout << "2 to -1\n" << "5 to 2\n" << "3 to -3\n";
} else {
work(1, 2 * n);
}
return;
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...