题解：P7677 [COCI2013-2014#5] LADICE

JoeZYQ · 2024-05-02 23:36:13 · 题解

先看题

题目思路

我们设 vis_i 表示第 i 个抽屉有没有放置物品，以此来判断能放置下第 i 个物品的抽屉 a_i 和 b_i 是否为空。

如果这个物品的一个抽屉 a_i 已经放置了另一个物品，就占据这个物品的另一个抽屉 b_i，然后抽屉 b_i 中如果原本有物品，那就查询这个物品的 a_i 与 b_i 抽屉，直到找到一个抽屉为空时，并查集便可以优化这一过程。

如果都没有抽屉可以存放物品，就只能将这个物品丢弃。

如果还没看懂，以下是代码的具体实现

#include<iostream>
using namespace std;
int n,l;
const int N=3e5+5;
int vis[N],fa[N];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void un(int x,int y){
    x=find(x),y=find(y);
    if(x!=y)
        fa[y]=x;
}//并查集基本操作 
int main(){
    cin>>n>>l;
    for(int i=1;i<=l;i++)fa[i]=i;//初始化 
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        if(vis[find(x)]==0||vis[find(y)]==0) {//放得下 
            cout<<"LADICA\n";
            if(vis[find(x)]==0){//可以执行条件1/3 
                vis[find(x)]=1;//标记 
                un(y,x);
            }
            else{//可以执行条件2/4 
                vis[find(y)]=1;//标记 
                un(x,y);
            }
        } 
        else cout<<"SMECE\n";//放不下 
    }
    return 0; 
}