Atcoder Beginner Contest 391 赛记（4 / 7）

xy_mc · 2025-02-02 15:07:49 · 个人记录

题面

这次 D 还挺简单的（逃。

C - Pigeonhole Query 讲解：

看完这道题的第一时间，本蒟蒻首先想到的就是用带权并查集写，可是写着写着出现了问题……

带权并查集做法：

很简单，这种做法唯一的难点就是合并了，但也很容易理解，只需另开一个数组来存鸽舍里的鸽子数量，然后每次合并的时候进行维护就行了。

但是这种做法具有局限性，当编号为 P 的鸽子存在的鸽舍里鸽子的数量不为 1 时，合并时就会把 P 号鸽子在的鸽舍里所有的鸽子全转移到 H 号鸽舍里了，与题里只让转移 P 号鸽子的题意不符，故错。

这时候就有同学要问了：煮啵煮啵，这个题我就是想用并查集的方法做，有没有更简单强势且不会错的做法呢？

可能有，我们改天再讲。

正解：

我们继续沿用存鸽子数量的数组，但是原来用来找爸爸的数组换一个作用：用来存鸽舍编号。

这样一来，我们就可以直接进行维护，舍去了 find 函数。

code:

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i)
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
using namespace std;
const int N=1e6+5;
int n,T,opt,p,h,f[N],l[N],sum;
inl void merge(int x,int y){
    int fx=f[x];
    if(fx!=y){
        if(l[fx]>1) sum--;
        l[fx]--;
        if(l[fx]>1) sum++;
        if(l[y]>1) sum--;
        l[y]++;
        if(l[y]>1) sum++;
        f[x]=y;
    }
}
signed main(){
    fst;
    cin>>n>>T;
    rep(i,1,n) f[i]=i,l[i]=1;
    while(T--){
        cin>>opt;
        if(opt==1){
            cin>>p>>h;
            merge(p,h);
        }else if(opt==2){
            cout<<sum<<"\n";
        }
    }
    return 0;
}

本蒟蒻觉得这道题用并查集应该能解出来，求 dalao 赐教，orz。

~~看了讨论发现自己想复杂了 QWQ。~~

D - Gravity 讲解

这个题本蒟蒻卡了好长时间，建议评黑黄。

全是翻译的事，大半天没读懂题 QWQ。是时候提升一下英文水平了。

正解：

~~这个过程很像消消乐~~，行数太大，高达 1000000000，肯定不能直接模拟。

小方格存储：

我们可以使用 vector，存下每一列的方块，方便后续处理。

情况 1：

高度最小的那一列一定是可以被全部消除的，如图：

则大于最小高度的方块不能被消除，故存在。

情况 2：

先甩出结论：d[r[A]-1]>T-1，其中 d[i] 是所有列第 i 层（从底部开始）的最大初始行数，r[i] 是第 i 个方块在其列中的位置（从 1 开始）。

d 数组维护：
- 这里提到了最大初始行数，那么我们就要知道初始行数，初始行数就等于行数减 1，因为初始行数为第 i 个方块的行数到底层的距离，则为中间的楼层数，如：当行数为 2 时，它与底层仅隔 1 层楼。初始行数使用 c 数组存储。
- 如何获得最大值呢？要遍历 0 到最小初始高度，因为只有这个区间才能被消除。然后遍历每一列，求最大值就行了，如：`
```
rep(i,0,minn-1){
rep(j,1,w){
    d[i]=max(d[i],c[v[j][i]]);
}
}
```
r 数组维护：
- 我们只需要实时获取第 X 列的高度就行了，如：
```
cin>>x>>y;
v[x].push_back(i);
r[i]=v[x].size();
```
那为什么 d[r[A]-1]>T-1 成立则为存在呢？
- 这表示该层中所有列的最大初始行数大于 T-1。
- 即使经过 T 次移除操作，该层中的方块初始行数仍然足够大，不会被移除到最底层。
因此，这些方块会继续存在。

code:

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i)
using namespace std;
const int N=2e5+5;
int n,w,q,x,y,t,a,minn=INT_MAX; 
vector<int> v[N];
int r[N],c[N],d[N];
signed main(){
    fst;
    cin>>n>>w;
    rep(i,1,n){
        cin>>x>>y;
        v[x].push_back(i);
        r[i]=v[x].size();
        c[i]=y-1;
    }
    rep(i,1,w){
        if(minn>=v[i].size()) minn=v[i].size();
    }
    rep(i,0,minn-1){
        rep(j,1,w){
            d[i]=max(d[i],c[v[j][i]]);
        }
    }
    cin>>q;
    while(q--){
        cin>>t>>a;
        if(r[a]>minn) cout<<"Yes\n";
        else if(d[r[a]-1]>t-1) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}