算法题遇到的技巧和心得

IOIOIO记录算法题遇到的技巧可以在评论区补充你的看法和技巧1.有效括号1.左括号的数量 右括号的数量2.从头开始的任意一个子串左括号的数量 右括号的数量题目22. 括号生成 - 力扣LeetCode2.对字符处理的常用函数C/C中对字符处理的常用函数_c关于字符的常用函数-CSDN博客3.同余定理974. 和可被 K 整除的子数组 - 力扣LeetCode4.常见位运算基础位运算 (有0就是0) || (有1就是1)~ ^ (相同为0相异为1)无进位相加给一个数n确定n的二进制表示中 x 位是 0 还是 1操作 n (1 x)x位是0就返回0是1就返回1将一个数n的二进制表示中 x 位改成1操作n | (1 x)提取一个数n二进制最右侧的1操作n -n-n的本质将最右侧的1的左边的区域全部变成相反n: 0110101000~n: 10010101111:1001011000-n :1001011000对比n和-n可以发现-n的本质所以可以把n二进制最右侧的1提取出来干掉一个数n二进制中最右侧的1操作n (n - 1)(n - 1)的本质将最右侧的1右边的区域包含1全部变成相反n011010100n - 1011010011011010000异或(^)运算a ^ 0 aa ^ a 0 (消消乐)a ^ b ^ c a ^ (b ^ c) 用无进位相加来理解5.向上取整int ret (count k - 1) / k; // 计算用多少个k可以把count消除完6.差分1.作用快速解决“将某一个区间所有的元素统一加上一个数”的操作2.差分数组f[i]表示当前元素与前一个元素的差值3.性质原数组[LR]区间全部加上k这个操作相当于在差分数组中f[L] kf[R 1] - k(根据定义可证明)4.在初始化差分数组的时候可以直接用定义来初始化因为相当于在a[i]这个位置上加上一个 数(k)所以就可以用性质f[L] kf[R 1] - k来初始化5.最后对差分数组用前缀和运算来还原证明看下图7.二维差分8.使用unordered_map的细节问题https://www.doubao.com/thread/w9beaaab35d1349079.lower_bound 和 upper_bound的使用【STL中的⼆分查找】1. lower_bound 大于等于x的最小元素返回的是迭代器时间复杂度 O(logN)。2. upper_bound 大于x的最小元素返回的是迭代器。时间复杂度 O(logN) 。二者均采用二分实现。但是STL中的二分查找只能适用于在有序的数组中查找如果是二分答案就不能使用。10.哈夫曼编码11.正方形已知相邻两点求下面两点// 已知x1,y1 x2,y2两点 int x3 x1 - (y2 - y1); int y3 y1 (x2 - x1); int x4 x2 - (y2 - y1); int y4 y2 (x2 - x1);https://www.doubao.com/thread/w070944115d11e5b1https://www.doubao.com/thread/w070944115d11e5b112.离散化用sort排序unique去重lower_bound()查找下标即可。性质升序。情况虽然区间长度很大但是「区间 的个数」是很少的对于区间问题离散化会把区间缩短为了避免出现这种情况我们可以在离散化的区间[x,y]时不仅考虑x,y这两个值也把「x1,y1」也考虑进去。此时「单个区间内部」就出现空隙「区间与区间之间」也会出现空隙。就可以避免这种情况出现。此时的disc[N*4]因为有两套x,y,x 1, y 113.8个方向int dx[8] {0, 0, 1, -1, 1, -1, -1, 1}; int dy[8] {1, -1, 0, 0, 1, 1, -1, -1}; int dx[8] {0, 0, 1, -1, 1, -1, 1, -1}; int dy[8] {1, -1, 0, 0, 1, 1, -1, -1};14.最短路问题单源最短路P3371 【模板】单源最短路径弱化版 - 洛谷迪杰斯特拉时间复杂度O(n^2 m)#include bits/stdc.h using namespace std; //#define int long long const int N 1e4 10; const int M 5e5 10; const int INF 2147483647; using PII pairint, int; using ull unsigned long long; #define endl \n int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; int dxx[] {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] {1, -1, 0, 0, 1, 1, -1, -1}; ull base 131; vectorPII edges[M]; int dist[N]; int st[N]; int n, m, s; void dijkstra() { // 0 也要初始化 for(int i 0; i n; i) dist[i] INF; dist[s] 0; for(int i 1; i n; i) { int u 0; for(int j 1; j n; j) if(!st[j] dist[j] dist[u]) u j; st[u] true; for(auto e : edges[u]) { int v e.first; int w e.second; if(dist[u] w dist[v]) { dist[v] dist[u] w; } } } for(int i 1; i n; i) cout dist[i] ; } void solve() { cin n m s; for(int i 1; i m; i) { int u, v, w; cin u v w; edges[u].push_back({v, w}); } dijkstra(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ 1; // cin _; while(_--) { solve(); } return 0; }迪杰斯特拉堆优化P4779 【模板】单源最短路径标准版 - 洛谷时间复杂度O(m*logm)#include bits/stdc.h using namespace std; //#define int long long const int N 1e5 10; const int M 5e5 10; const int INF 2147483647; using PII pairint, int; using ull unsigned long long; #define endl \n int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; int dxx[] {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] {1, -1, 0, 0, 1, 1, -1, -1}; ull base 131; vectorPII edges[M]; int dist[N]; int st[N]; int n, m, s; void dijkstra() { // 0 也要初始化 priority_queuePII, vectorPII, greaterPII heap; for(int i 0; i n; i) dist[i] INF; dist[s] 0; heap.push({0, s}); while(heap.size()) { auto t heap.top(); heap.pop(); int u t.second; if(st[u]) continue; st[u] true; for(auto e : edges[u]) { int v e.first; int w e.second; if(dist[u] w dist[v]) { dist[v] dist[u] w; heap.push({dist[v], v}); } } } for(int i 1; i n; i) cout dist[i] ; } void solve() { cin n m s; for(int i 1; i m; i) { int u, v, w; cin u v w; edges[u].push_back({v, w}); } dijkstra(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ 1; // cin _; while(_--) { solve(); } return 0; }bellman-ford算法#include bits/stdc.h using namespace std; //#define int long long const int N 1e4 10; const int M 5e5 10; const int INF 2147483647; using PII pairint, int; using ull unsigned long long; #define endl \n int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; int dxx[] {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] {1, -1, 0, 0, 1, 1, -1, -1}; ull base 131; int n, m, s; int dist[N]; bool st[N]; vectorPII edges[M]; void dijkstra() { for(int i 0; i n; i) dist[i] INF; dist[s] 0; for(int i 1; i n; i) { int u 0; for(int i 1; i n; i) if(!st[i] dist[i] dist[u]) u i; st[u] true; for(auto e : edges[u]) { int v e.first; int w e.second; if(dist[u] w dist[v]) { dist[v] dist[u] w; } } } for(int i 1; i n; i) { cout dist[i] ; } } void bf() { for(int i 1; i n; i) dist[i] INF; dist[s] 0; for(int i 1; i n; i) { bool flag 1; for(int u 1; u n; u) { if(dist[u] INF) continue; for(auto e : edges[u]) { int v e.first; int w e.second; if(dist[u] w dist[v]) { flag 0; dist[v] dist[u] w; } } } if(flag) break; } for(int i 1; i n; i) cout dist[i] ; } void solve() { cin n m s; for(int i 1; i m; i) { int u, v, w; cin u v w; edges[u].push_back({v, w}); } bf(); // dijkstra(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ 1; // cin _; while(_--) { solve(); } return 0; }spfa算法0#include bits/stdc.h using namespace std; //#define int long long const int N 1e4 10; const int M 5e5 10; const int INF 2147483647; using PII pairint, int; using ull unsigned long long; #define endl \n int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; int dxx[] {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] {1, -1, 0, 0, 1, 1, -1, -1}; ull base 131; vectorPII edges[M]; int dist[N]; int st[N]; int n, m, s; void dijkstra() { // 0 也要初始化 priority_queuePII, vectorPII, greaterPII heap; for(int i 0; i n; i) dist[i] INF; dist[s] 0; heap.push({0, s}); while(heap.size()) { auto t heap.top(); heap.pop(); int u t.second; if(st[u]) continue; st[u] true; for(auto e : edges[u]) { int v e.first; int w e.second; if(dist[u] w dist[v]) { dist[v] dist[u] w; heap.push({dist[v], v}); } } } for(int i 1; i n; i) cout dist[i] ; } void bf() { for(int i 0; i n; i) dist[i] INF; dist[s] 0; for(int i 1; i n; i) { bool flag 0; for(int u 1; u n; u) { if(dist[u] INF) continue; for(auto e : edges[u]) { int v e.first; int w e.second; if(dist[u] w dist[v]) { flag 1; dist[v] dist[u] w; } } } if(flag 0) break; } for(int i 1; i n; i) cout dist[i] ; } void spfa() { for(int i 1; i n; i) dist[i] INF; dist[s] 0; queueint q; q.push(s); st[s] true; while(q.size()) { int u q.front(); q.pop(); st[u] false; for(auto e : edges[u]) { int v e.first; int w e.second; if(dist[u] w dist[v]) { dist[v] dist[u] w; if(!st[v]) { q.push(v); st[v] true; } } } } for(int i 1; i n; i) cout dist[i] ; } void solve() { cin n m s; for(int i 1; i m; i) { int u, v, w; cin u v w; edges[u].push_back({v, w}); } // dijkstra(); // bf(); spfa(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ 1; // cin _; while(_--) { solve(); } return 0; }负环P3385 【模板】负环 - 洛谷BF算法判断负环#include bits/stdc.h using namespace std; //#define int long long const int N 2e3 10; const int M 3e3 10; const int INF 0x3f3f3f3f; using PII pairint, int; using ull unsigned long long; #define endl \n int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; int dxx[] {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] {1, -1, 0, 0, 1, 1, -1, -1}; ull base 131; vectorPII edges[M]; int dist[N]; int st[N]; int n, m; //void bf() //{ // for(int i 0; i n; i) dist[i] INF; // dist[s] 0; // // for(int i 1; i n; i) // { // bool flag 0; // for(int u 1; u n; u) // { // if(dist[u] INF) continue; // for(auto e : edges[u]) // { // int v e.first; // int w e.second; // if(dist[u] w dist[v]) // { // flag 1; // dist[v] dist[u] w; // } // } // } // if(flag 0) break; // } // for(int i 1; i n; i) cout dist[i] ; //} int s; bool bf() { // memset(dist, 0x3f, sizeof dist); for(int i 0; i n; i) dist[i] INF; dist[1] 0; bool flag; for(int i 1; i n; i) // 执行到n次看第n次是否会松弛操作 { flag false; for(int u 1; u n; u) { if(dist[u] INF) continue; for(auto e : edges[u]) { int v e.first; int w e.second; if(dist[u] w dist[v]) { flag true; dist[v] dist[u] w; } } } if(flag false) return flag; } return flag; } void solve() { for(int i 1; i M; i) edges[i].clear(); cin n m; for(int i 1; i m; i) { int u, v, w; cin u v w; edges[u].push_back({v, w}); if(w 0) edges[v].push_back({u, w}); } // dijkstra(); // bf(); // spfa(); if(bf()) cout YES endl; else cout NO endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ 1; cin _; while(_--) { solve(); } return 0; }spfa判断负环#include bits/stdc.h using namespace std; //#define int long long const int N 2e3 10; const int M 3e3 10; const int INF 0x3f3f3f3f; using PII pairint, int; using ull unsigned long long; #define endl \n int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; int dxx[] {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] {1, -1, 0, 0, 1, 1, -1, -1}; ull base 131; vectorPII edges[M]; int dist[N]; int st[N]; int n, m; int cnt[N]; bool spfa() { memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); memset(cnt, 0, sizeof cnt); dist[1] 0; st[1] true; queueint q; q.push(1); while(q.size()) { int u q.front(); q.pop(); st[u] false; for(auto e : edges[u]) { int v e.first; int w e.second; if(dist[u] w dist[v]) { cnt[v] cnt[u] 1; if(cnt[v] n) return true; dist[v] dist[u] w; if(!st[v]) { q.push(v); st[v] true; } } } } return false; } void solve() { cin n m; for(int i 1; i n; i) edges[i].clear(); for(int i 1; i m; i) { int u, v, w; cin u v w; edges[u].push_back({v, w}); if(w 0) edges[v].push_back({u, w}); } if(spfa()) cout YES endl; else cout NO endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ 1; cin _; while(_--) { solve(); } return 0; }小总结多源最短路模板题B3647 【模板】Floyd - 洛谷代码#include bits/stdc.h using namespace std; //#define int long long const int N 110; const int M 4600; const int INF 0x3f3f3f3f; using PII pairint, int; using ull unsigned long long; #define endl \n int dx[] {0, 0, 1, -1}; int dy[] {1, -1, 0, 0}; int dxx[] {0, 0, 1, -1, 1, -1, 1, -1}; int dyy[] {1, -1, 0, 0, 1, 1, -1, -1}; ull base 131; int f[N][N]; int n, m; void floyd() { for(int k 1; k n; k) { for(int i 1; i n; i) { for(int j 1; j n; j) { f[i][j] min(f[i][j], f[i][k] f[k][j]); } } } for(int i 1; i n; i) { for(int j 1; j n; j) { cout f[i][j] ; } cout endl; } } void solve() { cin n m; memset(f, 0x3f, sizeof f); for(int i 1; i n; i) f[i][i] 0; for(int i 1; i m; i) { int u, v, w; cin u v w; f[u][v] f[v][u] min(f[u][v], w); } floyd(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int _ 1; // cin _; while(_--) { solve(); } return 0; }生成全排列https://www.doubao.com/thread/w1445475a5d70c00ehttps://www.doubao.com/thread/w4606a86ee3941e00等差数量求和公式