题解 UVA1697 【Baggage】

· · 题解

构造神题，听说是当年 WF 的压轴题 （这种东西怎么可能会）

考虑增量构造，发现 n=3,4,5,6,7 都是可以手玩的（


    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

发现中间那一段和起始状态是一样的，就可以大力递归，回溯的时候回代一下即可。

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("") ;
}