Deep_Dark_FAntasy♂

未归档

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

全部文章 / 未归档（共176篇）

牛牛的mex

链接：https://ac.nowcoder.com/acm/contest/7079/A思路：让求在这个区间的最小未出现的最小自然数，那么可以反向思维来求不在这个区间出现的最小自然数。那么维护一个前缀和后缀最小值即可。代码： #include<bits/stdc++.h> using ...

反向思维

2020-09-25

2 423

#165. 拉格朗日插值

题目链接：https://loj.ac/problem/165拉格朗日插值重心优化 #include<bits/stdc++.h> using namespace std; #define int long long const int mod = 998244353; const in...

拉格朗日插值重心优化

2020-09-23

2 566

两个数互质

如何判断两个数互质：来源：https://blog.csdn.net/HelloZEX/article/details/82667263 bool isrp(int a, int b) { if(a==1||b==1) // 两个正整数中，只有其中一个数值为1，两个正整数为互质...

2020-09-23

1 503

lower_bound和upper_bound

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 upper_bound( begin,end,num)：...

2020-09-23

1 447

DFS实现种子填充

种子填充(连通块）紫皮书p162 要实现bfs算法需要标记数组需要使用回溯法 #include <cstdio> #include <cstring> const int maxn = 100 + 5; char pic[maxn][maxn]; int m, n, ...

2020-09-23

1 508

【寒假坚持学习鸭】2.1日（暴力dfs）

题目地址：3rd_Practice_A:Illusive Chase 题目大意：先给你一幅图，0表示可以走，1表示障碍物。在第1s的时候，向R（右）走12步，第2s的时候，向D(下)方向走12步，第3s的时候向右走一步。问有多少个起始点满足要求。 tag：对每个点来遍DFS note：二维数组中...

2020-09-23

1 415

【寒假坚持学习鸭】2.2日（dfs求连通块）

题目地址题意：给你一个有m条权值为1的无向边的完全图，问你得到的最小生成树的权值为多少 tag:最小生成树，贪心思想题解：能用权值为0的边就用。那么对那m条边的端点，将能用0边到达的点都缩在一起形成一个个连通块在对缩完的点进行用1边连接，所以答案为缩完后的点数减一 dfs求连通块 u...

2020-09-23

1 457

最小生成树(MST)的Kruskal算法

内容来源紫皮书p356 kruskal算法的思想在于合并 Kruskal算法的第一步是给所有边按照从小到大的顺序排列。这一步可以直接使用sort。接下来从小到大依次考察每条边(u,v)。 u,v如果在同一个连通分量中，那么加入(u,v)后会成环伪代码：把所有边排序，记第i小的边为e[...

2020-09-23

1 667

最短路问题(Dijkstra算法、Bellman-Ford算法)

1.Dijkstra算法 Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路，即从单个源点出发，到所有节点的最短路。该算法同时适用于有向图和无向图。伪代码如下：清除所有点的标号设d[0]=0, 其他d[i]=INF 循环n次 { 在所有未标号结点中，选出...

2020-09-23

1 790

【寒假坚持学习鸭】2.3日（差分约束）

题目地址:https://vjudge.net/contest/354354#problem/F 参考博客：https://blog.csdn.net/qq_28954601/article/details/60969313 主要参考博客：差分约束算法总结：https://www.cnblo...

2020-09-23

1 480