P7115

· · 个人记录

[NOIP2020] 移球游戏

挺考验思维的一道构造题，而且相当有趣。

抽象一个上提或下压的过程：

假设我们有一个目标柱 X，一个辅助柱（满）Y，以及空柱 E，保证空柱 E 为柱 n+1。

那么我们假设只有两种颜色 0 或 1：把 0 全部弄到 X 的上方，称该过程为上提；把 0 全部弄到 X 的下方，称该过程为下压。

那么我们先讨论上提：

对于柱 X 有 a 个球的颜色为 0（a\le m）：

  1. 将 Y 上方的 a 个球依次移动至 E；

  2. 将 X 柱上的球依次取出，若颜色为 0 则放入 Y，反之放入 E。

  3. 将 X 取空后，Y 与 E 恰好满了。

  4. 将 E 上方 m-a 个球依次移动至 X，再将 Y 上方 a 个球依次移动至 X。

  5. 最后将 E 中的 a 个球依次移动至 Y。

此时，X 完成了上提，并且保证了 Y 的原有顺序不改变。

下压是同理，只要将第 4 步的顺序调换一下即可。

操作步骤数是 a+m+m+a=2m+2a\le 4m。

显然这种做法可以针对某一种单一颜色，依次将每个柱上的该颜色上提，并全部移动到一个柱子上，但是该做法的步骤数达到 O(n^2m)，大概只能拿到 70pts。

考虑一种分治的做法。

我们定义一个函数 solve(l,r)，表示在满足柱子 [l,r] 包含且仅包含颜色为 [l,r] 的情况下，完成该区间问题的步骤生成。

定义 mid=\lfloor\dfrac{l+r}{2}\rfloor那么显然，要完成 solve(l,r)，只要调整好 [l,mid] 和 [mid+1,r] 满足条件，再执行 solve(l,mid) 和 solve(mid+1,r) 即可。

现在的问题就是如何调整。

显然我们可以把颜色 \le mid 抽象为颜色 0，颜色 >mid 抽象为颜色 1。

进行一个类似归并的过程，使用两个指针 i,j，初始分别指在 l 和 mid+1 上。

我们可以针对所指的两个柱，将颜色 0 尽量移动到柱 i，而颜色 1 尽量移动到柱 j。更细节地说，分两种情况：如果两个柱中颜色 0 较多，说明柱 i 可以填满，我们就设法将 0 全部填充到柱 i，并将指针 i 后移；反之则柱 j 可以填满，我们就设法将 1 全部填充到柱 j，并将指针 j 后移。

现在我们可以思考填充的方法。

先讨论填充柱 i 为颜色 0 的方法：

有了上提和下压的方法，我们可以先把柱 i 的颜色 0 下压，再把柱 j 的颜色 0 上提（过程中互相使用为辅助柱）。这样以后，我们把柱 i 上方的颜色 1 全部移到空柱，再用柱 j 上方颜色 0 将柱 i 填充满，最后把空柱上的球移动到柱 j，这样柱 j 又满了，而柱 i 则已经被颜色 0 填充了。

同理，我们用类似的方法也能完成柱 j 的 1 填充。

这样我们就可以使区间在函数执行前满足条件了。

那么这个问题就已经解决了。

操作次数的话，我们单次调整柱 i 和柱 j 的填充的操作上限是 9m。

那么可以主定理计算步骤数：

T(n)=2\cdot T(\dfrac{n}{2})+O(nm) T(n)=O(nm\log n)

常数略大但是无所谓，已经可以通过该题了。

至于一些卡常的技巧，可以在下压和上提的过程中不把 X 取空，取到柱中没有颜色 0 的时候就开始从柱 Y 和柱 E 中往回取。

然后针对这种方法应该没有更好地卡常技巧了（因为严格界定了颜色与区间的关系，柱与柱之间的相对关系没有办法转换）。

代码略长，不要彷徨。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=50,M=4e2,S=9e5;

ll n,m,step;

ll top[N+5],st[N+5][M+5],ansx[S+5],ansy[S+5];

void remove(ll u,ll v) {
    st[v][++top[v]]=st[u][top[u]--];
    ansx[++step]=u;ansy[step]=v;
}

void download(ll x,ll h,ll mid) {
    ll a=0;
    for(ll i=1;i<=m;i++) a+=(st[x][i]<=mid);
    for(ll i=1;i<=a;i++) remove(h,n+1);
    for(ll i=1;i<=m;i++) {
        if(st[x][top[x]]<=mid) remove(x,h);
        else remove(x,n+1);
    }
    for(ll i=1;i<=a;i++) remove(h,x);
    for(ll i=1;i<=m-a;i++) remove(n+1,x);
    for(ll i=1;i<=a;i++) remove(n+1,h);
}

void upload(ll x,ll h,ll mid) {
    ll a=0;
    for(ll i=1;i<=m;i++) a+=(st[x][i]>mid);
    for(ll i=1;i<=a;i++) remove(h,n+1);
    for(ll i=1;i<=m;i++) {
        if(st[x][top[x]]>mid) remove(x,h);
        else remove(x,n+1);
    }
    for(ll i=1;i<=a;i++) remove(h,x);
    for(ll i=1;i<=m-a;i++) remove(n+1,x);
    for(ll i=1;i<=a;i++) remove(n+1,h);
}

void filldown(ll x,ll y,ll mid) {
    ll a=0;
    for(ll i=1;i<=m;i++) a+=(st[x][i]>mid);
    for(ll i=1;i<=a;i++) remove(x,n+1);
    for(ll i=1;i<=a;i++) remove(y,x);
    for(ll i=1;i<=a;i++) remove(n+1,y);
}

void fillup(ll x,ll y,ll mid) {
    ll a=0;
    for(ll i=1;i<=m;i++) a+=(st[x][i]<=mid);
    for(ll i=1;i<=a;i++) remove(x,n+1);
    for(ll i=1;i<=a;i++) remove(y,x);
    for(ll i=1;i<=a;i++) remove(n+1,y);
}

bool merge(ll x,ll y,ll mid) {
    ll cnt_0=0,cnt_1=0;
    for(ll i=1;i<=m;i++) {
        if(st[x][i]<=mid) cnt_0++;
        else cnt_1++;
        if(st[y][i]<=mid) cnt_0++;
        else cnt_1++;
    }
    download(x,y,mid);upload(y,x,mid);
    if(cnt_0>=cnt_1) filldown(x,y,mid);
    else fillup(y,x,mid);
    return cnt_1>cnt_0;
}

void solve(ll l,ll r) {
    if(l==r) return;
    ll mid=(l+r)>>1;
    ll i=l,j=mid+1,tmp=0;
    while(i<=mid&&j<=r) {
        tmp=merge(i,j,mid);
        if(tmp) j++;
        else i++;
    }
    solve(l,mid);solve(mid+1,r);
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

void print() {
    writeln(step);
    for(ll i=1;i<=step;i++) {
        write(ansx[i]);putchar(' ');writeln(ansy[i]);
    }
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=n;i++) {
        top[i]=m;
        for(ll j=1;j<=m;j++) {
            st[i][j]=read();
        }
    }

    solve(1,n);

    print();

    return 0;
}