题解 UVA1697 【Baggage】

构造神题，听说是当年 `WF` 的压轴题 ~~（这种东西怎么可能会）~~ 考虑增量构造，发现 $n=3,4,5,6,7$ 都是可以手玩的（ ```cpp if (len == 3 << 1) return oo(2, -1), oo(5, 2), oo(3, -3), void() ; if (len == 4 << 1) return oo(L + 5, L - 2), oo(L + 2, L + 5), oo(L - 1, L + 2), oo(L + 6, L - 1), void() ; if (len == 5 << 1) return oo(L + 7, L - 2), oo(L + 2, L + 7), oo(L + 5, L + 2), oo(L - 1, L + 5), oo(L + 8, L - 1), void() ; if (len == 6 << 1) return oo(L + 9, L - 2), oo(L + 6, L + 9), oo(L + 1, L + 6), oo(L + 5, L + 1), oo(L - 1, L + 5), oo(L + 10, L - 1), void() ; if (len == 7 << 1) return oo(L + 7, L - 2), oo(L + 4, L + 7), oo(L + 11, L + 4), oo(L + 2, L + 11), oo(L + 8, L + 2), oo(L - 1, L + 8), oo(L + 12, L - 1), void() ; ``` 比如 $n=4$ 就是这样： >`__babababa` > >`abbabab__a` > >`abba__bbaa` > >`a__abbbbaa` > >`aaaabbbb__` 那么接下来考虑以 $4$ 为增量构造解。 对于 $n+4$，记 $|BA|$ 表示有一堆 `bababa` 这种东西。 那么考虑 $n+4$ 可以这么玩： > `__|BA|` > > `ab|BA|b__a` > > `abba__|BA|bbaa` 发现中间那一段和起始状态是一样的，就可以大力递归，回溯的时候回代一下即可。 ```cpp void oo(int x, int y){ cout << x << " to " << y << '\n' ; } void work(int L, int R){ int len = R - L + 1 ; if (len == 3 << 1) return oo(2, -1), oo(5, 2), oo(3, -3), void() ; if (len == 4 << 1) return oo(L + 5, L - 2), oo(L + 2, L + 5), oo(L - 1, L + 2), oo(L + 6, L - 1), void() ; if (len == 5 << 1) return oo(L + 7, L - 2), oo(L + 2, L + 7), oo(L + 5, L + 2), oo(L - 1, L + 5), oo(L + 8, L - 1), void() ; if (len == 6 << 1) return oo(L + 9, L - 2), oo(L + 6, L + 9), oo(L + 1, L + 6), oo(L + 5, L + 1), oo(L - 1, L + 5), oo(L + 10, L - 1), void() ; if (len == 7 << 1) return oo(L + 7, L - 2), oo(L + 4, L + 7), oo(L + 11, L + 4), oo(L + 2, L + 11), oo(L + 8, L + 2), oo(L - 1, L + 8), oo(L + 12, L - 1), void() ; oo(R - 2, L - 2), oo(L + 2, R - 2), work(L + 4, R - 4), oo(L - 1, R - 5), oo(R - 1, L - 1) ; } int main(){ while (cin >> N) work(1, N * 2), puts("") ; } ```