正文 

当前位置： 首页 > java > java教程

2017"百度之星"程序设计大赛-初赛（a）数据分割

Blue233333 Blue233333     2022-09-14     616

关键词：

n<=100000条相等/不等关系描述<=100000个数，把这些数据分割成若干段使得每一段描述都出现冲突且冲突只出现在最后一行。

相等关系具有传递性，并查集维护；不等关系根据相等关系进行合并，采用平衡树的启发式合并。

每次遇到相等关系x，y，先找到x，y对应并查集的根p，q，判是否p在q的不等关系中，若否说明成立，这时应合并并查集，并合并两棵平衡树，小的合到大的上。

每次遇到不等关系x，y，先找到x，y对应并查集的根p，q，判是否p和q在同一个并查集中，若否说明成立，这时应把p和q分别添加到对方的平衡树中。

平衡树调用set即可。

技术分享 
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<algorithm>
 6 #include<set>
 7 //#include<iostream>
 8 using namespace std;
 9 
10 int T,n=200001;
11 #define maxn 200011
12 set<int> s[maxn];
13 int cnt,vis[maxn],sta[maxn],top;
14 struct UFS
15 {
16     int fa[maxn];
17     UFS() {for (int i=1;i<=n;i++) fa[i]=i;}
18     int find(int x) {return x==fa[x]?x:(fa[x]=find(fa[x]));}
19     void Union(int &x,int &y)
20     {
21         x=find(x),y=find(y);
22         if (x!=y) fa[x]=y;
23     }
24 }ufs;
25 int x,y,id;
26 int ans[maxn],lans=0,Case;
27 void clear()
28 {
29     while (top)
30     {
31         int now=sta[top--];
32         ufs.fa[now]=now;
33         s[now].clear();
34     }
35     ans[cnt++]=Case;
36 }
37 int main()
38 {
39     scanf("%d",&T);
40     memset(vis,0,sizeof(vis));
41     top=0;cnt=1;
42     for (Case=1;Case<=T;Case++)
43     {
44         scanf("%d%d%d",&x,&y,&id);
45         if (vis[x]!=cnt) vis[x]=cnt,sta[++top]=x;
46         if (vis[y]!=cnt) vis[y]=cnt,sta[++top]=y;
47         x=ufs.find(x),y=ufs.find(y);
48         if (s[x].size()>s[y].size()) {int t=x;x=y;y=t;}
49         if (id)
50         {
51             if (s[x].find(y)!=s[x].end())
52             {
53                 clear();
54                 continue;
55             }
56             ufs.Union(x,y);
57             for (set<int>::iterator i=s[x].begin();i!=s[x].end();i++)
58             {
59                 int now=*i;now=ufs.find(now);
60                 s[now].erase(x);
61                 s[y].insert(now);
62                 s[now].insert(y);
63             }
64             s[x].clear();
65         }
66         else
67         {
68             if (x==y)
69             {
70                 clear();
71                 continue;
72             }
73             s[x].insert(y);
74             s[y].insert(x);
75         }
76     }
77     printf("%d
",cnt-1);
78     for (int i=1;i<cnt;i++) printf("%d
",ans[i]-ans[i-1]);
79     return 0;
80 }
View Code

 

2017"百度之星"程序设计大赛-资格赛-度度熊与邪恶大魔王（dp+后缀最小值）

度度熊与邪恶大魔王思路：由于防御和血量的范围很小，所以暴力枚举出对于每种防御造成的每种伤害所需的最小花费，最后只需在伤害大于等于血量的情况下再找到最小花费（这个只需要后缀最小值预处理一下就可以了）状态... 查看详情

2017"百度之星"程序设计大赛-资格赛1003

2017"百度之星"程序设计大赛-资格赛1003  dp，类似背包#include<bits/stdc++.h>usingnamespacestd;#pragmacomment(linker,"/STACK:102400000,102400000")#definerep(i,a,b)for(inti=a;i<=b;++i)#defineper(i,b,a)fo 查看详情

2017"百度之星"程序设计大赛-资格赛寻找母串

ProblemDescription对于一个串S，当它同时满足如下条件时，它就是一个01偏串：1、只由0和1两种符组成；2、在S的每一个前缀中，0的个数不超过1的个数；3、S中0的个数和1的个数相等。现在给定01偏串S，请计算一下S在所有长度为n的01... 查看详情

2017"百度之星"程序设计大赛-初赛（b）小小粉丝度度熊

ProblemDescription度度熊喜欢着喵哈哈村的大明星——星星小姐。为什么度度熊会喜欢星星小姐呢？首先星星小姐笑起来非常动人，其次星星小姐唱歌也非常好听。但这都不是最重要的，最重要的是，星星小姐拍的一手好代码！于是... 查看详情

2017"百度之星"程序设计大赛-初赛（a）01，05，06

 小C的倍数问题   TimeLimit:2000/1000MS(Java/Others)  MemoryLimit:32768/32768K(Java/Others)ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一... 查看详情

hdu6122今夕何夕数学公式（2017"百度之星"程序设计大赛-初赛（a））

今夕何夕TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1295    AcceptedSubmission(s):455ProblemDescription今天是2017年8月6 查看详情

hdu6114chess组合数（2017"百度之星"程序设计大赛-初赛（b））

ChessTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):513    AcceptedSubmission(s):319ProblemDescription車是中国象棋中的一种棋 查看详情

2017"百度之星"程序设计大赛-初赛（a）

小C的倍数问题ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。现在给定进制P，求有多少个B满足P... 查看详情

hdu6109数据分割并查集（2017"百度之星"程序设计大赛-初赛（a））

  数据分割TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1119    AcceptedSubmission(s):268ProblemDescriptio 查看详情

2017"百度之星"程序设计大赛-初赛（a）数据分割

n<=100000条相等/不等关系描述<=100000个数，把这些数据分割成若干段使得每一段描述都出现冲突且冲突只出现在最后一行。相等关系具有传递性，并查集维护；不等关系根据相等关系进行合并，采用平衡树的启发式合并。每次... 查看详情

hdu6113度度熊的01世界dfs（2017"百度之星"程序设计大赛-初赛（a））

 度度熊的01世界TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1117    AcceptedSubmission(s):400ProblemDescription度 查看详情

hdu6108小c的倍数问题数学（2017"百度之星"程序设计大赛-初赛（a））

小C的倍数问题TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):481    AcceptedSubmission(s):278ProblemDescription根据小学数学的知识 查看详情

2017"百度之星"程序设计大赛-复赛1005&&hdu6148valleynumer数位dp

ValleyNumerTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):311    AcceptedSubmission(s):165ProblemDescription众所周知， 查看详情

hdu6119小小粉丝度度熊预处理+尺取法（2017"百度之星"程序设计大赛-初赛（b））

小小粉丝度度熊TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):1572    AcceptedSubmission(s):513ProblemDescription度度熊喜欢着喵哈 查看详情

2017"百度之星"程序设计大赛-初赛（a）小c的倍数问题

ProblemDescription根据小学数学的知识，我们知道一个正整数x是3的倍数的条件是x每一位加起来的和是3的倍数。反之，如果一个数每一位加起来是3的倍数，则这个数肯定是3的倍数。现在给定进制P，求有多少个B满足P进制下，一个正... 查看详情

2017"百度之星"程序设计大赛-资格赛度度熊的王国战略

度度熊的王国战略度度熊国王率领着喵哈哈族的勇士，准备进攻哗啦啦族。哗啦啦族是一个强悍的民族，里面有充满智慧的谋士，拥有无穷力量的战士。所以这一场战争，将会十分艰难。为了更好的进攻哗啦啦族，度度熊决定首... 查看详情

2017"百度之星"程序设计大赛-初赛（b）度度熊的交易计划

n个村庄m条带权路，权值为花费，村庄可以造东西卖东西，造完东西可以换地方卖，给出每个村庄造东西花费a和最多个数b、卖东西价值c和最多个数d，求最大收益。裸的费用流。然而还WA了一发。很好。建源向每个村庄连边(b,a)... 查看详情

2017"百度之星"程序设计大赛-复赛1003&&hdu6146pokémongo数学，递推，dp

PokémonGOTimeLimit:3000/1500MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):171    AcceptedSubmission(s):104ProblemDescription 查看详情