基础算法
快速排序
#include <iostream> using namespace std; const int N = 100010; int q[N]; void quick_sort(int q[], int l, int r){ if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j){ do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r); } int main(){ int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); quick_sort(q, 0, n - 1); for (int i = 0; i < n; i ++ ) printf("%d ", q[i]); return 0; }
第k kk个数
#include <iostream> using namespace std; const int N = 100010; int q[N]; int quick_sort(int q[], int l, int r, int k){ if (l >= r) return q[l]; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j){ do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } if (j - l + 1 >= k) return quick_sort(q, l, j, k); else return quick_sort(q, j + 1, r, k - (j - l + 1)); } int main(){ int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); cout << quick_sort(q, 0, n - 1, k) << endl; return 0; }
归并排序
#include <iostream> using namespace std; const int N = 1e5 + 10; int a[N], tmp[N]; void merge_sort(int q[], int l, int r){ if (l >= r) return; int mid = l + r >> 1; merge_sort(q, l, mid), merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; } int main(){ int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); merge_sort(a, 0, n - 1); for (int i = 0; i < n; i ++ ) printf("%d ", a[i]); return 0; }
逆序对数
#include <iostream> using namespace std; typedef long long LL; const int N = 1e5 + 10; int a[N], tmp[N]; LL merge_sort(int q[], int l, int r){ if (l >= r) return 0; int mid = l + r >> 1; LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else{ res += mid - i + 1; tmp[k ++ ] = q[j ++ ]; } while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; return res; } int main(){ int n; scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); cout << merge_sort(a, 0, n - 1) << endl; return 0; }
数的范围
#include <iostream> using namespace std; const int N = 100010; int n, m; int q[N]; int main(){ scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); while (m -- ){ int x; scanf("%d", &x); int l = 0, r = n - 1; while (l < r){ int mid = l + r >> 1; if (q[mid] >= x) r = mid; else l = mid + 1; } if (q[l] != x) cout << "-1 -1" << endl; else{ cout << l << ' '; int l = 0, r = n - 1; while (l < r){ int mid = l + r + 1 >> 1; if (q[mid] <= x) l = mid; else r = mid - 1; } cout << l << endl; } } return 0; }
三次方根
#include <iostream> using namespace std; int main(){ double x; cin >> x; double l = -100, r = 100; while (r - l > 1e-8){ double mid = (l + r) / 2; if (mid * mid * mid >= x) r = mid; else l = mid; } printf("%.6lf\n", l); return 0; }
高精加
#include <iostream> #include <vector> using namespace std; vector<int> add(vector<int> &A, vector<int> &B){ if (A.size() < B.size()) return add(B, A); vector<int> C; int t = 0; for (int i = 0; i < A.size(); i ++ ){ t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C; } int main(){ string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0'); auto C = add(A, B); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; return 0; }
高精减
#include <iostream> #include <vector> using namespace std; bool cmp(vector<int> &A, vector<int> &B){ if (A.size() != B.size()) return A.size() > B.size(); for (int i = A.size() - 1; i >= 0; i -- ) if (A[i] != B[i]) return A[i] > B[i]; return true; } vector<int> sub(vector<int> &A, vector<int> &B){ vector<int> C; for (int i = 0, t = 0; i < A.size(); i ++ ){ t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main(){ string a, b; vector<int> A, B; cin >> a >> b; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0'); vector<int> C; if (cmp(A, B)) C = sub(A, B); else C = sub(B, A), cout << '-'; for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl; return 0; }
高精乘
#include <iostream> #include <vector> using namespace std; vector<int> mul(vector<int> &A, int b){ vector<int> C; int t = 0; for (int i = 0; i < A.size() || t; i ++ ){ if (i < A.size()) t += A[i] * b; C.push_back(t % 10); t /= 10; } while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main(){ string a; int b; cin >> a >> b; vector<int> A; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); auto C = mul(A, b); for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]); return 0; }
高精除
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> div(vector<int> &A, int b, int &r){ vector<int> C; r = 0; for (int i = A.size() - 1; i >= 0; i -- ){ r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; } int main(){ string a; vector<int> A; int B; cin >> a >> B; for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0'); int r; auto C = div(A, B, r); for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i]; cout << endl << r << endl; return 0; }
前缀和
#include <iostream> using namespace std; const int N = 100010; int n, m; int a[N], s[N]; int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化 while (m -- ){ int l, r; scanf("%d%d", &l, &r); printf("%d\n", s[r] - s[l - 1]); // 区间和的计算 } return 0; }
矩阵前缀和
#include <iostream> using namespace std; const int N = 1010; int n, m, q; int s[N][N]; int main(){ scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) scanf("%d", &s[i][j]); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; while (q -- ){ int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]); } return 0; }
差分
#include <iostream> using namespace std; const int N = 100010; int n, m; int a[N], b[N]; void insert(int l, int r, int c){ b[l] += c; b[r + 1] -= c; } int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]); while (m -- ){ int l, r, c; scanf("%d%d%d", &l, &r, &c); insert(l, r, c); } for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1]; for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]); return 0; }
差分矩阵
#include <iostream> using namespace std; const int N = 1010; int n, m, q; int a[N][N], b[N][N]; void insert(int x1, int y1, int x2, int y2, int c){ b[x1][y1] += c; b[x2 + 1][y1] -= c; b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c; } int main(){ scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) scanf("%d", &a[i][j]); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) insert(i, j, i, j, a[i][j]); while (q -- ){ int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; insert(x1, y1, x2, y2, c); } for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; for (int i = 1; i <= n; i ++ ){ for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]); puts(""); } return 0; }
最长连续不重复子序列
#include <iostream> using namespace std; const int N = 100010; int n; int q[N], s[N]; int main(){ scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]); int res = 0; for (int i = 0, j = 0; i < n; i ++ ){ s[q[i]] ++ ; while (j < i && s[q[i]] > 1) s[q[j ++ ]] -- ; res = max(res, i - j + 1); } cout << res << endl; return 0; }
数组元素的目标和
#include <iostream> using namespace std; const int N = 1e5 + 10; int n, m, x; int a[N], b[N]; int main(){ scanf("%d%d%d", &n, &m, &x); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]); for (int i = 0, j = m - 1; i < n; i ++ ){ while (j >= 0 && a[i] + b[j] > x) j -- ; if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl; } return 0; }
二进制中1的个数
#include <iostream> using namespace std; int main(){ int n; scanf("%d", &n); while (n -- ){ int x, s = 0; scanf("%d", &x); for (int i = x; i; i -= i & -i) s ++ ; printf("%d ", s); } return 0; }
区间和离散化
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 300010; int n, m; int a[N], s[N]; vector<int> alls; vector<PII> add, query; int find(int x){ int l = 0, r = alls.size() - 1; while (l < r){ int mid = l + r >> 1; if (alls[mid] >= x) r = mid; else l = mid + 1; } return r + 1; } int main(){ cin >> n >> m; for (int i = 0; i < n; i ++ ){ int x, c; cin >> x >> c; add.push_back({x, c}); alls.push_back(x); } for (int i = 0; i < m; i ++ ){ int l, r; cin >> l >> r; query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } // 去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 处理插入 for (auto item : add){ int x = find(item.first); a[x] += item.second; } // 预处理前缀和 for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; // 处理询问 for (auto item : query){ int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; }
区间合并
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; void merge(vector<PII> &segs){ vector<PII> res; sort(segs.begin(), segs.end()); int st = -2e9, ed = -2e9; for (auto seg : segs) if (ed < seg.first){ if (st != -2e9) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else ed = max(ed, seg.second); if (st != -2e9) res.push_back({st, ed}); segs = res; } int main(){ int n; scanf("%d", &n); vector<PII> segs; for (int i = 0; i < n; i ++ ){ int l, r; scanf("%d%d", &l, &r); segs.push_back({l, r}); } merge(segs); cout << segs.size() << endl; return 0; }
数据结构
单调栈
给定一个长度为 N NN的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
#include<iostream> #include<stack> using namespace std; stack<int> stk; const int N = 100005; int arr[N]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> arr[i]; for (int i = 0; i < n; i++) { while (!stk.empty()&&arr[i] <= stk.top()) stk.pop(); if (stk.empty()) cout << -1 << " "; else cout << stk.top() << " "; stk.push(arr[i]); } return 0; }
滑动窗口
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
#include<iostream> #include<deque> using namespace std; deque<int> dq; const int N = 1000005; int arr[N]; int main() { int n, k; cin >> n >> k; for (int i = 0; i < n; i++) cin >> arr[i]; for (int i = 0; i < n; i++) { if (!dq.empty() && i - k + 1 > dq.front()) dq.pop_front(); while (!dq.empty() && arr[dq.back()] >= arr[i]) dq.pop_back(); dq.push_back(i); if (i >= k - 1) cout << arr[dq.front()]<<" "; } dq.clear(); cout << endl; for (int i = 0; i < n; i++) { if (!dq.empty() && i - k + 1 > dq.front()) dq.pop_front(); while (!dq.empty() && arr[dq.back()] <= arr[i]) dq.pop_back(); dq.push_back(i); if (i >= k - 1) cout << arr[dq.front()] << " "; } return 0; }
KMP
#include <iostream> using namespace std; const int N = 100010, M = 1000010; int n, m; int ne[N]; char s[M], p[N]; int main(){ cin >> n >> p + 1 >> m >> s + 1; for (int i = 2, j = 0; i <= n; i ++ ){ while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++ ; ne[i] = j; } for (int i = 1, j = 0; i <= m; i ++ ){ while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j ++ ; if (j == n){ printf("%d ", i - n); j = ne[j]; } } return 0; } /*下标从0开始 #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1000010; int n, m; char s[N], p[N]; int ne[N]; int main(){ cin >> m >> p >> n >> s; ne[0] = -1; for (int i = 1, j = -1; i < m; i ++ ){ while (j >= 0 && p[j + 1] != p[i]) j = ne[j]; if (p[j + 1] == p[i]) j ++ ; ne[i] = j; } for (int i = 0, j = -1; i < n; i ++ ){ while (j != -1 && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j ++ ; if (j == m - 1){ cout << i - j << ' '; j = ne[j]; } } return 0; }
Trie
#include <iostream> using namespace std; const int N = 100010; int son[N][26], cnt[N], idx; char str[N]; void insert(char *str){ int p = 0; for (int i = 0; str[i]; i ++ ){ int u = str[i] - 'a'; if (!son[p][u]) son[p][u] = ++ idx; p = son[p][u]; } cnt[p] ++ ; } int query(char *str){ int p = 0; for (int i = 0; str[i]; i ++ ){ int u = str[i] - 'a'; if (!son[p][u]) return 0; p = son[p][u]; } return cnt[p]; } int main(){ int n; scanf("%d", &n); while (n -- ){ char op[2]; scanf("%s%s", op, str); if (*op == 'I') insert(str); else printf("%d\n", query(str)); } return 0; }
最大异或对
#include <iostream> #include <algorithm> using namespace std; const int N = 100010, M = 3100010; int n; int a[N], son[M][2], idx; void insert(int x){ int p = 0; for (int i = 30; i >= 0; i -- ){ int &s = son[p][x >> i & 1]; if (!s) s = ++ idx; p = s; } } int search(int x){ int p = 0, res = 0; for (int i = 30; i >= 0; i -- ){ int s = x >> i & 1; if (son[p][!s]){ res += 1 << i; p = son[p][!s]; } else p = son[p][s]; } return res; } int main(){ scanf("%d", &n); for (int i = 0; i < n; i ++ ){ scanf("%d", &a[i]); insert(a[i]); } int res = 0; for (int i = 0; i < n; i ++ ) res = max(res, search(a[i])); printf("%d\n", res); return 0; }
并查集
#include <iostream> using namespace std; const int N = 100010; int p[N]; int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x]; } int main(){ int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) p[i] = i; while (m -- ){ char op[2]; int a, b; scanf("%s%d%d", op, &a, &b); if (*op == 'M') p[find(a)] = find(b); else{ if (find(a) == find(b)) puts("Yes"); else puts("No"); } } return 0; }
连通块中点的数量
#include <iostream> using namespace std; const int N = 100010; int n, m; int p[N], cnt[N]; int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x]; } int main(){ cin >> n >> m; for (int i = 1; i <= n; i ++ ){ p[i] = i; cnt[i] = 1; } while (m -- ){ string op; int a, b; cin >> op; if (op == "C"){ cin >> a >> b; a = find(a), b = find(b); if (a != b){ p[a] = b; cnt[b] += cnt[a]; } } else if (op == "Q1"){ cin >> a >> b; if (find(a) == find(b)) puts("Yes"); else puts("No"); } else{ cin >> a; cout << cnt[find(a)] << endl; } } return 0; }
堆排序
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n, m; int h[N], cnt; void down(int u){ int t = u; if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t){ swap(h[u], h[t]); down(t); } } int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]); cnt = n; for (int i = n / 2; i; i -- ) down(i); while (m -- ){ printf("%d ", h[1]); h[1] = h[cnt -- ]; down(1); } puts(""); return 0; }
模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 x xx；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 k kk 个插入的数；
C k x，修改第 k kk 个插入的数，将其变为 x xx；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
#include<iostream> #include<algorithm> using namespace std; const int N=1e5+10; int h[N]; //堆 int ph[N]; //存放第k个插入点的下标 int hp[N]; //存放堆中点的插入次序 int cur_size; //size 记录的是堆当前的数据多少 //这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系 //之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序 //从而我们需要对应到原先第K个堆中元素 //如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 //h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响 void heap_swap(int u,int v){ swap(h[u],h[v]); swap(hp[u],hp[v]); swap(ph[hp[u]],ph[hp[v]]); } void down(int u){ int t=u; if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2; if(u*2+1<=cur_size&&h[t]>h[u*2+1]) t=u*2+1; if(u!=t){ heap_swap(u,t); down(t); } } void up(int u){ if(u/2>0&&h[u]<h[u/2]) { heap_swap(u,u/2); up(u>>1); } } int main(){ int n; cin>>n; int m=0; //m用来记录插入的数的个数 //注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少 //对应上文 m即是hp中应该存的值 while(n--){ string op; int k,x; cin>>op; if(op=="I"){ cin>>x; m++; h[++cur_size]=x; ph[m]=cur_size; hp[cur_size]=m; //down(size); up(cur_size); } else if(op=="PM") cout<<h[1]<<endl; else if(op=="DM"){ heap_swap(1,cur_size); cur_size--; down(1); } else if(op=="D"){ cin>>k; int u=ph[k];//这里一定要用u=ph[k]保存第k个插入点的下标 heap_swap(u,cur_size);//因为在此处heap_swap操作后ph[k]的值已经发生 cur_size--;//如果在up,down操作中仍然使用ph[k]作为参数就会发生错误 up(u); down(u); } else if(op=="C"){ cin>>k>>x; h[ph[k]]=x;//此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以 down(ph[k]);//所以可直接传入ph[k]作为参数 up(ph[k]); } } return 0; }
字符串哈希
#include <iostream> #include <algorithm> using namespace std; typedef 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] * P; } while (m -- ){ int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2); if (get(l1, r1) == get(l2, r2)) puts("Yes"); else puts("No"); } return 0; }
搜索与图论
全排列
#include <iostream> using namespace std; const int N = 10; int n; int path[N]; void dfs(int u, int state){ if (u == n){ for (int i = 0; i < n; i ++ ) printf("%d ", path[i]); puts(""); return; } for (int i = 0; i < n; i ++ ) if (!(state >> i & 1)){ path[u] = i + 1; dfs(u + 1, state + (1 << i)); } } int main(){ scanf("%d", &n); dfs(0, 0); return 0; }
组合型枚举
#include<iostream> #include<vector> using namespace std; bool chosen[30]; int n, m; vector<int> nums; void dfs(int pos) { if (nums.size() > m || nums.size() + n - pos + 1 < m) return; if (nums.size() == m) { for (int i = 0; i < nums.size(); i++) cout << nums[i]<<" "; cout << endl; return; } nums.push_back(pos); dfs(pos + 1); nums.pop_back(); dfs(pos + 1); } int main() { cin >> n >> m; dfs(1); return 0; }
八皇后
#include <iostream> using namespace std; const int N = 20; int n; char g[N][N]; bool col[N], dg[N], udg[N]; void dfs(int u){ if (u == n){ for (int i = 0; i < n; i ++ ) puts(g[i]); puts(""); return; } for (int i = 0; i < n; i ++ ) if (!col[i] && !dg[u + i] && !udg[n - u + i]){ g[u][i] = 'Q'; col[i] = dg[u + i] = udg[n - u + i] = true; dfs(u + 1); col[i] = dg[u + i] = udg[n - u + i] = false; g[u][i] = '.'; } } int main(){ cin >> n; for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) g[i][j] = '.'; dfs(0); return 0; }
走迷宫
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; typedef pair<int, int> PII; const int N = 110; int n, m; int g[N][N], d[N][N]; int bfs(){ queue<PII> q; memset(d, -1, sizeof d); d[0][0] = 0; q.push({0, 0}); int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; while (q.size()){ auto t = q.front(); q.pop(); for (int i = 0; i < 4; i ++ ){ int x = t.first + dx[i], y = t.second + dy[i]; if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){ d[x][y] = d[t.first][t.second] + 1; q.push({x, y}); } } } return d[n - 1][m - 1]; } int main(){ cin >> n >> m; for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) cin >> g[i][j]; cout << bfs() << endl; return 0; }
树的重心
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
#include<iostream> #include<vector> #include<queue> using namespace std; const int N = 100005; vector<int> g[N]; int n; int st[N]; int ans = N; int dfs(int u) { st[u] = true; int sum = 1, res = 0; for (auto node : g[u]) { if (!st[node]) { int s = dfs(node); res = max(res, s); sum += s; } } res = max(res, n - sum); ans = min(ans, res); return sum; } int main() { cin >> n; for(int i=0;i<n-1;i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } dfs(1); cout << ans; return 0; }
拓扑排序
#include<iostream> #include<vector> #include<queue> using namespace std; const int N = 100010; int n, m; vector<int> graph[N]; vector<int> path; int ind[N];//入度 bool toposort() { int indnode = 0; queue<int> q; for (int i = 1; i <= n; i++) { if (ind[i] == 0) { indnode = i; q.push(i); } } if (indnode == 0) return false; while (!q.empty()) { int cur = q.front(); q.pop(); path.push_back(cur); for (auto node : graph[cur]) { ind[node]--; if (ind[node] == 0) q.push(node); } } for (int i = 1; i <= n; i++) if (ind[i] > 0) return false; return true; } int main() { cin >> n >> m; while (m--) { int x, y; cin >> x >> y; graph[x].push_back(y); ind[y]++; } if (toposort()) { for (auto node : path) cout << node << " "; } else cout << -1; return 0; }
八数码
#include<iostream> #include<queue> #include<vector> #include<map> using namespace std; typedef pair<int, vector<int> > PIV; priority_queue<PIV, vector<PIV>,greater<PIV> > q; map<vector<int>, string> path; map<vector<int>, int> dist; vector<int> endst = { 1,2,3,4,5,6,7,8,0 }; int pred(vector<int> state,int steps) { int res = 0; for (int i = 0; i < 9; i++)//这里1~8对应的下标为0~7 if (state[i] != 0) { int t = state[i] - 1;//对应下标 res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);//曼哈顿距离 } return res+steps;//返回总曼哈顿距离 } int mfind(vector<int> state) { for (int i = 0; i < 9; i++) if (state[i] == 0) return i; return -1; } void bfs() { while (!q.empty()) { PIV cur = q.top(); q.pop(); if (cur.second ==endst) { cout << path[cur.second]; return; } int pos = mfind(cur.second); if (pos / 3 == 0) { vector<int> newc = cur.second; swap(newc[pos], newc[pos + 3]); if (path.count(newc) == 0||dist[newc]>dist[cur.second]+1) { path[newc] = path[cur.second] + "d"; dist[newc] = dist[cur.second] + 1; q.push({pred(newc,dist[newc]),newc }); } } if (pos / 3 == 1) { vector<int> newc = cur.second; swap(newc[pos], newc[pos + 3]); if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) { path[newc] = path[cur.second] + "d"; dist[newc] = dist[cur.second] + 1; q.push({ pred(newc,dist[newc]),newc }); } newc = cur.second; swap(newc[pos], newc[pos - 3]); if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) { path[newc] = path[cur.second] + "u"; dist[newc] = dist[cur.second] + 1; q.push({ pred(newc,dist[newc]),newc }); } } if (pos / 3 == 2) { vector<int> newc = cur.second; swap(newc[pos], newc[pos - 3]); if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) { path[newc] = path[cur.second] + "u"; dist[newc] = dist[cur.second] + 1; q.push({ pred(newc,dist[newc]),newc }); } } if (pos % 3 == 0) { vector<int> newc = cur.second; swap(newc[pos], newc[pos + 1]); if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) { path[newc] = path[cur.second] + "r"; dist[newc] = dist[cur.second] + 1; q.push({ pred(newc,dist[newc]),newc }); } } if (pos % 3 == 1) { vector<int> newc = cur.second; swap(newc[pos], newc[pos + 1]); if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) { path[newc] = path[cur.second] + "r"; dist[newc] = dist[cur.second] + 1; q.push({ pred(newc,dist[newc]),newc }); } newc = cur.second; swap(newc[pos], newc[pos - 1]); if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) { path[newc] = path[cur.second] + "l"; dist[newc] = dist[cur.second] + 1; q.push({ pred(newc,dist[newc]),newc }); } } if (pos % 3 == 2) { vector<int> newc = cur.second; swap(newc[pos], newc[pos - 1]); if (path.count(newc) == 0 || dist[newc] > dist[cur.second] + 1) { path[newc] = path[cur.second] + "l"; dist[newc] = dist[cur.second] + 1; q.push({ pred(newc,dist[newc]),newc }); } } } } int nixu(vector<int> state) { int res = 0; for (int i = 0; i < 9; i++) { for (int j = i; j < 9; j++) if (state[j] < state[i] && state[j] != 0) res++; } return res; } int main() { vector<char> ch(9); for (int i = 0; i < 9; i++) cin >> ch[i]; vector<int> init(9); for (int i = 0; i < 9; i++) { if (ch[i] == 'x') init[i] = 0; else init[i] = ch[i] - '0'; } if (nixu(init) % 2 == 0) { q.push({pred(init,0),init }); dist[init] = 0; path[init] = ""; bfs(); return 0; } else { cout << "unsolvable"; return 0; } }
解数独
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 9, M = 1 << N; int ones[M], map[M]; int row[N], col[N], cell[3][3]; char str[100]; void init(){ for (int i = 0; i < N; i ++ ) row[i] = col[i] = (1 << N) - 1; for (int i = 0; i < 3; i ++ ) for (int j = 0; j < 3; j ++ ) cell[i][j] = (1 << N) - 1; } void draw(int x, int y, int t, bool is_set){ if (is_set) str[x * N + y] = '1' + t; else str[x * N + y] = '.'; int v = 1 << t; if (!is_set) v = -v; row[x] -= v; col[y] -= v; cell[x / 3][y / 3] -= v; } int lowbit(int x){ return x & -x; } int get(int x, int y){ return row[x] & col[y] & cell[x / 3][y / 3]; } bool dfs(int cnt){ if (!cnt) return true; int minv = 10; int x, y; for (int i = 0; i < N; i ++ ) for (int j = 0; j < N; j ++ ) if (str[i * N + j] == '.'){ int state = get(i, j); if (ones[state] < minv){ minv = ones[state]; x = i, y = j; } } int state = get(x, y); for (int i = state; i; i -= lowbit(i)){ int t = map[lowbit(i)]; draw(x, y, t, true); if (dfs(cnt - 1)) return true; draw(x, y, t, false); } return false; } int main(){ for (int i = 0; i < N; i ++ ) map[1 << i] = i; for (int i = 0; i < 1 << N; i ++ ) for (int j = 0; j < N; j ++ ) ones[i] += i >> j & 1; while (cin >> str, str[0] != 'e'){ init(); int cnt = 0; for (int i = 0, k = 0; i < N; i ++ ) for (int j = 0; j < N; j ++, k ++ ) if (str[k] != '.') { int t = str[k] - '1'; draw(i, j, t, true); } else cnt ++ ; dfs(cnt); puts(str); } return 0; }
堆优化Dijkstra
#include<iostream> #include<cstring> #include<vector> #include<queue> using namespace std; int t,c,ts,te; int ans=0; typedef pair<int,int> PII; priority_queue<PII,vector<PII>,greater<PII> > q; int st[2505]; int dist[2505]; vector<PII> g[2505]; void dijkstra(){ memset(dist,0x3f3f3f3f,sizeof dist); dist[ts]=0; q.push({0,ts}); while(!q.empty()){ auto [d,cur]=q.top(); q.pop(); if (st[cur]) continue; st[cur]=1; for(auto node:g[cur]){ auto [d,next]=node; if (d+dist[cur]<dist[next]){ dist[next]=d+dist[cur]; q.push({dist[next],next}); } } } } int main(){ cin>>t>>c>>ts>>te; for(int i=1;i<=c;i++){ int rs,re,ci; cin>>rs>>re>>ci; g[rs].push_back({ci,re}); g[re].push_back({ci,rs}); } dijkstra(); cout<<dist[te]; }
SPFA
#include<iostream> #include<cstring> #include<vector> #include<queue> using namespace std; int n, m; const int N = 100005; int dist[N]; typedef pair<int, int> PII;//first表示指向点，second表示距离 vector<PII> graph[N]; void spfa() { dist[1] = 0; queue<int> q; q.push(1); while (!q.empty()) { int curnode = q.front(); q.pop(); for (auto node : graph[curnode]) { if (dist[node.first] > dist[curnode] + node.second) { dist[node.first] = dist[curnode] + node.second; q.push(node.first); } } } } int main() { cin >> n >> m; while (m--) { int x, y, z; cin >> x >> y >> z; graph[x].push_back({ y,z }); } memset(dist, 0x3f3f3f3f, sizeof dist); spfa(); if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible"; else cout << dist[n]; return 0; }
