fluery算法 void dfs(int x){ s.top++; s.node[s.top] = x; for(int i=0;i<n;i++){ if(graph[x][i]>0{ graph[x][i] = graph[i][x] = 0; dfs(i); break; } } return; } void fluery(int start){ int i; s.top = 0; s.node[s.top]...

spfa判断正环 Word Rings 二分+判断正环 #include<iostream> #include<cstring> #include<string> #include<cstdio> #include<vector> #include<map> #include<algorithm> #include<queue> using namespace std; const int maxn = 100000+5; vector<pair<int,int> >e[ma...

spfa_dfs的优化 spfa的朴素优化 void spfa(Node){ instack[Node] = true; for(Node,v) in E: if dis[v]>dis[Node]+edge(Node,v)){ dis[v] = dis[Node]+edge(Node,v); if not instack[v] { spfa(v); }else{ return; } }...

康托展开和逆康托展开 static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 阶乘 int cantor(int *a, int n) { int x = 0; for (int i = 0; i < n; ++i) { int smaller = 0; // 在当前位之后小于其的个数 for (int j = i + 1; j < n; ++j) { if (a[j] < a[i]) ...

双端队列bfs 题意： 一个 的图，现在有一束激光从左上角往右边射出，每遇到 '#'，你可以选择光线往四个方向射出，或者什么都不做，问最少需要多少个 '#' 往四个方向射出才能使光线在第 行往右边射出。此题目正解不是 0-1 BFS 但是适用 0-1 BFS 可以不需要思考过程，赛时许多大佬都是这么做的。做法很简单，一个方向射出不需要花费（0），而往四个方向射出需要花费（1），然后直接来就可以了。 适用条件：0-1图 #include <bits/stdc++.h> using namespace std; #define INF (1 << 29) int n, ...

贪心 #include <bits/stdc++.h> using namespace std; int n; #define MAXN 100010 int a[MAXN],b[MAXN]; int st,ed; struct Range{ int l,r; bool operator < (Range& w){ if(l==w.l) return r>w.r; return l<w.l; } }range[MAXN]; int main(){ cin>>st>>...

贪心 #include <bits/stdc++.h> using namespace std; #define N 100010 int n; struct Range{ int l,r; bool operator<(Range& w){ return l<w.l; } }range[N]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>range[i].l>>range[i].r; ...

Acwing 838 堆排序 #include <iostream> #include <cstdio> using namespace std; int m,n; #define MAXN 100010 int a[MAXN]; int size; void down(int u){ int t = u; if(u*2<=size && a[u*2]<a[t]) t = u*2; if(u*2+1<=size && a[u*2+1]<a[t]) t = u*2+1; if(u!=...

任意进制转换 题意：任意进制的转换代码：https://www.acwing.com/problem/content/126/ #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int T; cin >> T; while (T -- ) { int a, b; string line; cin >> a >&g...

题目大意：https://www.cnblogs.com/xxzh/p/9278487.html代码： #include <bits/stdc++.h> using namespace std; const int maxn = 100000 + 10; const int inf = 1e9 + 7; int m, n, k = 1; int head[maxn], c[maxn], dp[maxn][2]; struct EDGE { int to, next; } e[maxn]; void add(int u, int v) { e[++k].next =...

Leetcode 425 Word Square 题意：找所有满足要求的能够成对称矩阵的字符串的合集代码：https://leetcode.com/problems/word-squares/description/ class Solution{ public: struct TrieNode{ vector<int> indexes; vector<TrieNode*> children; TrieNode():children(26,NULL){} ...

树的重心： 假设有unordered_map<int,vector<int>> m 表示与结点关联的结点 void dfs(int v,int fa){ son[v] = 0; int d = G[v].size(); int prebalance = 0; for(int i=0;i<d;i++){ int k = G[v][i]; if(k==fa) continue; son[v] += son[u]+1; ...

Leetcode 903 题目大意： 求符合DI字符串的序列的个数 代码： class Solution { public: int numPermsDISequence(string S) { int res =0, n = S.size(),M=1e9+7; vector<vector<int>> dp(n+1,vector<int>(n+1)); dp[0][0] = 1; for(int i=1;i<=n;i++){ for(int j=0;j&lt...

Leetcode 730 Count Distinct Palindrome Subsequences 题目大意： 求对称回文子序列的个数 代码：https://www.cnblogs.com/fenice/p/7979770.html const int mod=1e9+7; class Solution { public: int dfs(int l,int r,int k,string& S,vector<vector<vector<int> > >& dp) { if(r<l) return 0; ...