题解：P6916 [ICPC2015 WF] Window Manager

nullqtr_pwp · 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();
}