题解 : Fabled Rooks

1.题意

We would like to place n rooks, 1 ≤ n ≤ 5000, on a n × n board subject to the following restrictions • The i-th rook can only be placed within the rectangle given by its left-upper corner (xl , yl) and its rightlower corner (xr , yr), where 1 ≤ i ≤ n, 1 ≤ xl ≤ xr ≤ n , 1 ≤ yl ≤ yr ≤ n. • No two rooks can attack each other, that is no two rooks can occupy the same column or the same row.

大概意思是，把n个棋子放在一个n*n的棋盘里，求任意一种方案。每个棋子有一个题目给出的位置区间xl,yl,xr,yr

2.思路

很显然，对于每一个棋子行和列的决策互不干扰，对于行或列，只要没有任意两个或以上棋子在同一行/列，方案合法，所以我们可以对于每一个棋子分别计算行和列的位置。

目前目前看到了三种方法：

假设我们现在在处理每个棋子的行位置

1.以每个棋子的限制区间的右端点从小到大排序，显然右端点越小越应该先给它分位置。然后放在这个棋子限制区间地最靠左的空位上。时间复杂度是o(n^2)，索性这个题n最大只有5000，我开始时想到使用类似 lowbit 函数的方法把每个位置的使用情况放在bitset里面这样查询某个棋子限制区间地最靠左的空位的时候就会变成o(1)，但是仔细想想这个过程仍然是o(n)的。
2.考虑把每个位置分配给每个区间，先把所有的限制区间按照右端点从小到大排序，然后从左到右遍历每个位置，将区间按顺序放进堆里，堆按照每个区间的左端点排序，一旦有区间的左端点<=当前位置，就把当前位置分配给该区间。对于这种方法的正确性其实和第一种方法差不多。在一定意义上可以算是对第一种方法的优化。时间复杂度o(nlogn)，十分优秀
3.网络流

当然还是有一些细节需要处理的，比如说把算的时候要记录每个点的序号，不然排序以后就乱了。最后输出答案以前记得按序号排回去

3.代码：

提供第一种方法的代码，因为懒

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1e5+7;
template <typename _TP>
inline void qread(_TP &X){
    char ch=0;int w;X=0;
    while(!isdigit(ch)){w=ch=='-';ch=getchar();}
    while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
    X=w?-X:X; 
}
int vis[MAXN];
struct node{
    int num,l,r;
}ax[MAXN],ay[MAXN];
struct ansNode{
    int num,val;
}ansx[MAXN],ansy[MAXN];
inline bool cmpAns(const ansNode &a,const ansNode &b){
    return a.num<b.num;
}
inline bool cmp(const node &a,const node &b){
    return a.r<b.r;
} 
inline void INIT(){
    memset(vis,0,sizeof(vis));
}
void solve(const int n){
    INIT();
    int xl,yl,xr,yr;
    for(int i=1;i<=n;i++){
        qread(xl);qread(yl);qread(xr);qread(yr);
        ax[i]=(node){i,xl,xr};
        ay[i]=(node){i,yl,yr};
    }
    sort(ax+1,ax+n+1,cmp);
    for(int i=1;i<=n;i++){
        ansx[i].num=ax[i].num;
        int flag=0;
        for(int j=ax[i].l;j<=ax[i].r;j++){
            if(!vis[j]){
                vis[j]=1;
                ansx[i].val=j;
                flag=1;
                break;
            }
        }
        if(!flag){
            cout<<"IMPOSSIBLE\n";
            return ;
        }
    }
    sort(ay+1,ay+n+1,cmp);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        ansy[i].num=ay[i].num;
        int flag=0;
        for(int j=ay[i].l;j<=ay[i].r;j++){
            if(!vis[j]){
                vis[j]=1;
                ansy[i].val=j;
                flag=1;
                break;
            }
        }
        if(!flag){
            cout<<"IMPOSSIBLE\n";
            return ;
        }
    }
    sort(ansx+1,ansx+n+1,cmpAns);
    sort(ansy+1,ansy+n+1,cmpAns);
    for(int i=1;i<=n;i++){
        cout<<ansx[i].val<<' '<<ansy[i].val<<'\n';
    }
}
int main(){
    int t;
    while(true){
        qread(t);
        if(!t)break;
        solve(t);
    }
    return 0;
}

题解:Fabled Rooks

题解 : Fabled Rooks

1.题意

2.思路

3.代码：