Codeforces Round 1101 (Div. 2)

Shiroha白羽的博客

Shiroha · 2026-06-07 · via Shiroha白羽的博客

因为如果首个位置要留给后面的 I 人，那么这个 A 人就得放弃（前面没有非空的有空桌子）
那为什么不选择让这个 A 人坐下，放弃后面那个 I 人，这样这个 A 人和 I 人之前的 E 人就有机会找到座位
这两个方案代价一致，但是带来收益完全可以被覆盖，故上面这条成立

这是一个汉诺塔题，但是，正常情况下，每一个块必须是上面没有其他块的时候才可以移动，而这里变成了：
上面必须恰好要有 $a_i$ 块的时候，$i$ 才能移动，且仅移动 $i$ 本身（不移动其上面的部分）

我们定义当前汉诺塔有三个柱子：base(当前所在的), tmp(用来华容道的), target(目标移动到的)
对于有 $n$ 个块的汉诺塔，我们可以得到两个显而易见的结论：

对于方块 $n$，无论它在哪，并不影响其他的方块移动：因为它是最大的那个方块，任何方块都可以放到它上面，它相当于基座
汉诺塔的三座塔等价，即在任何时候，如果 $\exists$ 一种操作，可以将 $x$ 高度的汉诺塔从 base 移动到 target，那么必然存在几乎相同的操作将其移动到 tmp

所以我们可以得到如下的汉诺塔递推公式：

假定有一种方式，可以将 $n - 1$ 的汉诺塔，从 base 移动到 target
那么对于 $n$ 而言，可以先将 $n - 1$ 按照之前的方式移动到 tmp
然后将 $n$ 移动到 target
最后将之前移动到 tmp 的 $n - 1$ 再执行一次 $n - 1$ 的汉诺塔操作，移动到 target，即块 $n$ 上
得到汉诺塔的递归公式：$a_i = 2 \times a_{i-1} + 1$
其中 $a_1 = 1$

通常情况下，我们会使用递推公式直接计算通项公式或者直接算出目标值，事实上，我们仍然可以使用递归来真实计算

这里由于需要考虑到拆分（需要保留一些块在当前块上，当前块才可以移动）
所以我们定义一个新的 $g(i, j)$ 表示：初始且保持 $1 \to (j - 1)$ 在 tmp 的情况下，让 $j \to i$ 这 $i - j + 1$ 块从 base 移动到 target 需要的步数

此时 A 块表示的就是 $1 \to (j - 1)$ 块部分，而 B + C + X 表示 $j \to i$ 部分
其中 X 表示就是第 $i$ 行， C 表示 $a_i$ 部分，而 B 就是多出来的部分

$$ \begin{matrix} A \to target \\ B \to tmp \\ A \to tmp \\ X \to target \\ C \to target \\ A \to base \\ B \to target\\ A \to tmp \end{matrix} $$

其中 X 表示就是第 $i$ 行，此时 C + X 块表示的就是 $j \to i$ 块部分
而 A + C 恰好为 $a_i$，A + B 为 $1 \to (j - 1)$，B 为剩余部分

$$ \begin{matrix} A \to base \\ X \to target \\ A \to tmp \\ C \to target \end{matrix} $$

using namespace std; void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> v(n);
        for (int i = 0; i < n; ++i) cin >> v[i];
        bool ok = true;
        for (int i = 0; i < n; ++i) if (v[i] > i) ok = false;
        if (!ok) {
            printf("NO\n");
            continue;
        }
         vector<tuple<int, int, int>> ans;
        ans.reserve(1 << (n + 1));
        // if [j, i] is on base, [0, (j - 1)] on tmp, make [j, i] into target and [0, (j - 1)] into base
        int deep = 0;
        const function<void(int, int, int, int, int)> mv = [&](int i, int j, int base, int target, int tmp) {
            if (i < j) return;
            ++deep;
            // if (i != j) cerr << deep << ' ' << i << ' ' << j << ' ' << base << ' ' << target << endl;
            if (i == j && v[i] == 0) {
                ans.emplace_back(i, base, target);
            } else if (v[i] == 0) {
                mv(j - 1, 0, tmp, target, base);
                mv(i - 1, j, base, tmp, target);
                mv(j - 1, 0, target, tmp, base);
                ans.emplace_back(i, base, target);
                mv(j - 1, 0, tmp, base, target);
                mv(i - 1, j, tmp, target, base);
                mv(j - 1, 0, base, tmp, target);
            } else if (i - j >= v[i]) {
                mv(j - 1, 0, tmp, target, base);
                mv(i - 1 - v[i], j, base, tmp, target);
                mv(j - 1, 0, target, tmp, base);
                // cerr << "MOV" << ans.size() << ' ' << i << ' ' << base << ' ' << target << endl;
                ans.emplace_back(i, base, target);
                mv(i - 1, i - v[i], base, target, tmp);
                mv(j - 1, 0, tmp, base, target);
                mv(i - 1 - v[i], j, tmp, target, base);
                mv(j - 1, 0, base, tmp, target);
            } else {
                const int need = v[i] - (i - j);
                mv(need - 1, 0, tmp, base, target);
                ans.emplace_back(i, base, target);
                mv(need - 1, 0, base, tmp, target);
                mv(i - 1, j, base, target, tmp);
            }
            --deep;
        };
         mv(n - 1, 0, 1, 3, 2);
        // merge
        int r = 0;
        for (int i = 1; i < ans.size(); ++i) {
            if (get<0>(ans[i]) != get<0>(ans[r])) {
                ++r;
                ans[r] = ans[i];
            } else {
                ans[r] = {get<0>(ans[r]), get<1>(ans[r]), get<2>(ans[i])};
                if (get<1>(ans[r]) == get<2>(ans[r])) --r;
            }
        }
        printf("YES\n%d\n", r + 1);
        for (int i = 0; i <= r; ++i) {
            auto [a, b, c] = ans[i];
            printf("%d %d %d\n", a + 1, b, c);
        }
    }
}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Shiroha白羽的博客