for (int i = 0; i < n - 1; i ++ ) { int t = -1; // 在还未确定最短路的点中，寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。 for (int i = 0; i < n; i ++ ) { memcpy(backup,dist,sizeof dist); for (int j = 0; j < m; j ++ ) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[b] > backup[a] + w) dist[b] = backup[a] + w; } }
for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入 { q.push(j); st[j] = true; } } } }
if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
floyd
1 2 3 4 5 6 7 8 9 10 11 12 13 14
初始化： 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]表示a到b的最短距离 void 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]); }
int n; // n表示点数 int h[N], e[M], ne[M], idx; // 邻接表存储图 int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色
// 参数：u表示当前节点，c表示当前点的颜色 bool dfs(int u, int c) { color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (color[j] == -1) { if (!dfs(j, !c)) return false; } else if (color[j] == c) return false; }
return true; }
bool check() { memset(color, -1, sizeof color); bool flag = true; for (int i = 1; i <= n; i ++ ) if (color[i] == -1) if (!dfs(i, 0)) { flag = false; break; } return flag; }
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); }
归并排序算法模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
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]; }
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }
1
### 浮点数二分模板
bool check(double x) {/* … */} // 检查x是否满足某种性质
double bsearch_3(double l, double r) { const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }
// 二分求出x对应的离散化的值 int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n }
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);
int son[N][26], cnt[N], idx; // 0号点既是根节点，又是空节点 // son[][]存储树中每个节点的子节点 // cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串 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]; }
// 交换两个点，及其映射关系 void heap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); }
void down(int u) { int t = u; if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { heap_swap(u, t); down(t); } }
void up(int u) { while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u >>= 1; } }
// O(n)建堆 for (int i = n / 2; i; i -- ) down(i);
一般哈希 （数组）
拉链法 int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数 void insert(int x) {
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在 bool find(int x) {
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
(2) 开放寻址法 （数组） int h[N];
// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
1
### 字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低 小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL; ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化 p[0] = 1; for (int i = 1; i <= n; i ++ ) { h[i] = h[i - 1] * P + str[i]; p[i] = p[i - 1] * P; }
// C = A + B, A >= 0, B >= 0 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; }
高精度减法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// C = A - B, 满足A >= B, A >= 0, B >= 0 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; }
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; }
高精度除法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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; }
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); } // 先排再递归
归并排序算法模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
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]; } //先递归再排序
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： // 找右边界 int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } return l; } // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用： //找左边界 int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }
浮点数二分算法模板
1 2 3 4 5 6 7 8 9 10 11 12 13
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r) { const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求 一般精确到题目要求后两位 while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }
reverse(a + 1, a + n + 1); 2.2 unique去重 返回去重（只去掉相邻的相同元素）之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。
把一个vector去重：
int m = unique(a.begin(), a.end()) – a.begin(); a.erase（unique(a.begin(), a.end())，a.end()） 把一个数组去重，元素存放在下标0 ~ m：
int m = unique(a + 1, a + n + 1) – (a + 1); 2.3 random_shuffle随机打乱 用法与reverse相同。 Srand (time(0)); 随机种子 <ctime>头文件 2.4 sort 对两个迭代器（或指针）指定的部分进行快速排序（从小到大）。可以在第三个参数传入定义大小比较的函数，或者重载“小于号”运算符。
把一个int数组（元素存放在下标1 ~ n）从大到小排序，传入比较函数：
int a[MAX_SIZE]; bool cmp(int a, int b) { return a > b; } sort(a + 1, a + n + 1, cmp);
sort(a.begin(),a.end(),greater<int>())
把自定义的结构体vector排序，重载“小于号”运算符：
struct Rec { int x, y; bool operator <(const Rec &t) const { return x < a.x; }
int main(){ int n; int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
while(cin >> n, n ){ memset(m, 0, sizeof m); int d = 1, x = 0, y = 0; int cnt = 0; // 表示改变方向次数 int res = 1; // 回形当前圈数 for (int i = 0; i < n * n; i ++){ int a = x + dx[d], b = y + dy[d]; m[x][y] = res;
if (a < 0 || a >= n || b < 0 || b >= n || m[a][b]){ d = (d + 1) % 4; a = x + dx[d], b = y + dy[d]; cnt ++; if (!(cnt % 4)) res ++; } x = a, y = b; }
for (int i = 0; i < n; i ++){ for (int j = 0; j < n; j ++) cout << m[i][j] << ' '; cout << endl; } cout << endl; }