自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 21:51:33，当前版本为作者最后更新于2018-11-01 18:12:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

##$x y R/D w$表示从$(x,y)$顶部取w个棋子想右/下移动 一到机房就被$Manchery$安利了这题…… 考虑$n$路归并，可以从$(1..x,1..y)$的格子归并到$(x,y)$

##$(1,1)$因为没有移动，所以只能保证顶部第一个棋子是有序的，$(2,1)(1,2)$可以通过比较$(1,1)$的顶部两个棋子来做到两个棋子的升序，$(2,2)$可以归并$(1,1)(2,1)(1,2)$做到5个有序……其他的格子可以从它之前的格子中n路归并得到序列。递归处理就可以了。 大概$(6,6)$刚好可以做到$40000$ 要做到从底向上升序的话，之前的格子得从底向上降序，反之亦然

粗略算了下复杂度……大概$O(66+36nlog36)$？？ 反正跑得过……

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#define X first
#define Y second

using namespace std;

typedef pair<int,int> pari;
typedef pair<int,pari> par;

int n;
int C[10][10];
stack<int> A[10][10],B[10][10];
priority_queue<par,vector<par>,less<par> > Q1;
priority_queue<par,vector<par>,greater<par> > Q2;

inline void move(int i,int j,int x,int y){
    for(;i<x;i++) printf("%d %d D 1\n",i,j);
    for(;j<y;j++) printf("%d %d R 1\n",i,j);
}

inline void Sort1(int x,int y){
    for(int i=1;i<=x;i++)
        for(int j=1;j<=y;j++)
            if((i!=x||j!=y)&&!A[i][j].empty()) Q1.push(par(A[i][j].top(),pari(i,j)));
    while(!Q1.empty()){
        A[x][y].push(Q1.top().X);
        int i=Q1.top().Y.X,j=Q1.top().Y.Y; Q1.pop();
        move(i,j,x,y); A[i][j].pop();
        if(!A[i][j].empty()) Q1.push(par(A[i][j].top(),pari(i,j)));
    }
}

inline void Sort2(int x,int y){
    for(int i=1;i<=x;i++)
        for(int j=1;j<=y;j++)
            if((i!=x||j!=y)&&!A[i][j].empty()) Q2.push(par(A[i][j].top(),pari(i,j)));
    while(!Q2.empty()){
        A[x][y].push(Q2.top().X);
        int i=Q2.top().Y.X,j=Q2.top().Y.Y; Q2.pop();
        move(i,j,x,y); A[i][j].pop();
        if(!A[i][j].empty()) Q2.push(par(A[i][j].top(),pari(i,j)));
    }
}

void solve(int x,int y,int wh){
    if(x==1&&y==1){
        if(!B[x][y].empty()) A[x][y].push(B[x][y].top()),B[x][y].pop();
        return ;
    }
    if((x==1&&y==2)||(x==2&&y==1)){
        if(B[1][1].empty()) return ;
        int i=B[1][1].top(); B[1][1].pop();
        if(B[1][1].empty()){ A[x][y].push(i); move(1,1,x,y); return ; }
        int j=B[1][1].top(); B[1][1].pop();
        if((i>j)^wh) printf("%d %d %c 2\n",1,1,x==1?'R':'D');
        else printf("%d %d %c 1\n%d %d %c 1\n",1,1,x==1?'R':'D',1,1,x==1?'R':'D');
        if(wh) A[x][y].push(max(i,j)),A[x][y].push(min(i,j));
        else A[x][y].push(min(i,j)),A[x][y].push(max(i,j));
        return ;
    }
    for(int i=x;i;i--)
        for(int j=y;j;j--)
            if(i!=x||j!=y) solve(i,j,wh^1);
    if(wh) Sort1(x,y);
    else Sort2(x,y);
}

int main(){
    //freopen("disks.in","r",stdin);
    //freopen("disks.out","w",stdout);
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x); B[1][1].push(x);
    }
    solve(6,6,1);
}