题解：P6892 [ICPC 2014 WF] Baggage

xzy_AK_IOI · 2026-06-30 10:03:19 · 题解

一种与题解不同的做法。

思路分析

观察样例，发现一些性质，比较好看出最小操作数为 n，可以通过设相邻数相同的对数加以证明，这里不做讨论。还有的性质是这一次的 f 即为下一次的 t，且所有 f 互不相同，所有 t 互不相同。

通过手模样例，发现第二个 n=8 的样例比较有启发性。

这是前四步的操作，具体地，我们可以发现它将前面 \frac{n}{4} 个四个字母的区间都变为了 \texttt{A B B A}，后面的 \frac{n}{4} 个区间都变为了 \texttt{B B A A}，且中间剩余的 \texttt{B A} 没了。

但这并不适用于所有区间，可以发现，这只适用于 n\equiv 0\pmod {4} 的情况，这启示我们按 n 模 4 的余数分类。

n\equiv 0\pmod {4}

以上已讨论过第一部分，即只交换 \texttt{B A} 和 \texttt{A B} 的部分。

下面再看 n=8 的样例：

可以看出这是前 \frac{n}{4} 个区间与后 \frac{n}{4} 个区间交替交换，分别将 \texttt{A A} 和 \texttt{B B} 换到对面。

n\equiv 1\pmod {4}

观察 n=5 的样例：

发现换到这一步时不满足第一种情况的规律，具体的，中间的 \texttt{B A} 变为了 \texttt{B A B A}，再看下两步：

发现其实是将前 \frac{n}{4} 个区间变为了 \frac{n-1}{4} 个，然后将最中间的区间的右端点换到 \texttt{A x x B} 那里。

然后依然是和上面一样的，较简单，不再叙述。

n\equiv 3\pmod {4}

手模 n=3 可能会没有什么建树，你会发现它甚至不满足一开始发现的性质。只能退而求其次，模 n=7。

打表发现其中一种解是这样的：

依照上述方法，将其化为长度为 4 的小区间，容易发现，前 \frac{n-3}{4} 个区间在第一部分时为 \texttt{A B B A}，而后 \frac{n+1}{4} 个区间为 \texttt{B B A A}。

对于第 \frac{n+1}{4} 个区间，发现它的两个 \texttt{B A} 分别被交换给了后面的两个区间，而回报是一个 \texttt{x x A B}，然后将后面一个的 \texttt{A A} 交换给它即可，后面和上面一样。

n\equiv 2\pmod {4}

直接手摸 n=6：

发现可以将它化为前后各 \frac{n-2}{4} 个区间，中间一个 \texttt{A B A B A B} 的区间，然后按照第 2,3,4,5 步的操作处理中间长度为 6 的区间，前后操作同上。

记得特判 n=3。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lli long long
#define db long double
#define ull unsigned long long
#define F(i,k,n) for (int i=k;i<=n;i++)
#define R(i,k,n) for (int i=k;i>=n;i--)
#define pu push_back
#define mpr make_pair
#define ins insert
#define lowb(x) (x&(-x))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mes(a,b) memset(a,b,sizeof a)
const int N=1e5+10;
const int M=50;
const int inf=1e12;
int n;
int a[N],b[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    if (n%4==0){
        a[1]=-1;
        b[1]=2;
        F(i,2,n/4){
            a[i]=a[i-1]+4;
            b[i]=b[i-1]+4;
        }
        a[n/2]=2*n-3;
        b[n/2]=2*n;
        R(i,n/2-1,n/4+1){
            a[i]=a[i+1]-4;
            b[i]=b[i+1]-4;
        }
        F(i,n/4+1,n/2-1){
            cout<<a[i]+1<<" to "<<a[i-n/4]<<'\n';
            cout<<a[i+1-n/4]<<" to "<<a[i]+1<<'\n';
        }
        cout<<a[n/2]+1<<" to "<<a[n/4]<<'\n';
        cout<<b[n/4]+1<<" to "<<a[n/2]+1<<'\n';
        cout<<a[1]+1<<" to "<<b[n/4]+1<<'\n';
        cout<<a[n/4+1]+2<<" to "<<a[1]+1<<'\n';
        F(i,2,n/4){
            cout<<a[i]+1<<" to "<<a[i+n/4-1]+2<<'\n';
            cout<<a[i+n/4]+2<<" to "<<a[i]+1<<'\n';
        } 
    }
    else if (n%4==1){
        a[1]=-1;
        b[1]=2;
        F(i,2,(n+1)/2){
            a[i]=a[i-1]+4;
            b[i]=b[i-1]+4;
        }
        F(i,1,n/4){
            cout<<a[(n+1)/2-i+1]+1<<" to "<<a[i]<<'\n';
            cout<<a[i+1]<<" to "<<a[(n+1)/2-i+1]+1<<'\n';
        }
        cout<<b[n/4+1]<<" to "<<a[n/4+1]<<'\n';
        cout<<a[1]+1<<" to "<<b[n/4+1]<<'\n';
        F(i,1,n/4-1){
            cout<<a[i+n/4+1]+2<<" to "<<a[i]+1<<'\n';
            cout<<a[i+1]+1<<" to "<<a[i+n/4+1]+2<<'\n';
        } 
        cout<<a[(n+1)/2]+2<<" to "<<a[n/4]+1<<'\n';
    }
    else if (n%4==3){
        if (n==3){
            cout<<"2 to -1\n5 to 2\n3 to -3";
            return 0;
        }
        a[1]=-1;
        b[1]=2;
        F(i,2,(n+1)/2){
            a[i]=a[i-1]+4;
            b[i]=b[i-1]+4;
        }
        F(i,1,n/4-1){
            cout<<a[(n+1)/2-i+1]+1<<" to "<<a[i]<<'\n';
            cout<<a[i+1]<<" to "<<a[(n+1)/2-i+1]+1<<'\n';
        }
        cout<<a[(n+1)/2-n/4+1]+1<<" to "<<a[n/4]<<'\n';
        cout<<a[n/4+1]+2<<" to "<<a[(n+1)/2-n/4+1]+1<<'\n';
        cout<<a[n/4+2]+1<<" to "<<a[n/4+1]+2<<'\n';
        cout<<a[n/4+1]<<" to "<<a[n/4+2]+1<<'\n';
        cout<<a[n/4+2]+2<<" to "<<a[n/4+1]<<'\n';
        F(i,n/4+2,(n+1)/2-1){
            cout<<a[(n+1)/2-i]+1<<" to "<<a[i]+2<<'\n';
            cout<<a[i+1]+2<<" to "<<a[(n+1)/2-i]+1<<'\n';
        } 
    }
    else{
        a[1]=-1;
        b[1]=2;
        F(i,2,n/4){
            a[i]=a[i-1]+4;
            b[i]=b[i-1]+4;
        }
        a[n/2]=2*n-3;
        b[n/2]=2*n;
        R(i,n/2-1,n/4+1){
            a[i]=a[i+1]-4;
            b[i]=b[i+1]-4;
        }
        F(i,1,n/4-1){
            cout<<a[n/2-i+1]+1<<" to "<<a[i]<<'\n';
            cout<<a[i+1]<<" to "<<a[n/2-i+1]+1<<'\n';
        }
        cout<<a[n/4+2]+1<<" to "<<a[n/4]<<'\n';
        cout<<a[n/4+1]+2<<" to "<<a[n/4+2]+1<<'\n';
        cout<<b[n/4]<<" to "<<a[n/4+1]+2<<'\n';
        cout<<a[n/4+1]+1<<" to "<<b[n/4]<<'\n';
        cout<<a[n/4]+1<<" to "<<a[n/4+1]+1<<'\n';
        cout<<a[n/4+2]+2<<" to "<<a[n/4]+1<<'\n';
        R(i,n/4-1,1){
            cout<<a[i]+1<<" to "<<a[n/2-i]+2<<'\n';
            cout<<a[n/2-i+1]+2<<" to "<<a[i]+1<<'\n';
        }
    }
    return 0;
}