自动搬运

查看原文

来自洛谷，原作者为

	nullqtr_pwp 我注意到有些人一直在做各种地方的cnoi题，但是并没有什么b用，可能是因为一直在舒适区里面舒服的卷，虐杀自己擅长的东西并获得成就感。

搬运于2025-08-24 22:25:10，当前版本为作者最后更新于2024-09-20 20:50:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

笔者正在准备中考，同时被一些高中物理卷子污染了，所以《运动与力》含量较高，但是极不标准。

注意到 $q$ 很小，每次都可以暴力扫与之前存活矩形的情况，操作一二三直接模拟即可。move 操作难点在于读懂。我们这样考虑：给予初始矩形在某个方向的动能。我们要模拟的是转化为机械能的距离。

在运动的部分一定是初始矩形向右黏上的一堆矩形，它们构成了连通块，第一次碰撞时只要在另一个维度上的坐标区间有交集就会黏上。

考虑暴力维护每一次碰撞，维护当前剩余动能。我们希望求出在一次碰撞内可以释放的动能 $nxt$。初始 $nxt$ 等于剩余动能的最大值。对于当前连通块中已有的矩形，对 $nxt$ 的更新就是在该运动方向上到达边界的距离，$nxt$ 要对此取 $\min$。

那么先将这些连通块中的所有矩形移动 $nxt$，可以黏上的就是在该运动方向上坐标相邻的，但是黏上一个新的之后可能又会由这个新的黏上更多相邻的。具体考虑黏上就是在另一个维度上的坐标区间有交集。这是一个图论问题，$u\to v$ 表示 $u$ 进入连通块后会把 $v$ 黏上，这是一个 dag，直接跑一遍拓扑排序就可以得出新加上的点。

如果没有新黏上的点，就终止过程，因为动能释放不出去了。否则继续这个循环。

由于最多 $256$ 次操作，所以这样的过程时间是可以接受的。

// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
using namespace std;
ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=500005;
int tot,n;
int xmx,ymx,nowtim;
struct node{
	int x,y,l,r,del=0;
	bool bound(){ return x>=0&&x+l-1<=xmx-1&&y>=0&&y+r-1<=ymx-1; }
	bool check(int p,int q){ return x<=p&&p<x+l&&y<=q&&q<y+r; }
};
inline bool chkx(node a,node b){ return max(a.x,b.x)<min(a.x+a.l,b.x+b.l); }
inline bool chky(node a,node b){ return max(a.y,b.y)<min(a.y+a.r,b.y+b.r); }
inline bool chk(node a,node b){ return (chkx(a,b)&&chky(a,b)); }
node a[305];
set<int>surv;
int find(int x,int y){
	for(int id:surv)if(a[id].check(x,y))return id;
	return -1;
}
void Open(){
	int x=read(),y=read(),l=read(),r=read();
	node tmp={x,y,l,r,0};
	for(int id:surv)if(chk(tmp,a[id]))return printf("Command %d: OPEN - window does not fit\n",nowtim),void();
	if(!tmp.bound())return printf("Command %d: OPEN - window does not fit\n",nowtim),void();
	a[++tot]=tmp;
	surv.insert(tot);
}
void Resize(){
	int x=read(),y=read(),l=read(),r=read(),qwq=find(x,y);
	if(qwq<0)return printf("Command %d: RESIZE - no window at given position\n",nowtim),void();
	node nxt={a[qwq].x,a[qwq].y,l,r};
	if(!nxt.bound())return printf("Command %d: RESIZE - window does not fit\n",nowtim),void();
	for(int id:surv)if(id!=qwq&&chk(nxt,a[id]))return printf("Command %d: RESIZE - window does not fit\n",nowtim),void();
	a[qwq]=nxt;
}
void Close(){
	int x=read(),y=read(),qwq=find(x,y);
	if(qwq<0)return printf("Command %d: CLOSE - no window at given position\n",nowtim),void();
	surv.erase(qwq),a[qwq].del=1;
}
void Output(){
	printf("%d window(s):\n",(int)surv.size());
	for(int i:surv)printf("%d %d %d %d\n",a[i].x,a[i].y,a[i].l,a[i].r);
}
int ins[305],q[505];
void Move(){
	int x=read(),y=read(),dx=read(),dy=read(),qwq=find(x,y);
	if(qwq<0)return printf("Command %d: MOVE - no window at given position\n",nowtim),void();
	x=dx,y=dy,memset(ins,0,sizeof ins),ins[qwq]=1;
	for(;;){
		if(!x&&!y)break;
		int nxt=abs(x^y);
		for(int i:surv)if(ins[i]){
			if(x<0)chkmin(nxt,abs(a[i].x));
			if(x>0)chkmin(nxt,abs(xmx-1-(a[i].x+a[i].l-1)));
			if(y<0)chkmin(nxt,abs(a[i].y));
			if(y>0)chkmin(nxt,abs(ymx-1-(a[i].y+a[i].r-1)));
		}
		for(int i:surv)if(ins[i])for(int j:surv)if(!ins[j]){
			if(x>0&&chky(a[i],a[j])&&a[j].x>(a[i].x+a[i].l-1))chkmin(nxt,abs(a[j].x-(a[i].x+a[i].l-1)-1));
			if(x<0&&chky(a[i],a[j])&&(a[j].x+a[j].l-1)<a[i].x)chkmin(nxt,abs(a[i].x-(a[j].x+a[j].l-1)-1));
			if(y>0&&chkx(a[i],a[j])&&a[j].y>(a[i].y+a[i].r-1))chkmin(nxt,abs(a[j].y-(a[i].y+a[i].r-1)-1));
			if(y<0&&chkx(a[i],a[j])&&(a[j].y+a[j].r-1)<a[i].y)chkmin(nxt,abs(a[i].y-(a[j].y+a[j].r-1)-1));
		}
		if(x<0){
			for(int i:surv)if(ins[i])a[i].x-=nxt;
		}
		if(x>0){
			for(int i:surv)if(ins[i])a[i].x+=nxt;
		}
		if(y<0){
			for(int i:surv)if(ins[i])a[i].y-=nxt;
		}
		if(y>0){
			for(int i:surv)if(ins[i])a[i].y+=nxt;
		}
		int flag=0,qL=1,qR=0;
		for(int i:surv)if(ins[i])q[++qR]=i;
		while(qL<=qR){
			const int u=q[qL++];
			for(int v:surv)if(!ins[v]){
				if(x>0&&chky(a[u],a[v])&&a[u].x+a[u].l==a[v].x)ins[v]=1,q[++qR]=v,flag=1;
				if(x<0&&chky(a[u],a[v])&&a[v].x+a[v].l==a[u].x)ins[v]=1,q[++qR]=v,flag=1;
				if(y>0&&chkx(a[u],a[v])&&a[u].y+a[u].r==a[v].y)ins[v]=1,q[++qR]=v,flag=1;
				if(y<0&&chkx(a[u],a[v])&&a[v].y+a[v].r==a[u].y)ins[v]=1,q[++qR]=v,flag=1;
			}
		}
		if(x>0)x-=nxt;
		if(x<0)x+=nxt;
		if(y>0)y-=nxt;
		if(y<0)y+=nxt;
		if(!flag)break;
	}
    if(!x&&!y)return;
	printf("Command %d: MOVE - moved %d instead of %d\n",nowtim,abs(dx+dy-x-y),abs(dx+dy));
}
void solve(){
	xmx=read(),ymx=read();
	string op;
	while(cin>>op){
		++nowtim;
		if(op=="OPEN")Open();
		if(op=="RESIZE")Resize();
		if(op=="CLOSE")Close();
		if(op=="MOVE")Move();
	}
	Output();
}
signed main(){
	const int zsy=1;
	F(____,1,zsy)solve();
}