首页 > 代码库 > BZOJ1854 [Scoi2010]游戏
BZOJ1854 [Scoi2010]游戏
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。
本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!
Description
lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次?
Input
输入的第一行是一个整数N,表示lxhgww拥有N种装备 接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值
Output
输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。
Sample Input
3
1 2
3 2
4 5
1 2
3 2
4 5
Sample Output
2
HINT
【数据范围】
对于30%的数据,保证N < =1000
对于100%的数据,保证N < =1000000
Source
Day1
正解:并查集
解题报告:
这篇博客写得比较清楚,参考一下吧:http://www.cnblogs.com/BLADEVIL/p/3474189.html
上周考cjl的题目的时候,他出过一道类似的题目,不过这道还有一些改进。
简而言之:读入的两个数之间连边,最后得到的如果是树,可以证明n个点可以选n-1个;如果是图(即有环),那么n个都可以选进去。所以在树的情况,肯定是编号最大的那个不选。
那么我们用并查集维护点与点之间的连通性,可以发现如果两个点已经处在一个连通块内,说明构成了环,那么这个并查集的最大编号也可以选进来(如果之前已经有环,那不用管,如果之前是树,那么之前选不了的那个点刚好可以选进来了);否则,就是两个连通块合并,然后把两个连通块中编号大的那个不选,小的那个选掉。但是这里有一个细节,就是如果编号小的已经选了,那么就可以选了那个大的编号。
1 //It is made by ljh2000 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector> 10 #include <queue> 11 #include <map> 12 #include <set> 13 using namespace std; 14 typedef long long LL; 15 const int MAXN = 10011; 16 int n,father[MAXN]; 17 bool ok[MAXN]; 18 19 inline int getint() 20 { 21 int w=0,q=0; char c=getchar(); 22 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 23 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w; 24 } 25 inline int find(int x){ if(father[x]!=x) father[x]=find(father[x]); return father[x]; } 26 inline void work(){ 27 n=getint(); for(int i=1;i<=10001;i++) father[i]=i; int x,y,r1,r2; 28 for(int i=1;i<=n;i++) { 29 x=getint(); y=getint(); r1=find(x); r2=find(y); 30 if(r1==r2) ok[r1]=true; 31 else{ 32 if(r1>r2) swap(r1,r2); 33 if(!ok[r1]) ok[r1]=true; else ok[r2]=true; 34 father[r1]=r2; 35 } 36 } 37 for(int i=1;i<=10001;i++) if(!ok[i]) { printf("%d",i-1); return ; } 38 printf("10000"); 39 } 40 41 int main() 42 { 43 work(); 44 return 0; 45 }
BZOJ1854 [Scoi2010]游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。