shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

全部文章 / 题解（共11篇）

模拟战役来自专栏

前言: 晚上有点困了,本来是看吉吉是第一个的,然后其实是司机,然后打错一些东西...不过也没很久就搞好了..说明还行. 思路: 本题思路十分简单,就算搜每个连通块大小,然后判断下吉吉的和司机的连通块数量就好了. 代码: 代码有点丑,将就一下~ #include <bits/stdc++.h&g...

并查集贪心

2021-01-12

4 704

pSort 来自专栏

直接并查集即可. #include <bits/stdc++.h> using namespace std; const int N=105; int fa[N],a[N],d[N]; int f(int x) { if(x==fa[x]) return x; else ...

并查集

2020-09-10

0 597

Quantity of Strings 来自专栏

不错的一个并查集的题目= - =应该是套路题吧...把必须相同的归为一类,然后m^t即是答案,因为每一类都有m种选择.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N...

并查集

2020-09-10

0 547

Destroying Array 来自专栏

写代码一定要规范,不然很多玄学错误,你都搞不懂...2333 #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],fa[N],b[N]; long long sum[N]; int f(in...

并查集

2020-09-09

2 571

Love Rescue 来自专栏

#include <bits/stdc++.h> using namespace std; const int N=1e5+5,M=30; char s1[N],s2[N]; int fa[M]; struct vv{ int t,m; }; vector<vv>v;...

并查集

2020-09-07

1 606

Chess Tournament&(判断有向图和无向图是否有环O(N)) 来自专栏

为什么打算重新写一下呢,因为最近一直在做并查集的题.emmm/现在讲两种dfs判断环的方式.对于无向图只需对另一一个点做一次dfs即可,因为任意一个点一定可以都到的. int vis[N]; void dfs(int u,int fa)//判断有没有环. { if(vis[u]) {flag...

并查集

2020-09-06

0 831

Socks 来自专栏

贪心+并查集即可.选取集合众数,然后答案就是集合大小-集合众数了. #include <bits/stdc++.h> using namespace std; const int N=2e5+5; int a[N]; int fa[N]; vector<int>v[N]; i...

并查集

2020-09-05

1 609

食物链来自专栏

建图种类并查集即可 #include <bits/stdc++.h> using namespace std; const int N=5e4+5; int fa[N],d[N]; int ask(int x) { if(fa[x]!=x) { int r...

并查集

2020-07-15

1 666

奇偶游戏来自专栏

各种找矛盾的题..下面用种比较好的算法写吧,不用扩展域,权值并查集.怎么权值查并集呢?首先和上个题目一样,用一个d[x]表示x到根节点的距离.假如距离为偶数就表示同一面.奇数就表示对立面. #include <bits/stdc++.h> using namespace std; con...

并查集

2020-07-15

1 1086

银河英雄传说来自专栏

又是查并集..没啥好说的...qaq大概是查并集+、差分思想吧?d[x]表示我x点到root的距离,然后sz[x]表示x集合的大小.显然root到root的距离为0.我们考虑两个集合合并,显然,我们第一个集合的d[root]设为sz[2].sz[2]的大小又要+sz[1].然后我们第二次查询时,就是...

并查集

2020-07-14

1 626