题解 P6447 [COCI2010-2011#1] ŽABE

· · 题解

洛谷。

题意

一共有 n 个人，每个人有一个编号，编号为 1\sim n。原来有一个序列，问如何操作，使其变成指定序列。

每次操作，可以使编号为 b 的人向前插队 b 格。

（比较想知道为什么我们的翻译是青蛙）。

分析

这是一道构造题，我们需要使两个序列相近。

令原序列为 A，最后的序列为 B，我们定义一个中转的序列为 C，我们需要使 A 先变成 C，再使 B 倒退成 C。

对于这个 C 序列，我们需要使他的性质要足够好，那么不妨令它是 1 直到 n。

我们在使序列接近我们的 C，我们就可以使我们匹配的顺序从小到大或者从大到小。

每次，我们使两个 C 中相邻的数 i 与 i+1 相邻。

不妨令 i 的位置在 i+1 的左侧。（因为是个环，所以可以转化）。要使两个相邻，我们有两种操作。

  1. 使 i 移动到 i+1 的左侧。
  2. 使 i 到 i+1 中间的数都移动开。

对于第一种，我们可以在模拟的过程中发现，我们移动 cnt 步实际上与移动 cnt \bmod (n-1) 步是相同的。

也就是说，我们移动 k 此后，使 i 移动到 i+1 左侧，需要 k\times i \equiv x \pmod{n-1} ，（x 为移动 x 步可以使其相邻）。

这也就使得，我们这种移动方式可能不能仅靠移动 i 使其相邻，我们需要再移动一些其他数，比较复杂，所以就不细节考虑。

对于第二种，我们贪心上可以从小到大移动这些数，是这些数移出这个区间内。

这时我们发现，我们的 n-1 不论怎么移动都无法移动出我们的区间，于是，我们在枚举相邻的数时，需要从大到小。

稍微证明一下，假如我们的另一个区间的之间长度为 D，那么我们的两个之间的数的最小值最大也就是 D+1，但是我们的这一整个区间的长度是 D+2（包括 i 与 i+1），那也就表示我们的这个点必然可以移动进这个区间。

然后我们就可以使我们的区间不断移动出这个区间了。

于是，我们就可以解决了从 A 到 C 的过程。

而我们从 B 逆推回 C，我们只需要是我们移动的方式从顺时针变成逆时针，再反向输出即可。

inline int find(int a[],int x) {
    for(int i=1; i<=n; ++i) if(a[i]==x) return i;
}

inline bool check(int L,int R,int x) {
    if(L<R) return L<x&&x<R;
    else return x<R||L<x;
}

inline void solve(int a[],int to[],bool flag) {
    top=0;
    for(int i=n-1; i; --i) {
        while(1) {
            int L=find(a,i);
            int R=find(a,i+1);
            if(L%n+1==R) break;
            int idx=L%n+1;
            for(int j=L%n+1; j!=R; j=j%n+1) if(a[j]<a[idx]) idx=j;
            R=find(a,n);
            while(check(L,R,idx)) {
                ans[++top]=a[idx];
                int cnt=a[idx];
                while(cnt--) {
                    swap(a[idx],a[to[idx]]);
                    if(a[idx]==n) R=idx;
                    else if(a[idx]==i) L=idx; 
                    idx=to[idx];
                }
            }
        }
    }
    if(!flag) for(int i=1; i<=top; ++i) cout<<ans[i]<<"\n";
    else for(int i=top; i; --i) cout<<ans[i]<<"\n";
}

总结一下，我们解决这道题需要非常的思考力，（反正我不讲绝对做不出来）。