【题解】CF356A Knight Tournament
2024-10-21 07:47:00
题面传送门
本蒟蒻想练习一下并查集,所以是找并查集标签来这里的。写题解加深理解。
解决思路
自然,看到区间修改之类很容易想到线段树,但本蒟蒻线段树会写挂,所以这里就讲比较简单的并查集思路。
并查集的核心是 \(\text{find}\) 函数。\(\text{find}\) 函数的目的是找到一个节点的父亲,本题中用于快速地找到下一个点搜谁。不带权的 \(\text{find}\) 很好理解也很好写。如果父亲是本身,直接返回即可。否则去找父亲的父亲,并更新。一般这样写:
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
如果你想压行也可以这样:
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
然后是主函数。首先,要把所有节点的父亲赋值为自己。注意,一般要赋到 \(n+1\) 。例如这题,如果只赋到 \(n\) ,那么在找 \(fa_{n+1}\) 时会进入死循环。
接着,对于每一个输入的 \(l,r,x\) ,如果从 \(l\) 到 \(r\) 遍历显然会超时。这时候并查集就发挥作用了。我们可以让 \(j\) 从 \(\text{find(l)}\) 开始,每次都跳到 \(\text{find(j+1)}\),这样可以避免反复扫到已经失败的骑士。之后,在这一范围里,如果 \(j\) \(\ne\) \(x\)(因为不会打败自己),就将 \(ans_j\) 设为 \(x\) 。再修改 \(fa_j\)。若 \(j<x\) 则可将 \(fa_j\) 设为 \(x\),否则就设为 \(r+1\)。这里可以根据 \(fa\) 数组的意义自己理解一下。
最后,只要愉快地输出 \(ans\) 数组就可以了。
注意:数据范围是 \(3\times10^5\),数组开小了会 RE (qwq)。
AC Code
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[300005],ans[300005],l,r,x;
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n+1;i++) fa[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&l,&r,&x);
for(int j=find(l);j<=r;j=find(j+1)){
if(j!=x){
if(j<x) fa[j]=x;
else fa[j]=r+1;
ans[j]=x;
}
}
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
最新文章
- 手动获取酷我Mp3外链
- web-app1--移动端等比例代码
- 69 Spring Interview Questions and Answers – The ULTIMATE List--reference
- Ubuntu---2
- GCC警告提示错误“cc1:all warnings being treated as errors”
- SVN和Maven及Jenkins(转)
- ubuntu安装openssh-server
- myeclipse 8.6 插件安装之SVN
- border-radius是向元素添加圆角边框的方法
- 【Netty】Netty核心组件介绍
- R读取excel文件乱码 read.xlsx() 解决方法
- Confluence DotNet API发布
- 海量数据挖掘MMDS week2: 频繁项集挖掘 Apriori算法的改进:非hash方法
- 老毛桃pe安装系统
- (办公)面试java设计模式
- docker 进阶
- java框架之Spring(1)-入门
- 20190313 org.apache.commons.lang3.builder.EqualsBuilder的两种典型用法
- day 018 面向对象--约束和异常处理
- GetWindowRect