解析

先考慮n=2的情況
可以利用一個空隊在不超過5m的操作次數(shù)下把兩個滿隊還原
如何推廣？
考慮分治
把[l,mid]的球看成同色，[mid+1,r]的球看成同色
在左右兩兩匹配柱子進(jìn)行n=2的還原操作
最后在遞歸處理
操作次數(shù)：5mnlogn

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e6+20000; const int mod=998244353; inline ll read() {ll x=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,m; int a[55][405],num[405]; int from[N],to[N],tot; bool ok[55]; void print(){printf("print:\n");for(int i=1;i<=n+1;i++){printf("[%d]:",i);for(int j=1;j<=num[i];j++) printf("%d ",a[i][j]);printf("\n");}printf("\n"); } inline void move(int x,int y){//printf("move:%d->%d\n",x,y);assert(num[x]);assert(num[y]<m);++tot;from[tot]=x;to[tot]=y;a[y][++num[y]]=a[x][num[x]--];//print();//if(tot%1000==0) fprintf(stderr,"%d\n",tot); } void solve(int l,int r){if(l>=r) return;int mid=(l+r)>>1;//fprintf(stderr,"(%d %d)\n",l,r);//print();memset(ok,0,sizeof(ok));for(int i=l;i<=mid;i++){for(int j=mid+1;j<=r;j++){//printf("i=%d j=%d\n",i,j);if(ok[i]||ok[j]) continue;int ss=0;for(int k=1;k<=m;k++){ss+=a[i][k]<=mid;ss+=a[j][k]<=mid;}int s=0;for(int k=1;k<=m;k++) s+=a[i][k]<=mid;for(int k=1;k<=s;k++) move(j,n+1);while(num[i]){if(a[i][num[i]]<=mid) move(i,j);else move(i,n+1);}for(int k=1;k<=s;k++) move(j,i);for(int k=1;k<=m-s;k++) move(n+1,i);for(int k=1;k<=m-s;k++) move(j,n+1);for(int k=1;k<=m-s;k++) move(i,j);if(ss>=m){for(int k=1;k<=m;k++){if(a[n+1][num[n+1]]<=mid&&num[i]<m) move(n+1,i);else move(n+1,j);}ok[i]=1;}else{for(int k=1;k<=m;k++){if(a[n+1][num[n+1]]>mid&&num[j]<m) move(n+1,j);else move(n+1,i);}ok[j]=1; }}}solve(l,mid);solve(mid+1,r);return; } int main() {#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();m=read();for(int i=1;i<=n;i++){num[i]=m;for(int j=1;j<=m;j++) a[i][j]=read();}//print();solve(1,n);printf("%d\n",tot);for(int i=1;i<=tot;i++) printf("%d %d\n",from[i],to[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的NOIP2020洛谷P7115:移球游戏（分治）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。