-符拉迪沃斯托克-

分类

算法(1) 赛后补题(4) 题解(26)

/ 注册

全部文章（共31篇）

Cow Contest

给你一堆奶牛间的胜负关系，问有多少头奶牛可以确定排位。确定排位的意思就是某一头奶牛和其余n-1头奶牛都有确定的胜负关系。并且胜负关系具有传递性。所以我们设两个数组来记录胜负关系，然后跑一遍，把所有的胜负关系全部推出来，最后扫一遍即可。附代码： #include<iostream>...

2021-01-23

0 463

Beauty of Trees

有一列未知数字，给出一些描述：区间的异或和为。求哪些描述有误。稀有的带权并查集题。表示从到根的异或值。对于一个区间：如果和在一棵树上，那么就是这个区间的异或值，和给出的值比较即可；如果不在一棵树上，那么结论一定正确，所以合并这两棵树，这个区间的权值就是。附代码： #inclu...

2021-01-23

1 721

Professional Manager

有n棵树，要求支持4种操作：把两棵树所在森林合并；把一颗树从森林中分离出来；问某棵树所属森林的大小；问两棵树是否在同一个森林中。如果没有查询树的大小（操作3）那肯定一个并查集解决。加上这个操作3就麻烦了。我们怎么维护一个森林的大小？暴力必不可能。。。每次合并和删除的时候直接改根节点也会出...

2021-01-22

0 497

虚虚实实

并查集判断连通性没得说。一笔画问题，就是欧拉回路，只要判断度为奇数的点的个数是否为0或2即可。附代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cstring>...

2021-01-22

2 561

任意点

两个点只要x或y坐标相同就可以到达。所以并查集就可以求出来联通块的数量。答案就是附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 110 using names...

2021-01-21

0 479

白色相簿

并查集都不用的吧。。。直接模拟就完了。附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 10010 using namespace std; int n,m,f[M...

2021-01-21

0 554

Call to your teacher

有向图dfs一遍即可。附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 60 #define MAXM 2010 using namespace std; int ...

2021-01-21

0 630

经商

显然先并查集把所有能交往的人搞出来。然后01背包搞一遍就好了。但是复杂度我并不知道这是怎么过的。。。玄学AC 附代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cs...

2021-01-21

1 600

加边的无向图

并查集板子题。答案就是附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 100010 using namespace std; int n,m,fa[MAXN];...

2021-01-20

0 463

奶酪

这个题一看就是并查集的板子题。记得在合并的时候开，不要开根号就行。我当年考的时候是拿跑过去的。。。附代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cstring...

2021-01-20

2 554