题解：P7677 LADICE

· · 题解

题目大意

对于每个物品 s_i 有两个归宿 A_i 和 B_i，且 A_i 优先级比 B_i 高，按 1 \sim n 的顺序放入物品 i，如果该位置有其他物品 j，给后面的物品 i 让位。如果让不了，将这个物品 i 丢了。

思路

从【样例解释 #2】中看出：这是一种类似于链一样的后退，考虑暴力的话，其实相当于把这个物品放到最后，但意义上是 A_i 或 B_i，这样就可以减少时间。

对于整体来看，所有物品可以组成若干条链，取决于每个 s_i 所指向的归宿 A_i 或 B_i，同时有些链可以合并为一条链。

而这一条条链只需要考虑到最后一位是否能放，即通过前面的物品来追根溯源，那我们可以想到用前面的物品来指向后面的物品，乃至指向最后，那这和并查集有异了。

算法出现：并查集。

并查集和上面说的思路其实相反，先存根而不是存末尾的东西，那我们可以将它反过来看：如果 A_i 所在的根 x 是空的，那标记 x 为 1 即满了，那满了怎么办？我们还有 B_i 呢！求出 B_i 所在的根，链接起来，这样就又有了新的空位。同时我们还要将 A_i 和 B_i 连接起来，组成一条新的“链”。

学废了吗

没有那只能残忍上代码了。

:::success[AC CODE]

//鬼嘲深渊的猩红主宰，戏谑命运的无相之王
const LL N=1e6+6;
LL T,n,m,q,k,ans,f[N];//物品的父结点
LL find(LL x){the f[x]!=x?f[x]=find(f[x]):x;}
void unite(LL x,LL y){if(x-y) f[x]=y;}
bool ff[N];
int main(){ cin.tie(0)->sync_with_stdio(0);cout.tie(0);
    cin>>n>>m;
    lop(i,1,m,1) f[i]=i;//维护自己
    while(n--){
        LL x,y;
        cin>>x>>y;
        x=find(x); y=find(y);//追根溯源
        if(ff[x] && ff[y]){ //如果都不能放
            cout<<"SMECE\n"; continue;
        } 
        cout<<"LADICA\n";
        if(ff[y]) ff[x]=1,unite(x,y);
        // A_i 能放, 将 A_i 链接于 B_i 的根,下次查到 B_i 根上
        else ff[y]=1,unite(y,x);
    } 
    return 0;
}

:::

写在最后

都看到这了，点个赞吧！我多么希望这篇题解是我第二篇赞破百的题解啊！