专栏文章

Atcoder Beginner Contest 391 赛记（4 / 7）

xxy_mc
个人记录参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqcw21v
此快照首次捕获于
2025/12/04 02:44
3 个月前
此快照最后确认于
2025/12/04 02:44
3 个月前
查看原文

题面

这次 DD 还挺简单的（逃。

C - Pigeonhole Query 讲解：

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

带权并查集做法：

很简单，这种做法唯一的难点就是合并了，但也很容易理解，只需另开一个数组来存鸽舍里的鸽子数量，然后每次合并的时候进行维护就行了。
但是这种做法具有局限性，当编号为 PP 的鸽子存在的鸽舍里鸽子的数量不为 11 时，合并时就会把 PP 号鸽子在的鸽舍里所有的鸽子全转移到 HH 号鸽舍里了，与题里只让转移 PP 号鸽子的题意不符，故错。
这时候就有同学要问了：煮啵煮啵，这个题我就是想用并查集的方法做，有没有更简单强势且不会错的做法呢？
可能有，我们改天再讲。

正解：

我们继续沿用存鸽子数量的数组，但是原来用来找爸爸的数组换一个作用：用来存鸽舍编号。
这样一来，我们就可以直接进行维护，舍去了 find 函数。

code:

CPP
#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。是时候提升一下英文水平了。

正解：

这个过程很像消消乐，行数太大，高达 10000000001000000000，肯定不能直接模拟。
小方格存储：
我们可以使用 vector，存下每一列的方块，方便后续处理。
情况 11：
高度最小的那一列一定是可以被全部消除的，如图：
则大于最小高度的方块不能被消除，故存在。
情况 22：
先甩出结论：d[r[A]-1]>T-1，其中 d[i] 是所有列第 ii 层（从底部开始）的最大初始行数，r[i] 是第 ii 个方块在其列中的位置（从 11 开始）。
  • d 数组维护：
    • 这里提到了最大初始行数，那么我们就要知道初始行数，初始行数就等于行数减 11，因为初始行数为第 ii 个方块的行数到底层的距离，则为中间的楼层数，如：当行数为 22 时，它与底层仅隔 11 层楼。初始行数使用 c 数组存储。
    • 如何获得最大值呢？要遍历 00 到最小初始高度，因为只有这个区间才能被消除。然后遍历每一列，求最大值就行了，如：`
    CPP
    rep(i,0,minn-1){
    rep(j,1,w){
        d[i]=max(d[i],c[v[j][i]]);
    }
}
  • r 数组维护：
    • 我们只需要实时获取第 XX 列的高度就行了，如：
    CPP
    cin>>x>>y;
v[x].push_back(i);
r[i]=v[x].size();
  • 那为什么 d[r[A]-1]>T-1 成立则为存在呢？
    • 这表示该层中所有列的最大初始行数大于 T−1T-1。
    • 即使经过 TT 次移除操作，该层中的方块初始行数仍然足够大，不会被移除到最底层。
    因此，这些方块会继续存在。

code:

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...