最小生成树
假设 nnn 表示图中点数，mmm 表示图中边数。 Prim算法堆优化 时间复杂度 O(nlogn)O(nlogn)O(nlogn)。 核心思想：每次挑一条与当前集合相连的最短边。 code 12345678910111213141516171819202122232425int ans,cnt;struct edge{int v,w;};vector<edge> e[N];int d[N], vis[N];priority_queue<pair<int,int>> q; bool prim(int s){ for(int i=0;i<=n;i++) d[i]=inf; d[s]=0; q.push({0,s}); while(q.size()){ int u=q.top().second; q.pop(); if(vis[u])continue;//再出队跳过 vis[u]=1;//标记u已出队 ans+=d[u]; cnt++; ...
二叉树给出先序和中序遍历序列，求和树 要求输出中序遍历序列；
1.就算不知道用vector的初始化，也可以手动赋值创建子数组。 2.不断找到当前序列对应的根节点，计算他的子节点的总和，在这样递归处理过程中，注意要中序输出，所以对于是先遍历完左子树，然后输出答案，然后遍历右子树 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include <bits/stdc++.h>using namespace std;#define ll long long//# define int long long#define ull unsigned long long#define pii pair<int,int>#define baoliu(x, y) cout << fixed << setprecision(y) << x#define endl "\n"#define...
二叉树扩展先序遍历转中序遍历
利用前序遍历的特性，如果左子树不空，下一个一定是左节点，不然就是# 因为是转中序遍历，就在两次遍历之间输出 12345678910111213141516171819202122232425262728#include <iostream>#include <cstring>#include <algorithm>using namespace std;int k;string str;void dfs(){ if (str[k] == '#') { k ++ ; return; } char r = str[k ++ ]; // 根节点 dfs(); // 左子树 cout << r << ' '; dfs(); // 右子树}int main(){ cin >> str; dfs(); return 0;}
二叉树已经知道先序中序推后序
https://www.acwing.com/problem/content/3601/ 不断找新的先序的根节点，根据位置切割中序，根据中序左右子树大小反切割先序，找到左子树对应的先序中序，然后递归处理 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<stdio.h>#include<vector>#include<map>#include<algorithm>#include <algorithm>#include <iostream>#include<string>using namespace std;#define ll long long//# define int long long#define ull unsigned long long#define pii pair<int,int>#define...
给出中序和按层遍历，求该树的先序遍历，后序遍历，叶子结点。
一切的核心是怎么利用中序和按层遍历构建二叉树？ 1.优化空间很大，可以提前预处理记录每个数对应的位置，还可以vis数组记录这个点是不是已经作为根了。 2.我们考虑到每次找到当前中序要处理区间，里面的数记为集合mid，我们从前到后看层序遍历中的哪个数最先出现在mid中。那么这个数就是当前中序处理区间的根，这个新根的左边是左子树，右边是右子树，我们可以递归处理。 3.对于叶子节点，就是当他作为根的时候，没有左右节点，也就无法进行进一步深搜，flag记一下就可以了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include<stdio.h>#include<vector>#include<map>#include<algorithm>#include...
树的重心
12345678910111213141516171819202122232425262728const int N=100010;int n, a, b;vector<int> e[N];//用vector作邻接表int siz[N], pos, ans=1e9;void dfs(int x, int fa){ siz[x]=1; int mx=0; for(auto y : e[x]){ if(y == fa) continue; dfs(y, x);//先搜完，再统计答案 siz[x] += siz[y]; mx=max(mx, siz[y]); } mx=max(mx, n-siz[x]);//维护了重心是pos if(mx<ans) ans=mx,pos=x;}int main(){ scanf("%d", &n); for(int i=1;i<n;i++){ ...
完全二叉树的公共父结点
1.有点后序遍历的思想，就是先把左子树，右子树的结果算出来，然后合并到根节点。 2.合并时四种情况分类讨论. 3.对于遇到要找的点就可以直接返回，不管另一个点在这个点下面还是在别的子树上，都是正确的 123456789101112131415161718192021222324252627282930313233int n, m;int a[N];int query(int root,int x,int y){ //cerr<<root<<endl; if(root>max(x,y))return -1; if(root==x||root==y)return root; int l=query(2*root,x,y); int r=query(2*root+1,x,y); if(l==-1&&r==-1)return -1; if(l!=-1&&r!=-1)return root; if(l!=-1&&r==-1)return...
为什么树的dfs不需要vis数组，只需要维护父节点就可以？
无向图无环的，无环的图总是可以展成树的形式。 然后考虑无向图，顶多有回边指向父节点。不可能有回边指向祖先。更不可能有横向边，因为无环啊。所以只需要考虑指向父节点的回边就可以无需使用Vis。
字符串哈希
单哈希且用自然溢出代替取模操作，常数小但是容易被卡 单字符串区间内比较，查询子串hash值 123456789101112131415161718192021222324252627282930313233343536typedef unsigned long long ULL;const int N = 100010, P = 131;int n, m;char str[N];ULL h[N], p[N];ULL get(int l, int r){ return h[r] - h[l - 1] * p[r - l + 1];}int main(){ scanf("%d%d", &n, &m); scanf("%s", str + 1); p[0] = 1; for (int i = 1; i <= n; i ++ ) { h[i] = h[i - 1] * P + str[i]; p[i] = p[i - 1]...
最新文章