肖先生~

题解

bfs(2) dfs(2) dp(6) hdu(9) html(2) Oracle(3) poj(2) STL(3) 优先队列(1) 位运算(1) 全排列(1) 前缀和(2) 并查集(1) 数学问题(1) 最小生成树(1) 最短路(1) 未归档(12) 模拟(9) 汇编(1) 牛客(23) 贪心(1)

/ 注册

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

旅行来自专栏

spfa+链式前向星存图题目大意首先要明确，不管题目给了多少个城市，题目只需要求三个点之间的最大距离的最短路径，所以我们依次枚举每个中点，让每个点都做一次中点，并跑一次spfa，求出最短路径，然后再求最短路径的最大值就行细节处理就是在跑完spfa之后，此时的最短路已经形成，我们所要做的就是求...

2020-07-16

0 760

道路建设来自专栏

最小生成树的模板题不多说，可以看我之前写的最小生成树的博客 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; int pre[maxn]; struct node { int u, ...

2020-07-14

0 610

挖沟来自专栏

最小生成树模板题直接上代码大概意思解释一下，1.首先最小生成树的克鲁斯卡尔算法相当于并查集的升级版，与并查集不同的是，他要对边的权值进行排序，并且最后生成树的边是m-1条2.我们用一个结构体内嵌比较函数去记录和排序边，外加一个路径压缩和一个判断联通的函数3.然后我们对已经排好队的边进行加边操作，如...

2020-07-14

2 680

DDoS 来自专栏

记忆化搜索开始我还以为是一个最小生成树的题目，后面发现不是，他这里的边不起到作用，可以说是可有可无的，最后看来这就是一个深度优先搜索求到达终点可行边的数量 #include <bits/stdc++.h> using namespace std; const int maxn = 1e...

2020-07-14

1 723

计算系数来自专栏

组合数学+快速幂方法一：递推+打表首先我第一眼看到的时候就隐隐约约的感觉到了一丝熟悉的味道，这不就是高中数学的组合思想嘛，然后就快速的敲了一遍，但是却忘记了组合数学的规律，组合数学和杨辉三角紧密的联系在一起！！他的每一项系数正好是杨慧三角每一行的值，所以我们只要把杨辉三角打印出来，然后就可以快速...

2020-07-13

0 743

最大公约数(lcm) 来自专栏

水题虽然这是个水题，但是还是有一些地方要注意一下，题目说了不能超过ULL的范围，我们都知道求解两个数的最小公倍数就是用a*b/gcd（a，b）。。但是！！！这里不能超过题目给的范围，所以我们就要先相除再相乘，这样处理就不会越界了第一种解法——利用STL内置函数 #include <b...

2020-07-12

2 686

Diff-prime Pairs 来自专栏

数论+埃氏筛+前缀和题目分析：这道题目的难度只有一颗星，但是题目给的数据范围达到了1e7之多，暴力的时间复杂度达到了O（n^2），显然是不行的，所以这个题目需要优化+转化，我们不能被题目的表现所迷惑，题目里面有gcd，但是如果去求gcd的话时间复杂度肯定很高，所以这里用了十分巧妙地方法 1.首先我...

2020-07-12

1 612

经商

并查集+01背包（滚动数组） PS：刚开始并没有想到这是一个并查集+01背包，我就以为是一个简单的并查集然后贪心就完事了，但是当时纠结的是，两边都可以贪心（精力和利益值），当时没多想随便找一个贪心然后代码过了样例，交上去的时候却wa了，这时候就开始认真分析问题了。求解最大值有两种方式，一个是二分，一...

2020-06-19

0 584

Cut

贪心这个题目我吐了，居然用long long才能过，简单排序+贪心，我们按照从小到大排序就行，这样下一步操作只是将当前最小的数去掉，这样就能保持最大数了很简单的题目啦~ #include <bits/stdc++.h> using namespace std; const int m...

2020-06-14

0 494

加边的无向图

并查集模板题这与前一个题目任意点几乎一样，只需要改一下main函数里面的一小部分代码就行我们把联通之间的点放入一个集合，最后只需要去找根节点就知道有多少个集合，我们需要集合数减一的边就可以把这些散落的集合联系起来 #include <bits/stdc++.h> using names...

2020-06-14

0 431