【Nowcoder】2020牛客暑期多校训练营(第八场)I – Interesting Computer Game | 并查集、思维、离散化

题目链接:https://ac.nowcoder.com/acm/contest/5673/I

题目大意:

从1~n给出n组数据,每次可以选择a 或者选择b,选了之后不能在选,问最多选多少个?

题目思路:

和之前总结的一道题很像:https://blog.csdn.net/qq_43857314/article/details/107253264

注意到关联性,所以不可以贪心的去搞

考虑并查集

当一些点连同时

1.如果当前存在n-1条边,也就是是一棵树,你总可以使得有n-1个点被选

update:

引出:对于一棵树,你总可以使得一个点不被选,其他点都被选

简单证明一下,对于每条边而言,树内是无向边,但是操作时可以将他看为有向边,比如a-b,如果这组数据选择a,那么a<-b

也就是说此时a的入度+1,而我们的目标是除了一个点外其余的入度都是1

因为图联通,所以我们总可以找到一个点入度为0,使得从该点出发的一个拓扑序

所以得证:对于一棵树,可以随意剩下一个点不被选

2.如果大于n-1条边,根据上述的红字,那么哪个边多出来,这个边连接的一个点就作为入度为0的点,然后用这多余的边去补上入度为0的点的入度。

因为可以不选,所以就结束了~

注意到数据范围,所以离散化一下即可

Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include <string.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int Maxn=1e6+10;
const int maxn =1e6+10;
const int mod= 998244353;
const int Mod = 1e6+7;
const int S = 1000;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
int pre[maxn];
struct node{
int x,y;
}q[maxn];
ll sz[maxn],ed[maxn];
int vis[maxn];
vector<int>v;
int Find(int x){
return pre[x] == x?x:pre[x] = Find(pre[x]);
}
int getid(ll x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int main()
{
int cas = 0;
int T;scanf("%d",&T);
while(T--){
read(n);
v.clear();
for(int i=1;i<=n;i++){
scanf("%d%d",&q[i].x,&q[i].y);
v.push_back(q[i].x);
v.push_back(q[i].y);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int szt = v.size();
/// debug(szt);
printf("Case #%d: ",++cas);
for(int i=1;i<=szt;i++) pre[i] = i,sz[i] = 1,ed[i] = 0,vis[i] = 0;

for(int i=1;i<=n;i++){
int x = getid(q[i].x),y = getid(q[i].y);
int dx = Find(x),dy = Find(y);
if(dx != dy){
pre[dx] = dy;
sz[dy] += sz[dx];
ed[dy] += ed[dx]+1;
}
else ed[dx]++;
}
ll ans = 0;
for(int i=1;i<=szt;i++){
int di = Find(i);
if(!vis[di]){
vis[di] = 1;
if(ed[di]>=sz[di]) ans+=sz[di];
else ans+=sz[di]-1;
}
}
printf("%lld\n",ans);
}
return 0;
}

 

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【Nowcoder】2020牛客暑期多校训练营(第八场)I - Interesting Computer Game | 并查集、思维、离散化

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【Nowcoder】2020牛客暑期多校训练营(第八场)I – Interesting Computer Game | 并查集、思维、离散化
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏