栈

经典场景：

  1. 括号画家

一排括号序列，其中包含小括号 ( )、中括号 [ ] 和大括号 { }，总长度为 N。现在求最长合理的字串长度。
这道题是栈的经典题，先把各类括号的左半边入栈，然后遇到右半边时，弹栈时更新答案。如果遇到不匹配的地方，需要重新设置下次合理字串的起点。有一个小技巧是对于字符配对，可以创建一个128长度的整形数组。

  1. #include<cstdio>
  2. #include<cmath>
  3. using namespace std;
  5. const int N = 1e5 + 10;
  7. char s[N];
  8. int stk[N], top = 0;
  9. char mp[128];
  11. int main() {
  12.     scanf("%s", s);
  14.     // "([{->123"
  15.     mp[')'] = '(';
  16.     mp[']'] = '[';
  17.     mp['}'] = '{';
  18.     int ans = 0;
  19.     stk[0] = -1; // 特殊处理：当完全匹配时，长度应为i+1
  20.     for(int i = 0; s[i]; i++) {
  21.         if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
  22.             stk[++top] = i;
  23.         }
  24.         else if (top && s[stk[top]] == mp[(int)s[i]]) {
  25.             top--;
  26.             ans = max(ans, i - stk[top]); // 匹配成功，更新最大长度
  27.         }
  28.         else {
  29.             top = 0;
  30.             stk[top] = i; // 特殊处理：如果匹配错误，则将栈顶作为新的起点
  31.         }
  32.     }
  34.     printf("%d\n", ans);
  36.     return 0;
  37. }
  1. 表达式计算

给你一个表达式，类似于-(2+2)^4-3*5/(2-4)，输出答案。
由于这道题存在括号，一个通用的做法是将表达式转化为后缀表达式，然后计算。总体思路是维护一个数栈，一个操作符栈。这道题需要注意的有2点，第一点是负数的处理，直接出现负号，我们可以通过向数栈中加0处理，第二点是在处理+-这种低优先级运算符时，需要先弹栈计算。

  1. #include<cstdio>
  2. #include<cmath>
  3. using namespace std;
  5. const int N = 1e5 + 10;
  7. char s[N];
  8. int stk_num[N], num_top = 0, stk_op[N], op_top = 0;
  10. int cal(int a, int b, char c) {
  11.     if(c == '+') return a + b;
  12.     else if(c == '-') return a - b;
  13.     else if(c == '*') return a * b;
  14.     else if(c == '^') return pow(a, b);
  15.     return a / b;
  16. }
  18. int main() {
  19.     scanf("%s", s);
  21.     // "(+-*/^" -> "012345"
  23.     for(int i = 0; s[i]; i++) {
  24.         char c = s[i];
  26.         if(c >= '0' && c <= '9') { // 得出数字
  27.             int num = 0;
  28.             while(s[i] && s[i] >= '0' && s[i] <= '9') {
  29.                 num = num * 10 + s[i] - '0';
  30.                 i++;
  31.             }
  32.             i--;
  33.             stk_num[++num_top] = num;
  34.         }
  35.         else if(c == ')') {
  36.             while(num_top > 1 && op_top && stk_op[op_top] != '(') { // 计算括号内的表达式
  37.                 int a = stk_num[num_top--];
  38.                 int b = stk_num[num_top--];
  39.                 char o = stk_op[op_top--];
  40.                 //printf("%d %c %d == %d\n", b, o, a, cal(b, a, o));
  41.                 stk_num[++num_top] = cal(b, a, o);
  42.             }
  43.             op_top--;
  44.         }
  45.         else if(c == '*' || c == '/' || c == '^' || c == '(') {
  46.             stk_op[++op_top] = c;
  47.         }
  48.         else {
  49.             if(c == '-' && !(s[i - 1] >= '0' && s[i - 1] <= '9') && s[i - 1] != ')') { // 处理负数情况
  50.                 stk_num[++num_top] = 0; 
  51.             }
  52.             while(num_top > 1 && op_top && stk_op[op_top] != '(') {
  53.                 int a = stk_num[num_top--];
  54.                 int b = stk_num[num_top--];
  55.                 char o = stk_op[op_top--];
  56.                 //printf("%d %c %d == %d\n", b, o, a, cal(b, a, o));
  57.                 stk_num[++num_top] = cal(b, a, o);
  58.             }
  59.             stk_op[++op_top] = c;
  60.         }
  61.     }
  63.     while(op_top && num_top > 1) {
  64.         int a = stk_num[num_top--];
  65.         int b = stk_num[num_top--];
  66.         char o = stk_op[op_top--];
  67.         stk_num[++num_top] = cal(b, a, o);
  68.         //printf("%d %c %d == %d\n", b, o, a, cal(b, a, o));
  69.     }
  71.     printf("%d\n", stk_num[num_top]);
  73.     return 0;
  74. }
  1. 双栈排序

给出一个长度为N的序列（1~N，N<=1000），能否利用2个栈对序列进行排序，将第一个栈的入栈出栈操作记为ab，将第二个栈的入栈出栈操作记为cd，求字典序最小的操作序列。
这道题比较难切入，如果用暴力搜索，4^1000会超时。但是如何能判定能否用双栈进行排序，以及如何排序就能难。实际上，我们首先需要将这个序列中的数字划分成两部分，一部分通过栈A完成排序，另一部分通过栈B完成排序，因为假设数据可以通过一个栈进行排序，要想将其中的元素进行升序或降序，入栈和出栈的操作顺序都是唯一的。那如何判断哪些数字该划分为一起。这里就需要用到离散数学中的一个知识点：如果一个栈不可以对一个序列进行排序，那么对于i, j，满足i<j，存在k(i < j < k)，满足a[k] < a[i] < a[j]。这样，因为a[k]的存在，a[i]必须先保留在栈中，且a[i]因为a[j]无法弹出了。通过这种方式将数据划分两部分，可能会存在矛盾，比如a 不能和 b 一起, a 不能和 c一起， c又不能和b一起，这样也无法通过两个栈完成排序。这个问题对应到图论中的模型，就是通过染色法来判断一个图是否为二分图。如果是二分图，那么就可以用两个栈来模拟答案，如果不是二分图，则无解。

  1. #include<cstdio>
  2. #include<cmath>
  3. #include<cstring>
  4. using namespace std;
  6. const int N = 1010, M = N * N;
  8. int s1[N], s2[N], t1, t2;
  9. int color[N];
  10. int h[N], e[M], ne[M], idx;
  11. int n, a[N], f[N];
  13. void add(int a, int b) {
  14.     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
  15. }
  17. bool dfs(int u, int c) {
  18.     color[u] = c;
  20.     for(int i = h[u]; ~i; i = ne[i]) {
  21.         int j = e[i];
  22.         if(color[j] == c) {
  23.             return false;
  24.         }
  25.         if(color[j] == -1 && !dfs(j, 1 - c)) {
  26.             return false;
  27.         }
  28.     }
  30.     return true;
  31. }
  33. int main() {
  34.     scanf("%d", &n);
  35.     for(int i = 0; i < n; i++) {
  36.         scanf("%d", &a[i]);
  37.     }
  39.     f[n] = n + 1;
  40.     for(int i = n - 1; i >= 0; i--) {
  41.         f[i] = min(f[i + 1], a[i]);
  42.     }
  44.     // 判断两个数字能否输入一个栈，不能则连边
  45.     memset(h, -1, sizeof h);
  46.     idx = 0;
  48.     // 根据 i<j<k, 存在k使得a[k]<a[i]<a[j] 建图
  49.     for(int i = 0; i < n; i++) {
  50.         for(int j = i + 1; j < n; j++) {
  51.             if(a[i] < a[j] && a[i] > f[j + 1]) {
  52.                 add(i, j);
  53.                 add(j, i);
  54.             }
  55.         }
  56.     }
  58.     // 用染色法判断构造的图是否为二分图，用颜色数组表示每个点应该属于哪个栈
  59.     bool ok = true;
  60.     memset(color, -1, sizeof color);
  61.     for(int i = 0; i < n; i++) {
  62.         if(color[i] == -1 && !dfs(i, 0)) {
  63.             ok = false;
  64.             break;
  65.         }
  66.     }
  68.     // 如果不是二分图，则无法用两个栈来完成升序排序
  69.     if(!ok) {
  70.         printf("0\n");
  71.         return 0;
  72.     }
  74.     // 用两个栈来模拟答案
  75.     t1 = t2 = 0;
  76.     int num = 1;
  77.     for(int i = 0; i < n; i++) { // 将第一个栈的操作放在第二个栈之前，保证操作字典序最小
  78.         if(color[i] == 0) {
  79.             s1[++t1] = a[i];
  80.             printf("a ");
  81.         }
  82.         else {
  83.             s2[++t2] = a[i];
  84.             printf("c ");
  85.         }
  87.         while(true) {
  88.             bool flag = false;
  89.             while(t1 && s1[t1] == num) {
  90.                 printf("b ");
  91.                 t1--;
  92.                 num++;
  93.                 flag = true;
  94.             }
  95.             while(t2 && s2[t2] == num) {
  96.                 printf("d ");
  97.                 t2--;
  98.                 num++;
  99.                 flag = true;
  100.             }
  101.             if(!flag) {
  102.                 break;
  103.             }
  104.         }
  106.     }
  108.     printf("\n");
  110.     return 0;
  111. }

单调栈

定义：当后面的数据需要确定“边界”时，发现并不是所有的数据都会被用到，比如只有比自己小的数据才有用，这种情况就可以用单调栈来优化判断，将O(n2)判断过程优化为O(n)，及时地不可能的候选项排除掉。

经典例题

  1. 直方图中最大的矩形 ```cpp // 思路：枚举以每个长方形为最低点的最大面积 // 优化：寻找每个长方形的左右边界的过程用单调栈优化

    include

    include

    using namespace std;

typedef long long int64;

const int N = 1e5 + 10;

int l[N], r[N], a[N], st[N], tt = 0;

int main() { int n; while(true) { scanf(“%d”, &n); if(!n) { break; }

  1.     for(int i = 0; i < n; i++) {
  2.         scanf("%d", &a[i]);
  3.     }
  5.     tt = -1;
  6.     st[++tt] = -1;
  7.     for(int i = 0; i < n; i++) {
  8.         while(tt && a[st[tt]] >= a[i]) tt--;
  9.         l[i] = st[tt]; // 左边界（取不到）
  10.         st[++tt] = i;
  11.     }
  13.     tt = -1;
  14.     st[++tt] = n;
  15.     for(int i = n - 1; i >= 0; i--) {
  16.         while(tt && a[st[tt]] >= a[i]) tt--;
  17.         r[i] = st[tt]; // 右边界（取不到）
  18.         st[++tt] = i;
  19.     }
  21.     int64 ans = 0;
  22.     for(int i = 0; i < n; i++) {
  23.         ans = max(ans, 1ll * a[i] * (r[i] - l[i] - 1));
  24.     }
  26.     printf("%lld\n", ans);
  27. }
  28. return 0;

}

  2. 2. 城市游戏
  4. 本质是求01矩形中，全1子矩阵的最大面积。这道题是上一题的拓展，我们可以对每一行求一遍直方图中的最大面积，更新答案即可。
  5. ```cpp
  6. #include<cstdio>
  7. #include<iostream>
  8. #include<cstring>
  9. using namespace std;
  11. typedef long long ll;
  13. const int N = 1010;
  15. int a[N][N];
  16. int l[N], r[N], h[N], stk[N], top;
  18. int main() {
  19.     int n, m;
  20.     scanf("%d%d", &n, &m);
  22.     string s;
  23.     getline(cin, s);
  24.     for(int i = 1; i <= n; i++) {
  25.         getline(cin, s);
  26.         //cout << s << endl;
  27.         for(int j = 1, k = 1; j <= s.size(); j++) {
  28.             if(s[j - 1] == 'R') {
  29.                 a[i][k++] = 0;
  30.             }
  31.             else if(s[j - 1] == 'F') {
  32.                 a[i][k++] = 1;
  33.             }
  34.         }
  35.     }
  37.     memset(h, 0, sizeof h);
  38.     ll ans = 0;
  39.     for(int i = 1; i <= n; i++) {
  40.         for(int j = 1; j <= m; j++) {
  41.             if(a[i][j] == 1) {
  42.                 h[j]++;
  43.             }
  44.             else {
  45.                 h[j] = 0;
  46.             }
  47.         }
  49.         top = 0;
  50.         stk[0] = 0;
  51.         for(int j = 1; j <= m; j++) {
  52.             while(top && h[stk[top]] >= h[j]) top--;
  53.             l[j] = stk[top];
  54.             stk[++top] = j;
  55.         }
  57.         top = 0;
  58.         stk[0] = m + 1;
  59.         for(int j = m; j >= 1; j--) {
  60.             while(top && h[stk[top]] >= h[j]) top--;
  61.             r[j] = stk[top];
  62.             stk[++top] = j;
  63.         }
  65.         for(int j = 1; j <= m; j++) {
  66.             ans = max(ans, 1LL * (r[j] - l[j] - 1) * h[j]);
  67.         }
  68.     }
  70.     printf("%lld\n", 3 * ans);
  72.     return 0;
  73. }

单调队列

定义：和单调栈一样，维护可能的候选项，即使排除不可能的选项。

经典场景

  1. 蚯蚓：

有很多蚯蚓，每秒钟将一个最长的蚯蚓一分为二，其他的蚯蚓增加一个非负整数q。由于所有元素都需要变大，而互相之间的大小关系并没有发生变化，这时可以使用一个偏移量，表示所有元素的增大量，而别切开的蚯蚓减去q后再放回最大堆即可。值得注意的是，元素出队时需要加上偏移量还原真实值，入队时需要减去偏移量，进行还原。
如果单纯地用优先队列，有多次入队和出队操作，每次都要消耗O(logn)的时间，在本题中有一个独特的性质，蚯蚓都是按等比例切分。如果切分前蚯蚓A长于蚯蚓B，则切分后对应的两段A也比B长，因此可以维护3个单调队列，分别存放原始降序排列的元素（队列1），切分后较长的一段（队列2），切分后较短的一段（队列3），这样整体最大值就是三个队列的队头的最大值，而切分后的两端一定小于之前所有切分的情况，直接添加在队列的最后即可，时间复杂度由O(logn)降为O(1)。

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  5. const int N = 1e8 + 10;
  7. int a[N], q1[N], q2[N], q3[N];
  8. int hh1, hh2, hh3, tt1, tt2, tt3;
  10. int get_max() {
  11.     int v1 = hh1 <= tt1 ? q1[hh1] : -1e9;
  12.     int v2 = hh2 <= tt2 ? q2[hh2] : -1e9;
  13.     int v3 = hh3 <= tt3 ? q3[hh3] : -1e9;
  14.     int x = max(v1, max(v2, v3));
  15.     //printf("x: %d\n", x);
  16.     if(x == v2) {
  17.         hh2++;
  18.     }
  19.     else if(x == v3) {
  20.         hh3++;
  21.     }
  22.     else {
  23.         hh1++;
  24.     }
  26.     return x;
  27. }
  29. int main() {
  30.     int n, m, q, u, v, t;
  31.     scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
  33.     hh1 = hh2 = hh3 = 0;
  34.     tt1 = tt2 = tt3 = -1;
  35.     for(int i = 0; i < n; i++) {
  36.         scanf("%d", &a[i]);
  37.     }
  39.     sort(a, a + n);
  40.     for(int i = n - 1; i >= 0; i--) {
  41.         q1[++tt1] = a[i];
  42.     }
  44.     int diff = 0;
  45.     for(int i = 1; i <= m; i++) {
  46.         int x = get_max();
  47.         x += diff;
  48.         if(i % t == 0) {
  49.             printf("%d ", x);
  50.         }
  51.         int half1 = 1.0 * u / v * x;
  52.         int half2 = x - half1;
  53.         q2[++tt2] = max(half1 - diff - q, half2 - diff - q);
  54.         q3[++tt3] = min(half1 - diff - q, half2 - diff - q);
  55.         diff += q;
  56.     }
  57.     printf("\n");
  59.     for(int i = 1; i <= n + m; i++) {
  60.         int x = get_max();
  61.         //printf("i: %d, x: %d\n", i, x);
  62.         if(i % t == 0) {
  63.             printf("%d ", x + diff);
  64.         }
  65.     }
  66.     printf("\n");
  68.     return 0;
  69. }
  1. 最大子序列和：

求一个数组中连续子序列的和的最大值，子序列长度不超过m。思路是通过单调队列维护候选项，队头是最小值，但是最远，队尾是最大值，但是最近，因为后面队头的元素因为距离太远会失效，所以可以通过单调队列维护。

  1. #include<cstdio>
  2. #include<cmath>
  3. using namespace std;
  5. const int N = 3e5 + 10;
  7. int q[N], hh, tt;
  8. int a[N], s[N];
  10. int main() {
  11.     int n, m;
  12.     scanf("%d%d", &n, &m);
  14.     for(int i = 1; i <= n; i++) {
  15.         scanf("%d", &a[i]);
  16.     }
  18.     for(int i = 1; i <= n; i++) {
  19.         s[i] = s[i - 1] + a[i];
  20.     }
  22.     hh = 0, tt = -1;
  23.     q[++tt] = 0;
  25.     int ans = -1e9;
  26.     for(int i = 1; i <= n; i++) {
  27.         if(hh <= tt && i - q[hh] > m) hh++; // m不小于1，所以第一次不会发生弹出的情况
  28.         ans = max(ans, s[i] - s[q[hh]]);
  29.         while(hh <= tt && s[q[tt]] >= s[i]) tt--;
  30.         q[++tt] = i;
  31.     }
  33.     printf("%d\n", ans);
  35.     return 0;
  36. }
  1. 滑动窗口

滑动窗口是单调队列最经典的应用，在这总结一下单调队列应用时的几个常见的操作：将不合法的元素出队，入队时先将无效选项弹出，入队。

  1. #include<iostream>
  2. using namespace std;
  4. const int N = 1e6 + 10;
  6. int a[N];
  7. int q[N], hh, tt;
  9. int main() {
  10.     int n, k;
  11.     scanf("%d%d", &n, &k);
  13.     for(int i = 0; i < n; i++) {
  14.         scanf("%d", &a[i]);
  15.     }
  17.     hh = 0, tt = -1;
  18.     for(int i = 0; i < n; i++) {
  19.         if(hh <= tt && q[hh] < i - k + 1) hh++;
  20.         while(hh <= tt && a[q[tt]] >= a[i]) tt--;
  21.         q[++tt] = i;
  22.         if(i >= k - 1) {
  23.             printf("%d ", a[q[hh]]);
  24.         }
  25.     }
  26.     printf("\n");
  28.     hh = 0, tt = -1;
  29.     for(int i = 0; i < n; i++) {
  30.         if(hh <= tt && q[hh] < i - k + 1) hh++;
  31.         while(hh <= tt && a[q[tt]] <= a[i]) tt--;
  32.         q[++tt] = i;
  33.         if(i >= k - 1) {
  34.             printf("%d ", a[q[hh]]);
  35.         }
  36.     }
  37.     printf("\n");
  39.     return 0;
  40. }

链表

定义：链式的结构，可以找到前一个结点，后一个结点，并且能很方便地删除结点，在中间插入结点。

经典场景：

  1. 邻值查找

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 A[i]，求：MIN1≤j以及令上式取到最小值的 j（记为 p[i]）。若最小值点不唯一，则选择使 j 较小的那个。

思路：首先n2算法默认一致忽略-_-。这道题有两种解法，分别利用了链表的方便插入和删除的两个性质。解法一从正向做，先建立一个双向链表，对于一个点，先利用set找到插入位置，将数值插入链表，并得到答案，过程中还需要利用map存储元素到结点编号的映射。解法二从反向做，先对数组进行一轮带下标的排序（可以用pair），然后再建立双向链表，由于这道题是对每个元素寻找之前位置的最近接近的数，所以前面的数字会多次用到，而后面的数字不会用到。可以倒序做一遍，比如对于原来位置i的元素A[i]，先找到排序后的位置j，然后答案就是左右两边较接近的数字，记录答案后，再删除结点j（因为前面的元素抉择时看不到后面的元素）。
由于解法一会多次利用set查找插入位置(1238ms)，效率不如解法二更优(255ms)，下面是解法二的代码

  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  5. typedef long long int64;
  6. typedef pair<int64,int> pli;
  8. const int N = 1e5 + 10;
  10. pli a[N];
  11. int p[N], l[N], r[N];
  12. int ans[N][2];
  14. int main() {
  15.     int n;
  16.     scanf("%d", &n);
  18.     for(int i = 1; i <= n; i++) {
  19.         scanf("%lld", &a[i].first);
  20.         a[i].second = i;
  21.     }
  22.     a[0].first = -3e9, a[0].second = 0;
  23.     a[n + 1].first = 3e9, a[n + 1].second = n + 1;
  24.     r[0] = 1, l[n + 1] = n;
  26.     sort(a + 1, a + 1 + n);
  28.     for(int i = 1; i <= n; i++) {
  29.         l[i] = i - 1, r[i] = i + 1;
  30.         p[a[i].second] = i;
  31.     }
  33.     for(int i = n; i > 1; i--) {
  34.         int j = p[i]; // 找到排序后原来第N个元素的新位置
  35.         int left = l[j], right = r[j];
  36.         int64 t1 = abs(a[left].first - a[j].first), t2 = abs(a[right].first - a[j].first);
  37.         if(t1 <= t2) {
  38.             ans[i][0] = t1, ans[i][1] = a[left].second;
  39.         }
  40.         else {
  41.             ans[i][0] = t2, ans[i][1] = a[right].second;
  42.         }
  43.         r[left] = right, l[right] = left; // 利用链表快速删除和查找结点
  44.     }
  46.     for(int i = 2; i <= n; i++) {
  47.         printf("%d %d\n", ans[i][0], ans[i][1]);
  48.     }
  50.     return 0;
  51. }

哈希

哈希通常是为了快速计算一个较为复杂的东西（比如一个数组）有没有出现过，通常包括两部分，哈希值计算，以及冲突处理（我一般是通过链表处理）。

经典场景：

  1. 字符串哈希

给出一段很长的字符串序列，然后再给出若干区间，判断这些区间的字串内容是否相同。该题是字符串哈希的模板题，里面值得注意的一点是首字母是权值最高的元素，然后通过前缀和的思想得到某一部分的哈希值，另外通过unsigned long long避免位溢出。

  1. #include<cstdio>
  2. #include<cstring>
  3. using namespace std;
  5. typedef unsigned long long ull;
  7. const int N = 1e6 + 10, M = 131;
  9. ull p[N], h[N];
  10. char s[N];
  12. bool same(int l1, int r1, int l2, int r2) {
  13.     ull v1 = h[r1] - h[l1 - 1] * p[r1 - l1 + 1];
  14.     ull v2 = h[r2] - h[l2 - 1] * p[r2 - l2 + 1];
  15.     return v1 == v2;
  16. }
  18. int main() {
  19.     scanf("%s", s + 1);
  21.     int n = strlen(s + 1);
  22.     p[0] = 1, s[0] = 0;
  24.     for(int i = 1; i <= n; i++) {
  25.         p[i] = p[i - 1] * M;
  26.         h[i] = h[i - 1] * M + s[i] - 'a';
  27.     }
  29.     int m;
  30.     scanf("%d", &m);
  32.     for(int i = 0; i < m; i++) {
  33.         int l1, r1, l2, r2;
  34.         scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
  36.         if(same(l1, r1, l2, r2)) {
  37.             printf("Yes\n");
  38.         }
  39.         else {
  40.             printf("No\n");
  41.         }
  42.     }
  44.     return 0;
  45. }
  1. 最长回文字符子串

给出一个字符串，求该字符串的最长回文字符字串的长度。这道题也可以用字符串哈希处理，我们可以二分最长回文字符字串的长度，然后结合二分，快速缩小答案的区间。这里值得注意的一点是，回文字符串有两种形式，分别是长度是奇数的字符串和长度为偶数的字符串，这两种不可以一起判断。比如我们判断长度为8的回文不存在，长度为4的回文不存在，然而长度为5的回文可能存在。因此，这里不能简单的二分长度，然后枚举左端点来做。结合两种二分的情况，我们可以枚举中间点，然后写两遍二分，分别判断两种情况下答案的最大值。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cmath>
  4. using namespace std;
  6. typedef unsigned long long ull;
  8. const int N = 1e6 + 10, M = 131;
  10. char s[N];
  11. ull p[N], h1[N], h2[N];
  12. int n;
  14. bool same(int l, int r) {
  15.     int l1 = n + 1 - r, r1 = n + 1 - l;
  17.     ull v1 = h1[r] - h1[l - 1] * p[r - l + 1];
  18.     ull v2 = h2[r1] - h2[l1 - 1] * p[r1 - l1 + 1];
  20.     return v1 == v2;
  21. }
  23. bool check_even(int len) {
  24.     for(int i = 1; i + 1 <= n; i++) {
  25.         int l = i - len + 1, r = i + len;
  26.         if(l < 1) continue;
  27.         if(r > n) break;
  29.         if(same(l, r)) {
  30.             return true;
  31.         }
  32.     }
  33.     return false;
  34. }
  36. bool check_odd(int len) {
  37.     for(int i = 1; i <= n; i++) {
  38.         int l = i - len, r = i + len;
  39.         if(l < 1) continue;
  40.         if(r > n) break;
  42.         if(same(l, r)) {
  43.             return true;
  44.         }
  45.     }
  46.     return false;
  47. }
  49. int main() {
  50.     int T = 0;
  51.     while(true) {
  52.         scanf("%s", s + 1);
  54.         if(s[1] == 'E') {
  55.             break;
  56.         }
  58.         n = strlen(s + 1);
  59.         p[0] = 1, h1[0] = h2[0] = 0;
  60.         for(int i = 1; i <= n; i++) {
  61.             p[i] = p[i - 1] * M;
  62.             h1[i] = h1[i - 1] * M + s[i] - 'a' + 1;
  63.             h2[i] = h2[i - 1] * M + s[n + 1 - i] - 'a' + 1;
  64.         }
  66.         int ans = 0;
  68.         int l = 0, r = n >> 1;
  69.         while(l < r) {
  70.             int mid = l + r + 1 >> 1;
  71.             if(check_odd(mid)) {
  72.                 l = mid;
  73.             }
  74.             else {
  75.                 r = mid - 1;
  76.             }
  77.         }
  78.         ans = max(ans, l * 2 + 1);
  80.         l = 0, r = n >> 1;
  81.         while(l < r) {
  82.             int mid = l + r + 1 >> 1;
  83.             if(check_even(mid)) {
  84.                 l = mid;
  85.             }
  86.             else {
  87.                 r = mid - 1;
  88.             }
  89.         }
  90.         ans = max(ans, l * 2);
  91.         printf("Case %d: %d\n", ++T, ans);
  92.     }
  94.     return 0;
  95. }
  1. 后缀数组的朴素求法()

后缀数组包含2个数组，数组SA和Height。我们将从k(0<=k求SA的思路是总体快排(logn层)，每层一共比较n个数字，每次比较结合字符串哈希和二分(logn)，总体复杂度，求Height就简单了，复用之前的字符串和二分（直接求两个字符串的最长公共前缀长度），复杂度

  1. // 求SA，快排logn层 * (n次比较 * 二分和哈希logn每次) = nlogn^2
  2. // 求height, n次比较 * 二分加哈希logn每次 = nlogn
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<cmath>
  7. using namespace std;
  9. typedef unsigned long long ull;
  11. const int N = 3e5 + 10, M = 131;
  13. char s[N];
  14. ull p[N], h[N];
  15. int a[N], n, hei[N];
  17. bool same(int l1, int l2, int len) {
  18.     int r1 = l1 + len - 1, r2 = l2 + len - 1;
  19.     ull v1 = h[r1] - h[l1 - 1] * p[r1 - l1 + 1];
  20.     ull v2 = h[r2] - h[l2 - 1] * p[r2 - l2 + 1];
  21.     return v1 == v2;
  22. }
  24. int common_len(int u, int v) {
  25.     int len = min(n - u + 1, n - v + 1);
  27.     int l = 0, r = len;
  28.     while(l < r) {
  29.         int mid = l + r + 1 >> 1;
  30.         if(same(u, v, mid)) {
  31.             l = mid;
  32.         }
  33.         else {
  34.             r = mid - 1;
  35.         }
  36.     }
  38.     return l;
  39. }
  41. bool cmp(int u, int v) {
  42.     int len = min(n - u + 1, n - v + 1);
  43.     int c_len = common_len(u, v);
  44.     if(c_len == len) {
  45.         return u > v; // 如果全部相等，长度短的字符串排序在前
  46.     }
  47.     return s[u + c_len] < s[v + c_len]; // 比较不相等的第一个字符
  48. }
  50. void qsort(int l, int r) {
  51.     if(l >= r) {
  52.         return;
  53.     }
  55.     int i = l - 1, j = r + 1, x = a[l + r >> 1];
  56.     while(i < j) {
  57.         do i++; while(cmp(a[i], x));
  58.         do j--; while(cmp(x, a[j]));
  59.         if(i < j) {
  60.             swap(a[i], a[j]);
  61.         }
  62.     }
  63.     qsort(l, j), qsort(j + 1, r);
  64. }
  66. int main() {
  67.     scanf("%s", s + 1);
  68.     n = strlen(s + 1);
  70.     p[0] = 1;
  71.     for(int i = 1; i <= n; i++) {
  72.         a[i] = i;
  73.         p[i] = p[i - 1] * M;
  74.         h[i] = h[i - 1] * M + s[i] - 'a';
  75.     }
  77.     qsort(1, n);
  79.     hei[1] = 0;
  80.     for(int i = 2; i <= n; i++) {
  81.         hei[i] = common_len(a[i - 1], a[i]);
  82.     }
  84.     for(int i = 1; i <= n; i++) {
  85.         printf("%d ", a[i] - 1);
  86.     }
  87.     printf("\n");
  88.     for(int i = 1; i <= n; i++) {
  89.         printf("%d ", hei[i]);
  90.     }
  91.     printf("\n");
  93.     return 0;
  94. }
  1. 矩阵

给出一个NM的01矩阵，再给出若干个AB的小矩阵，询问这些小矩阵是否在大矩阵中出现过。
这道题相当于问一些字符串是否出现过。我们可以先把每个A*B的矩阵的哈希值计算出来，然后存在一个数组里，通过二分快速查找。现在唯一的问题就是如何计算小矩阵的hash值，这涉及到二维哈希值的计算，我们可以先计算大矩阵中每一行的哈希值，然后再构造出小矩阵的hash值，这就是二维hash计算。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  6. typedef unsigned long long ull;
  8. const int N = 1010;
  10. ull h[N][N], p[N];
  11. int P = 131;
  12. int n, m, a, b, q;
  13. char s[N];
  14. ull v[N * N];
  15. int idx = 0;
  17. ull get(ull hr[], int l, int r) {
  18.     return hr[r] - hr[l - 1] * p[r - l + 1];
  19. }
  21. void cal(int x, int y) {
  22.     ull tmp = 0;
  23.     for(int i = x - a + 1; i <= x; i++) {
  24.         tmp = tmp * p[b] + get(h[i], y - b + 1, y);
  25.     }
  26.     v[idx++] = tmp;
  27. }
  29. int find(ull x) {
  30.     int l = 0, r = idx - 1;
  31.     while(l < r) {
  32.         int mid = l + r >> 1;
  33.         if(v[mid] >= x) {
  34.             r = mid;
  35.         }
  36.         else {
  37.             l = mid + 1;
  38.         }
  39.     }
  41.     if(v[l] != x) {
  42.         return 0;
  43.     }
  45.     return 1;
  46. }
  48. int main() {
  49.     scanf("%d%d%d%d", &n, &m, &a, &b);
  51.     memset(h, 0, sizeof h);
  53.     p[0] = 1;
  54.     for(int i = 1; i <= n; i++) {
  55.         p[i] = p[i - 1] * P;
  56.     }
  58.     for(int i = 1; i <= n; i++) {
  59.         scanf("%s", s + 1);
  60.         for(int j = 1; j <= m; j++) {
  61.             h[i][j] = h[i][j - 1] * P + s[j] - '0';
  62.         }
  63.     }
  65.     for(int i = a; i <= n; i++) {
  66.         for(int j = b; j <= m; j++) {
  67.             cal(i, j); // 计算小矩阵的hash值
  68.         }
  69.     }
  71.     sort(v, v + idx);
  73.     scanf("%d", &q);
  75.     while(q--) {
  76.         ull tmp = 0;
  77.         for(int i = 0; i < a; i++) {
  78.             scanf("%s", s);
  79.             for(int j = 0; j < b; j++) {
  80.                 tmp = tmp * P + s[j] - '0';
  81.             }
  82.         }
  84.         printf("%d\n", find(tmp));
  85.     }
  87.     return 0;
  88. }
  1. 匹配统计

给出一个字符串A和一个字符串B，给出一个数字x，求A的所有后缀子串中和B匹配长度（从头匹配）为x的字串有多少？
本题可以先计算一遍字符串哈希，然后对A的每一个后缀子串直接采用二分结合字符串hash的方式判断该后缀子串的匹配长度，时间复杂度：O（N+NlogN）。

  1. #include<iostream>
  2. using namespace std;
  4. typedef unsigned long long ull;
  6. const int N = 2e5 + 10, P = 131;
  8. ull p[N], h1[N], h2[N];
  9. char s1[N], s2[N];
  10. int n, m, q, x;
  11. int cnt[N];
  13. ull get_hash(ull h[], int l, int r) {
  14.     return h[r] - h[l - 1] * p[r - l + 1];
  15. }
  17. int main() {
  18.     scanf("%d%d%d", &n, &m, &q);
  19.     scanf("%s%s", s1 + 1, s2 + 1);
  21.     p[0] = 1;
  22.     h1[0] = h2[0] = 0;
  23.     for(int i = 1; i <= n; i++) {
  24.         p[i] = p[i - 1] * P;
  25.         h1[i] = h1[i - 1] * P + s1[i] - 'a';
  26.     }
  28.     for(int i = 1; i <= m; i++) {
  29.         h2[i] = h2[i - 1] * P + s2[i] - 'a';
  30.     }
  32.     for(int i = 1; i <= n; i++) {
  33.         int l = i - 1, r = min(n, i + m - 1); // 求相等的右端点
  34.         while(l < r) {
  35.             int mid = l + r + 1 >> 1;
  36.             int len = mid - i + 1;
  37.             if(get_hash(h1, i, mid) == get_hash(h2, 1, len)) {
  38.                 l = mid;
  39.             }
  40.             else {
  41.                 r = mid - 1;
  42.             }
  43.         }
  44.         cnt[r - i + 1]++;
  45.     }
  47.     while(q--) {
  48.         scanf("%d", &x);
  49.         printf("%d\n", cnt[x]);
  50.     }
  52.     return 0;
  53. }

KMP

KMP算法求一个字符串的每个位置为终点的子串，求最长前缀匹配，即s[1]~s[i]=s[j - i + 1]~s[j]。

经典场景：

  1. 求字符串所有前缀的最小循环节（前缀长度大于1，循环次数大于1）

推论：字符串s具有长度为len的循环节，是 len|n 且 s[1]~s[n-len]=s[len + 1]~s[n]的充要条件。两边都很好证明。因此，如果想得到字符串s的最小循环节，则需要len最小，对应的是s[len + 1]~s[n]的长度最大，等价于s[n]的next[n]，转化为KMP求next数组。n-len = next[n]，故len = n - next[n]，如果n能整除(n - next[n])，则字符串s具有长度为n-next[n]的最小循环节。
此外，一个字符串的任意循环节的长度最小循环节的长度的整数倍。因为若s[i]=s[i+x]=s[i+y]，则s[i]=s[i+mx+ny]=s[i+gcd(x,y)]，最小循环节长度为len，则必然满足 len | gcd(x,y)且len<=gcd(x,y)，因此得出len | x 和 len | y。

  1. #include<cstdio>
  2. using namespace std;
  4. const int N = 1e6 + 10;
  6. char s[N];
  7. int ne[N], n;
  9. int main() {
  10.     int T = 0;
  11.     while(true) {
  12.         scanf("%d", &n);
  13.         if(n == 0) {
  14.             break;
  15.         }
  16.         scanf("%s", s + 1);
  18.         for(int i = 2, j = 0; i <= n; i++) {
  19.             while(j > 0 && s[i] != s[j + 1]) j = ne[j];
  20.             if(s[i] == s[j + 1]) {
  21.                 j++;
  22.             }
  23.             ne[i] = j;
  24.         }
  26.         printf("Test case #%d\n", ++T);
  28.         for(int i = 2; i <= n; i++) {
  29.             if(ne[i] != 0 && i % (i - ne[i]) == 0) {
  30.                 printf("%d %d\n", i, i / (i - ne[i]));
  31.             }
  32.         }
  33.         printf("\n");
  34.     }
  35.     return 0;
  36. }
  1. 奶牛矩阵

给出一个由字母构成的矩阵，求最小子矩阵的面积，使得子矩阵扩张任意次后，可以包含原来的矩阵。
这道题本质上是二维的最小循环节问题，我们可以把一行看作一个字母，然后做一遍字符串的最小循环节，然后得到行的最小循环节长度。同理，在列上也做一遍，两者的乘积既是答案。这里有个判断两个字符串数组是否相等的API，若两个字符串相等，则strcmp(s1, s2)返回0，不等则返回1。值得注意的一点是，在做kmp的时候，字符串的起始下标习惯上用1，而strcmp需要让s1和s2从下标0开始比较，所以采用strcmp(s1+1,s2+1)。

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  5. const int N = 1e4 + 10, M = 80;
  7. char s1[N][M], s2[M][N];
  8. int ne1[N], ne2[M];
  9. int n, m;
  11. int main() {
  12.     scanf("%d%d", &n, &m);
  14.     for(int i = 1; i <= n; i++) {
  15.         scanf("%s", s1[i] + 1);
  16.     }
  18.     for(int i = 1; i <= n; i++) {
  19.         for(int j = 1; j <= m; j++) {
  20.             s2[j][i] = s1[i][j];
  21.         }
  22.     }
  24.     ne1[1] = ne2[1] = 0;
  25.     for(int i = 2, j = 0; i <= n; i++) {
  26.         while(j > 0 && strcmp(s1[i] + 1, s1[j + 1] + 1)) {
  27.             j = ne1[j];
  28.         }
  29.         if(!strcmp(s1[i] + 1, s1[j + 1] + 1)) {
  30.             j++;
  31.         }
  32.         ne1[i] = j;
  33.     }
  35.     for(int i = 2, j = 0; i <= m; i++) {
  36.         while(j > 0 && strcmp(s2[i] + 1, s2[j + 1] + 1)) {
  37.             j = ne2[j];
  38.         }
  39.         if(!strcmp(s2[i] + 1, s2[j + 1] + 1)) {
  40.             j++;
  41.         }
  42.         ne2[i] = j;
  43.     }
  45.     int w = m - ne2[m], h = n - ne1[n];
  46.     printf("%d\n", w * h);
  48.     return 0;
  49. }
  1. 匹配统计

给出一个字符串A和一个字符串B，给出一个数字x，求A的所有后缀子串中和B匹配长度（从头匹配）为x的子串有多少？
这个题之前用字符串哈希的方式做过一次，这里介绍一种KMP的方法。匹配理所当然的可以想到KMP，但是KMP求的是前缀子串的结尾的匹配。
假设前缀子串的在位置i的匹配是[i-j+1,i]，那么匹配长度是j，我们记录cnt[j]++，但是对于从i-j+1开始的后缀子串，这不是该子串的真正匹配，因为后面的字符可能进一步扩大匹配长度，所以cnt[j]表示的含义是匹配长度至少是j的后缀子串数量（难点一）。
而且对于从i-j+1开始的后缀子串，其还包括[i-ne[j]+1,i]的匹配，所以我们计算cnt[j]++的同时，还需要计算cnt[ne[j]]++，这样往复造成算法效率变低。因为对于所有的位置，如果存在cnt[j]++的计算，必然存在cnt[ne[j]]++。因此，我们不妨先在每个位置记录下“最长”的匹配cnt[j]，对于cnt[ne[j]]，我们可以用一个倒序遍历来累加，即cnt[ne[j]]+=cnt[j]（难点二）。
最后，我们得到了cnt数组，在求匹配长度为x的子串数量时，采用后缀和的思想，ans=cnt[x] - cnt[x+1]。（难点三）

  1. #include<iostream>
  2. #include<unordered_map>
  3. #include<cstring>
  4. using namespace std;
  6. const int N = 2e5 + 10;
  8. char s1[N], s2[N];
  9. int ne[N];
  10. int n, m, q, x;
  11. unordered_map<int,int> mp;
  12. int cnt[N];
  14. int main() {
  15.     scanf("%d%d%d", &n, &m, &q);
  16.     scanf("%s%s", s1 + 1, s2 + 1);
  18.     ne[1] = 0;
  19.     for(int i = 2, j = 0; i <= m; i++) {
  20.         while(j && s2[i] != s2[j + 1]) {
  21.             j = ne[j];
  22.         }
  23.         if(s2[i] == s2[j + 1]) {
  24.             j++;
  25.         }
  26.         ne[i] = j;
  27.     }
  29.     memset(cnt, 0, sizeof cnt);
  30.     for(int i = 1, j = 0; i <= n; i++) {
  31.         while(j && s1[i] != s2[j + 1]) {
  32.             j = ne[j];
  33.         }
  34.         if(s1[i] == s2[j + 1]) {
  35.             j++;
  36.         }
  37.         cnt[j]++; // 以位置i作为结尾的匹配的长度是j(kmp定义)，后续可能继续拓展，因此cnt[j]定义是匹配长度至少为j的数量，先统计最大
  38.     }
  40.     for(int i = m; i >= 1; i--) {
  41.         cnt[ne[i]] += cnt[i]; // cnt[j]表示匹配长度至少为j，一定会被cnt[ne[j]]所包含，依次，cnt[ne[ne[j]]会包含cnt[j]，倒序累加
  42.     }
  44.     while(q--) {
  45.         scanf("%d", &x);
  46.         printf("%d\n", cnt[x] - cnt[x + 1]); // 后缀和思想
  47.     }
  49.     return 0;
  50. }

字典树

存储多个字符串，整理成一颗树的形式，方便进行特定的统计。

经典场景：

  1. 前缀统计

给出n个字符串，再给出m次询问，每次询问给出一个字符串s，回答之前输入的n个字符串中有多少个是字符串s的前缀。
这道题可以用字典树，将输入的n个字符串构造字典树，然后每插入一个字符串，给对应位置的结点数量加一。之后每次询问时，我们根据字符串s沿着字典树向下走，如果某个结点的数量大于0，则说明出现了前缀，累加进答案。

  1. #include<cstdio>
  2. using namespace std;
  4. const int N = 1e6 + 10;
  6. int son[N][26], idx = 0, cnt[N * 26];
  7. char s[N];
  9. void insert(char *s) {
  10.     int p = 0;
  11.     for(int i = 0; s[i]; i++) {
  12.         int c = s[i] - 'a';
  13.         if(!son[p][c]) {
  14.             son[p][c] = ++idx;
  15.         }
  16.         p = son[p][c];
  17.     }
  18.     cnt[p]++;
  19. }
  21. int query(char *s) {
  22.     int p = 0, ans = 0;
  23.     for(int i = 0; s[i]; i++) {
  24.         int c = s[i] - 'a';
  25.         if(!son[p][c]) {
  26.             break;
  27.         }
  28.         p = son[p][c];
  29.         ans += cnt[p];
  30.     }
  31.     return ans;
  32. }
  34. int main() {
  35.     int n, m;
  36.     scanf("%d%d", &n, &m);
  38.     for(int i = 0; i < n; i++) {
  39.         scanf("%s", s);
  40.         insert(s);
  41.     }
  43.     for(int i = 0; i < m; i++) {
  44.         scanf("%s", s);
  45.         printf("%d\n", query(s));
  46.     }
  48.     return 0;
  49. }
  1. 最大异或对

给出一个数组，求其中任意两个元素异或的最大值。

  1. #include<cstdio>
  2. #include<cmath>
  3. using namespace std;
  5. const int N = 1e5 + 10;
  6. int son[N * 32][2], idx = 0;
  7. int a[N], n;
  9. void insert(int x) {
  10.     int p = 0;
  11.     for(int i = 30; i >= 0; i--) {
  12.         int v = x >> i & 1;
  13.         if(!son[p][v]) {
  14.             son[p][v] = ++idx; // 有多少个节点，对应son数组的第一维的大小
  15.         }
  16.         p = son[p][v];
  17.     }
  18. }
  20. int query(int x) {
  21.     int ans = 0, p = 0;
  22.     for(int i = 30; i >= 0; i--) {
  23.         int v = x >> i & 1;
  24.         if(son[p][!v]) {
  25.             p = son[p][!v];
  26.             ans |= (!v) << i;
  27.         }
  28.         else {
  29.             p = son[p][v];
  30.             ans |= v << i;
  31.         }
  32.     }
  33.     return ans ^ x;
  34. }
  36. int main() {
  37.     scanf("%d", &n);
  38.     for(int i = 0; i < n; i++) {
  39.         scanf("%d", &a[i]);
  40.     }
  42.     for(int i = 0; i < n; i++) {
  43.         insert(a[i]);
  44.     }
  46.     int ans = 0;
  47.     for(int i = 0; i < n; i++) {
  48.         ans = max(ans, query(a[i]));
  49.     }
  51.     printf("%d\n", ans);
  53.     return 0;
  54. }
  1. 最长异或值路径

给出一个树，树边有权值，求树上任意两点间路径的最大异或值。首先任意两点之间的路径异或值，可以看作这两点到根结点的路径的异或值的异或（公共部分抵消），因此这道题可以转化为：给你N个数字（所有节点到根的异或值），然后求任意两个数字的异或的最大值，就等价于上一题了。考的是建图+树简单遍历+字典树。

  1. #include<cstdio>
  2. #include<cmath>
  3. #include<cstring>
  4. using namespace std;
  6. const int N = 1e5 + 10;
  8. int son[N * 30][2], s_idx = 0;
  9. int h[N], e[N], ne[N], w[N], h_idx, n;
  10. int ind[N], a[N];
  12. void add(int a, int b, int c) {
  13.     e[h_idx] = b, w[h_idx] = c, ne[h_idx] = h[a], h[a] = h_idx++;
  14. }
  16. void dfs(int u, int v) {
  17.     a[u] = v;
  18.     for(int i = h[u]; ~i; i = ne[i]) {
  19.         int j = e[i];
  20.         dfs(j, v ^ w[i]);
  21.     }
  22. }
  24. void insert(int x) {
  25.     int p = 0;
  26.     for(int i = 30; i >= 0; i--) {
  27.         int v = x >> i & 1;
  28.         if(!son[p][v]) {
  29.             son[p][v] = ++s_idx;
  30.         }
  31.         p = son[p][v];
  32.     }
  33. }
  35. int query(int x) {
  36.     int ans = 0, p = 0;
  37.     for(int i = 30; i >= 0; i--) {
  38.         int v = x >> i & 1;
  39.         if(son[p][!v]) {
  40.             p = son[p][!v];
  41.             ans |= (!v) << i;
  42.         }
  43.         else {
  44.             p = son[p][v];
  45.             ans |= v << i;
  46.         }
  47.     }
  48.     return ans ^ x;
  49. }
  51. int main() {
  52.     memset(h, -1, sizeof h);
  53.     h_idx = 0;
  54.     memset(ind, 0, sizeof ind);
  56.     scanf("%d", &n);
  57.     for(int i = 0; i < n - 1; i++) {
  58.         int u, v, x;
  59.         scanf("%d%d%d", &u, &v, &x);
  60.         add(u, v, x);
  61.         ind[v]++;
  62.     }
  64.     for(int i = 0; i < n; i++) {
  65.         if(!ind[i]) {
  66.             dfs(i, 0);
  67.             break;
  68.         }
  69.     }
  71.     for(int i = 0; i < n; i++) {
  72.         insert(a[i]);
  73.     }
  75.     int ans = 0;
  76.     for(int i = 0; i < n; i++) {
  77.         ans = max(ans, query(a[i]));
  78.     }
  80.     printf("%d\n", ans);
  81.     return 0;
  82. }
  1. 电话列表

给出一系列字符串，判断是否存在某个字符串是另一个字符串的前缀，如果是，返回NO 。
多个字符串之间的联系，考虑字典树。字符串出现前缀有两种情况，第一种情况是插入的字符串完全在某个路径上，第二种情况是插入的字符串经过某个字符串的结尾节点。

  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  5. const int N = 100010, M = 11; // 10000个字符串，每个字符串最多创造10个新节点，故第一维1e5+10
  7. int son[N][M], idx = 0;
  8. int cnt[N];
  9. char s[M];
  11. bool insert(char *s) { // 发现前缀返回true
  12.     bool suffix = false;
  13.     bool same = true;
  14.     int p = 0;
  15.     for(int i = 0; s[i]; i++) {
  16.         int x = s[i] - '0';
  17.         if(!son[p][x]) {
  18.             son[p][x] = ++idx;
  19.             same = false;
  20.         }
  22.         p = son[p][x];
  23.         if(cnt[p]) {
  24.             suffix = true;
  25.         }
  26.     }
  27.     cnt[p] = 1;
  28.     return same || suffix;
  29. }
  31. int main() {
  32.     int T;
  33.     scanf("%d", &T);
  35.     while(T--) {
  36.         int n;
  37.         scanf("%d", &n);
  39.         memset(son, 0, sizeof son);
  40.         memset(cnt, 0, sizeof cnt);
  41.         idx = 0;
  43.         bool flag = false;
  44.         for(int i = 0; i < n; i++) {
  45.             scanf("%s", s);
  46.             if(insert(s)) {
  47.                 flag = true;
  48.             }
  49.         }
  51.         if(flag) {
  52.             printf("NO\n");
  53.         }
  54.         else {
  55.             printf("YES\n");
  56.         }
  57.     }
  59.     return 0;
  60. }

二叉堆

一般在程序里，直接使用优先队列的即可，这里有一点需要注意，如果只是简单地需要int或pair类型的优先队列，直接定义greater（小根堆），或less（大根堆）即可。但是如果是比较复杂的数据结构，就需要自定义结构体，在结构体里面定义排序规则（小根堆写大于号，大根堆写小于号），如：

  1. struct Node {
  2.     int i, j, val;
  3.     bool operator< (const Node & x) const { // 注意：这是小根堆的写法
  4.         return val > x.val;
  5.     }
  6. };
  8. priority_queue<Node> pq;

经典场景：

  1. 序列

给出N个数组，每个数组有M个数字，如果每个数组选一个数字，一共可以组成m^n个序列，求所有序列中最小的m个序列的值。
这道题蕴含了一个很好的思维方式。直观地看，第一个最小的序列一定是所有序列排序后的第一个数字组成，我们可以把这种排列方式和对应的值定义成结构体，然后用队列拓展m次即可，但是这个方法隐藏了两个很大的问题：第一个问题是重复的状态会被多次拓展，导致答案错误；第二个问题是最小值一次会拓展出很多候选项，状态数量会爆炸。这道题可以用数学归纳法的思想来做，我们可以先得到前两个数组中最小的前m个元素，合并后再和第三个数组进行合并，合并N-1次之后就是答案。而每次合并两个数组的状态数量大大减少，我们只需要保证其中一个数组有序，将有序数组的第一个数字和第二个数组的全部数字组成的状态全部加入，后面不断向后移动第一个数组的指针即可。由于合并过程会按顺序得到当前最小值，所以整个算法只需要对第一个数组排序。
这种先将问题简化，再拓展的思维方法（数学归纳法）值得好好学习！
固定一个变量，然后主要看另一个变量的变化，这种方式有点像微积分里求偏导数的做法，数学的思维方式在程序设计里还挺常见的。

  1. #include<cstdio>
  2. #include<queue>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  7. const int N = 1010, M = 2010;
  9. int a[M], b[M], c[M];
  10. int n, m;
  12. struct Node {
  13.     int i, j, val;
  15.     bool operator< (const Node & x) const { // 注意：这是小根堆的写法
  16.         return val > x.val;
  17.     }
  18. };
  22. void merge() { // 合并a, b, 将答案升序放在a中
  23.     priority_queue<Node> pq;
  25.     for(int i = 0; i < m; i++) {
  26.         pq.push({0, i, a[0] + b[i]}); // 先把所有的b全部入队，这样可以保证后续只需要移动a的指针，避免出现重复情况
  27.     }
  29.     for(int k = 0; k < m; k++) {
  30.         Node node = pq.top();
  31.         pq.pop();
  32.         c[k] = node.val;
  33.         pq.push({node.i + 1, node.j, a[node.i + 1] + b[node.j]});
  34.     }
  36.     memcpy(a, c, sizeof c);
  37. }
  39. int main() {
  40.     int T;
  41.     scanf("%d", &T);
  43.     while(T--) {
  44.         scanf("%d%d", &n, &m);
  46.         for(int i = 0; i < m; i++) {
  47.             scanf("%d", &a[i]);
  48.         }
  50.         sort(a, a + m);
  52.         for(int i = 1; i < n; i++) {
  53.             for(int j = 0; j < m; j++) {
  54.                 scanf("%d", &b[j]);
  55.             }
  57.             merge();
  58.         }
  60.         for(int i = 0; i < m; i++) {
  61.             printf("%d ", a[i]);
  62.         }
  63.         printf("\n");
  64.     }
  66.     return 0;
  67. }
  1. 数据备份

有N个点在一排，有K个线，每个线可以连接2个点，K条线一共可以连接2K个点，求K条线的最短长度。(K个线的两端都不一样)。
首先，如果要总长度最短，那么线段之间不能有重合部分，且每条线段都应该连接相邻的两个点。因此，相当于给出N-1个数字（每两个点之间的间距），然后我们从中选择K个，并且有个限制条件，选择了第i个数字，就不能选择第i-1个数字和第i+1个数字，因为线段的两端不能重合。在这种限制条件下，最优选择可以有2种情况：第一种就是我们选择最小的数字，然后删除最小的数字左右两边的数字。第二种是选择最小的数字左右两边的数字，然后删除3个数字。如何统一来考虑这两种情况是本题的精髓，我们可以先采用第一种选择，先选出当前集合中最小的数字，然后删除左右两边的数字，然后再将最小的数字a[i]的值修改为a[i-1]+a[i+1]-a[i]，这样，如果之后选择了修改后的数字，说明选择二比选择一更好，同时也能维护数据结构的一致性。此外，由于我们需要的操作需要能得到最小值，且要能删除指定位置和插入元素，可以采用小根堆和双向链表来实现。另外有一点值得注意的是，如果删除的结点包含哨兵结点，那么新加入的结点应该不能被选择，因为哨兵节点没有实际意义，不能表示为一个真实的结点，这个时候只需要将哨兵结点的值设为大数值，避免新节点被选择即可。（在这个点上卡了1整天）

  1. #include<cstdio>
  2. #include<queue>
  3. #include<cstring>
  4. using namespace std;
  6. typedef pair<int,int> pii;
  8. const int N = 2e5 + 10;
  10. int a[N], b[N];
  11. int e[N], r[N], l[N], head, tail, idx;
  13. void insert(int x, int pos) { // 在pos之后插入x
  14.     e[idx] = x;
  15.     r[idx] = r[pos], l[r[pos]] = idx;
  16.     l[idx] = pos, r[pos] = idx;
  17.     idx++;
  18. }
  20. int delete_node(int pos) { //删除掉一个点，并返回删除结点的前一个点的编号
  21.     l[r[pos]] = l[pos];
  22.     r[l[pos]] = r[pos];
  23.     return l[pos];
  24. }
  26. int main() {
  27.     int n, k;
  28.     scanf("%d%d", &n, &k);
  30.     for(int i = 0, p, x; i < n; i++) {
  31.         scanf("%d", &x);
  32.         if(i != 0) {
  33.             a[i] = x - p;
  34.         }
  35.         p = x;
  36.     }
  38.     head = 1, tail = 2, idx = 3;
  39.     e[head] = 1e9, e[tail] = 1e9; // 如果要删除哨兵结点，则新加入的结点不该被选择，所以数值设为最大
  40.     r[head] = tail, l[tail] = head;
  42.     priority_queue<pii,vector<pii>,greater<pii>> pq;
  44.     for(int i = 1; i < n; i++) {
  45.         pq.push({a[i], idx});
  46.         insert(a[i], l[tail]);
  47.     }
  49.     memset(b, 0, sizeof b); // 标记结点编号是不是处理过
  50.     int ans = 0;
  51.     for(int i = 0; i < k; i++) {
  52.         pii p = pq.top();
  53.         pq.pop();
  54.         int id = p.second;
  55.         int val = 0;
  56.         if(b[id]) { // 如果是删除过的结点，就忽略
  57.             i--;
  58.             continue;
  59.         }
  60.         ans += p.first;
  62.         b[l[id]] = 1;
  63.         val += e[l[id]];
  64.         delete_node(l[id]);
  66.         b[r[id]] = 1;
  67.         val += e[r[id]];
  68.         delete_node(r[id]);
  70.         b[id] = 1;
  71.         val -= e[id];
  72.         int n_pos = delete_node(id);
  74.         pq.push({val, idx});
  75.         insert(val, n_pos);
  76.     }
  78.     printf("%d\n", ans);
  80.     return 0;
  81. }
  1. 荷马史诗

给出N个单词和对应的频率，我们希望将单词变成K进制的形式，然后保证编码后整体的长度最短，其次希望最长的单词的长度最短。
这道题本质上是K进制的哈夫曼树。整体思路还是用小根堆优先合并数值小的元素，但是需要注意两点。一是这是K进制，对应的是K叉树，如果直接合并，可能会让最后一次合并的元素数量不足K个，这样就不是最优的，所以我们需要添加若干个数值为0的结点，让大数值的结点，充满整个合并过程。二是如何保证最长的单词长度最短，以后二叉树形式合并时，大多是直接求一个最优结果，并没有让我们思考第二问，而最长单词的最短长度等价于问合并好后树高最低是多少，我们合并时可以将结点高度作为第二关键字，在数值相同时，优先合并高度较低的结点，这样就能保证在不影响最优解的情况下，保证树高最低。

  1. #include<cstdio>
  2. #include<queue>
  3. using namespace std;
  5. typedef long long ll;
  6. typedef pair<ll,int> pli;
  8. const int N = 1e5 + 10;
  10. ll a[N];
  12. int main() {
  13.     int n, k;
  14.     scanf("%d%d", &n, &k);
  16.     for(int i = 0; i < n; i++) {
  17.         scanf("%lld", &a[i]);
  18.     }
  20.     if((n - 1) % (k - 1)) { // 添加0结点，保证最后一次合并不会出现空缺，从而整体最优
  21.         int s = (n - 1 + k - 2) / (k - 1) * (k - 1) - (n - 1);
  22.         for(int i = 0; i < s; i++) {
  23.             a[n + i] = 0;
  24.         }
  25.         n += s;
  26.     }
  28.     priority_queue<pli,vector<pli>,greater<pli>> pq; // 维护值和高度，在值等大时，选择高度更低的合并，降低整体树高
  30.     for(int i = 0; i < n; i++) {
  31.         pq.push({a[i], 0});
  32.     }
  34.     ll ans = 0;
  35.     int len = 0;
  36.     while(pq.size() > 1) {
  37.         ll s = 0;
  38.         int height = 0;
  39.         for(int i = 0; i < k; i++) {
  40.             pli p = pq.top();
  41.             pq.pop();
  42.             s += p.first;
  43.             height = max(height, p.second);
  44.         }
  45.         height++; // 合并之后的结点高度加1
  46.         pq.push({s,height});
  47.         ans += s;
  48.         len = max(height, len); // 更新最大高度
  49.     }
  51.     printf("%lld\n%d\n", ans, len);
  53.     return 0;
  54. }