luogu P7115 [NOIP2020] 移球游戏

本文主要是介绍luogu P7115 [NOIP2020] 移球游戏，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面传送门
首先大概有一个人口普查的40分做法：
考虑对每一种颜色单独做，主要就是将每根柱子上的球都拿到最上面。
先数出这根柱子上有多少个我们现在要拿的球，然后从另外一个柱子上拿出等量的球放在空柱子上，之后我们从当前柱子一个一个往外拿球，如果这个球是我们当前颜色的就放到我们之前拿出等量的球的柱子上，否则就放在之前的空柱子上，然后再把两边拿回来就好了，大概是\(O(n^2m)\)次操作带个\(2\)倍常数，能过\(m\leq 85\)。
似乎剪剪枝能过80（
感觉\(O(nm^2)\)不可能将常数卡下1，所以似乎可以换一种方法。
考虑分治，每次定分治区间\([l,r]\)的中点为\(m\)，然后将\([l,m]\)拿出来放在一边，\([m+1,r]\)拿出来放在另一边。如果能在\(O(nm)\)并且常数不太大的时间内做完每一层那么应该可以过。
分成两步：把每一根柱子中小于等于\(m\)的都弄到最上面以及将最上面的合并到一根柱子上。设\(n+1\)为空柱子。
第一步和上面是一样的不再赘述。第二步的话我们从\(l\)到\(m\)依次枚举\(i\)，先将第\(i\)根柱子上小于等于\(m\)的球移到\(n+1\)上。然后从\(m+1\)到\(r\)看每一根柱子，将小于等于\(m\)的球移到\(n+1\)上，直到\(n+1\)被填满为止。
然后将\(i\)填到\([m+1,r]\)上未被填满的柱子上，容易发现最多只有一根柱子上小于等于\(m\)的会被压下去，重新做一遍第一步即可。最后将\(n+1\)放回\(i\)。
容易发现这样做完后符合要求，并且常数在\([5,6]\)光景，实际上跑了大概\(65\)万次，应该是稳过的。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define ll long long
#define db double
#define lb long db
#define N (50+5)
#define M (400+5)
#define K (3000000+5)
#define mod 998244353
#define Mod (mod-1)
#define eps (1e-9)
#define ull unsigned ll
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (1ll*rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;
int n,m,A[N][M],Ts,X[K],Y[K],H[N],To;
I void Ins(int x,int y){X[++Ts]=x;Y[Ts]=y;A[y][++H[y]]=A[x][H[x]--];A[x][H[x]+1]=0;if(H[x]<0||H[y]<0||H[x]>m||H[y]>m) cerr<<Ts<<'\n',exit(0);}
I void Sep(int x,int w){int i,y=0;To=x%n+1;for(i=1;i<=m;i++) y+=(A[x][i]<=w);for(i=1;i<=y;i++) Ins(To,n+1);for(i=m;i;i--) A[x][i]<=w?Ins(x,To):Ins(x,n+1);for(i=1;i<=m-y;i++) Ins(n+1,x);for(i=1;i<=y;i++) Ins(To,x);for(i=1;i<=y;i++) Ins(n+1,To);}
I void Solve(int l,int r){
	if(l==r) return;int Mi=l+r>>1,i,j,h,R=Mi+1,y;for(i=l;i<=r;i++) Sep(i,Mi);
	for(i=l;i<=Mi;i++){
		y=m;while(H[i]&&A[i][H[i]]<=Mi) Ins(i,n+1),y--;
		while(y) {while(A[R][H[R]]>Mi) R++;Ins(R,n+1);y--;}
		for(j=Mi+1;j<=r;j++) while(H[j]^m) Ins(i,j);for(j=1;j<=m;j++) Ins(n+1,i);Sep(R,Mi);
	}Solve(l,Mi);Solve(Mi+1,r);
}
int main(){
	freopen("ball3.in","r",stdin);freopen("1.out","w",stdout);
	int i,j,h;scanf("%d%d",&n,&m);for(i=1;i<=n;i++) for(H[i]=m,j=1;j<=m;j++) scanf("%d",&A[i][j]);
	Solve(1,n);printf("%d\n",Ts);for(i=1;i<=Ts;i++)printf("%d %d\n",X[i],Y[i]);
} 

这篇关于luogu P7115 [NOIP2020] 移球游戏的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！