专栏文章
题解：UVA1697 Baggage
UVA1697题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miojeyle
- 此快照首次捕获于
- 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(int n) {
if (n == 3) {
cout << "2 to -1\n" << "5 to 2\n" << "3 to -3\n";
} else {
work(1, 2 * n);
}
return;
}
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...