白给怪

分类

未归档(2) 题解(21)

/ 注册

全部文章（共23篇）

道路建设（kruskal算法）

题目链接：https://ac.nowcoder.com/acm/problem/15108显然这是一道最小生成树的题其中利用的是 kruskal算法kruskal 算法思想：贪心选取最短的边来组成一棵最小的生成树。具体做法：先将所有的边做排序，然后利用并查集作判断来优先选择较小的边，直到建成一...

kruskal

2020-07-07

8 952

Treasure Island

题目链接：https://codeforces.com/problemset/problem/1214/D 分析：首先很明显答案在0，1，2中间选，为什么呢，因为最坏的情况也就是你把起点两边的两个点堵上去，就将整个路堵死了。那么只要dfs搜索两次路径，就可以了。第一次无路可走，答案是0，第一次有路...

dfs

2020-06-11

1 626

CodeForces 559B : Equivalent Strings

题目链接：https://codeforces.com/problemset/problem/559/B分析：比赛的时候以为是一道比较难的字符串题，用python交了一次递归的做法，结果runtime error了，可能是代码有问题。后来结束以后看别人的代码，才发现暴力的按照题目的分治递归就能过了。...

2020-06-08

1 943

幸运数字Ⅱ

题目链接：https://ac.nowcoder.com/acm/problem/15291分析：由于这道题的l 和 r的上线都很接近于int上限，觉得类型转换比较烦，所以索性把所有数据都声明为long long了在1e10里面的幸运数字个数为 2+2^2+2^3+2^4+...+2^10 数量...

dfs 打表

2020-06-06

13 740

走出迷宫

题目链接：https://ac.nowcoder.com/acm/problem/14572分析：很简单的dfs题目，当然也可以用bfs题，对于这类题是都行得通的，因为只要能走到终点就行。下面给出的是dfs的做法，“无脑走全图”。细节和终点看代码和注释吧！ #include<iostream&...

dfs

2020-06-05

2 782

建筑抢修

题目链接：https://ac.nowcoder.com/acm/problem/20154思路：首先将每栋建筑按照截至时间排序，当然你可以用结构体排序，或者定义二维数组，二位向量啥的，但是在这里，用pair会比较简单，pair 默认对first升序（若相等，对second 升序），这样可以避免写c...

堆贪心

2020-06-04

1 611

程序自动分析（不会写也能ac小技巧）

题目链接：https://ac.nowcoder.com/acm/problem/17881首先看到这道题，最简单的想法就是对于每一对相等的i，j通过并查集来建立联系，然后再去判断不相等的i，j是否有相等关系，有则不成立，没有就成立。但是一看i和j的数据范围，头晕了。这么大的数据？？？？？那怎么办呢...

并查集技巧性ac法（诈胡）

2020-06-03

2 731

关押罪犯

题目链接：https://ac.nowcoder.com/acm/problem/16591分析：因为市长只看最大影响力，所以我们将影响力从大到小排序，尽可能的去将会发生大影响的冲突避免（即将两个人分到两个监狱里面）下面解释一句话，敌人的敌人是朋友————假如 a和b会产生冲突，由于我们是将数组按照...

并查集

2020-06-03

16 900

任意点

题目链接：https://ac.nowcoder.com/acm/problem/15808说到这道题，就介绍一道及其相似的题目--- 加边无向图（链接：https://ac.nowcoder.com/acm/problem/14685）任意点这道题是很明显的一道并查集的题目，用一个复杂度为O（lo...

并查集

2020-06-02

4 699

加边的无向图

题目链接：https://ac.nowcoder.com/acm/problem/14685看题目好像是图论？不存在的，吓唬你一下而已。这就是简单的并查集，用到的也是并查集最常规的find 和merge（合并）操作而已在并查集基础上我用了集合，将各个不同的区域网放入了集合中，可能用不着set，...

并查集

2020-06-02

5 742