链表
链表 单链表 1234567891011121314151617181920212223242526272829303132333435void solve() { int n; cin >> n; int idx = 0; vector<int> nex(n + 1), e(n + 1); nex[0] = -1; int &head = nex[0]; auto insert = [&](int x, int k) { // 在地址为k的数后插入x idx++; nex[idx] = nex[k]; e[idx] = x; nex[k] = idx; }; auto del = [&](int k) { // 删除地址为k的数 nex[k] = nex[nex[k]]; }; for (int i = 1; i <= n; i++)...
最基础树状数组
1.单点加 2.前缀和查询 1234567891011121314151617181920212223242526272829303132int n, m;int a[N];int tr[N];int lowbit(int x){ return x&(-x);}void add(int pos,int k){ for(int i=pos;i<=n;i+=lowbit(i))tr[i]+=k;}int query(int x){ int res=0; for(int i=x;i;i-=lowbit(i))res+=tr[i]; return res;}void solve(){ cin>>n;cin>>m; for(int i=1;i<=n;i++){ int x;cin>>x; add(i,x); } while(m--){ int op;cin>>op; if(op==1){ int...
ST 表
封装函数版本 123456789101112131415161718192021222324252627282930313233343536template <typename T, class F = function<T(const T&, const T&)>>struct SparseTable { int n; vector<vector<T>> st; F func; SparseTable(const vector<T>& a, const F& f) : func(f) { n=(int)a.size()-1; int max_log = __lg(n) +1; st.resize(max_log+1); st[0] = a; for (int j = 1; j <=max_log; j++) { ...
最大子序列和
题目描述：给定一个序列，数有正有负，你需要选出一个子序列（不能为空）使你得到的和最大，对于选出来的子序列应该满足相邻数之间奇偶性不同，输出可以得到的最大和 没怎么改的std 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#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 double long double#define baoliu(x, y) cout << fixed << setprecision(y) << x#define endl "\n"const int N = 2e5 +...
染色法判定二分图
20230723与y总代码模板不同，为自己独立实现，不够美观，但便于自己理解 debug过程： 需要注意到本题是无向图，所以add函数需要用两次，还有就是我们使用链式前向星结构去存图，所以ne和e数组需要开两倍的边数。 就是因为数组开小了，导致最后tle了，数组开小了什么报错都有可能出现 染色算法能够解决非连通图的二部图判定，所以从一个点dfs出发是不够的，要多源dfs 也就是说对每个连通块进行dfs,先对一个点dfs后，找此时没有被染色的点再dfs，直到全都被染色或者dfs过程中return false; 这个dfs过程不需要还原现场，因为我们需要保留所有点的颜色。 我的代码中dfs函数只有一个参数，yxc的代码是两个参数，都是可以的？！ 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include...
染色法判定二分图(1)
...
拓扑排序
1234567891011121314151617181920212223242526272829const int N = 100010;int n,m,a,b;vector<int> e[N], tp;int din[N];//入度数组bool toposort(){ queue<int> q; for(int i = 1; i <= n; i++) if(din[i]==0) q.push(i); while(q.size()){ int x=q.front(); q.pop(); tp.push_back(x); for(auto y : e[x]){ if(--din[y]==0) q.push(y); } } return tp.size() == n;}int main(){ cin >> n >> m; for(int i=0; i<m; i++){ cin...
网格图上问题
2024天梯赛L3-1https://pintia.cn/problem-sets/994805046380707840/exam/problems/1781658570803388428?type=7&page=1 题意：网格图上有障碍物，空地，给定若干起点，和一个终点，求唯一的最短路。也就是存在大于等于两个起点到终点距离相同的时候，这些起点无法贡献答案。 Solution：考虑直接从终点开始bfs，得到所有答案，最后统计起点即可更新答案。 实现细节：首先这个题目给的坐标是和以往反过来的，需要我们仔细读题和看样例。其次我们在统计答案的时候，直接维护值域的哈希表，不应该维护pair坐标的哈希表，不然肯定不会出现重复。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960int n, m;int a[N][N];map<pii,int>mp;int...
最短路
单源最短路： 求一个点到其他点的最短路 多源最短路： 求任意两个点的最短路 稠密图用邻接矩阵存，稀疏图用邻接表存储。 稠密图： m 和 n2 一个级别 稀疏图： m 和 n 一个级别 朴素dij： 123456789101112131415161718192021222324252627282930313233int n,m,s,a,b,c;const int N=100010;struct edge{int v,w;};vector<edge> e[N];int d[N], vis[N];void dijkstra(int s){ for(int i=0;i<=n;i++)d[i]=inf; d[s]=0; for(int i=1;i<n;i++){//枚举次数 int u=0; for(int j=1;j<=n;j++)//枚举点 if(!vis[j]&&d[j]<d[u]) u=j; vis[u]=1; //标记u已出圈 for(auto...
最短路Floyd
12345678910111213141516void floyd(){ for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}init(){ for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF;}存边方式： d[a][b] = min(d[a][b], w);# 如果是无向边需要加d[b][a]
最新文章