整体偏移

假设有很多元素，当对某个元素进行处理，导致所有其他元素都发生增大，或缩小时，可以用偏移量来解决。

经典场景：
有很多蚯蚓，每秒钟将一个最长的蚯蚓一分为二，其他的蚯蚓增加一个非负整数q。由于所有元素都需要变大，而互相之间的大小关系并没有发生变化，这时可以使用一个偏移量，表示所有元素的增大量，而别切开的蚯蚓减去q后再放回最大堆即可。值得注意的是，元素出队时需要加上偏移量还原真实值，入队时需要减去偏移量，进行还原。

  1. int diff = 0; // 偏移量
  2. for(int i = 1; i <= m; i++) {
  3.     int x = get_max();
  4.     x += diff; // 出队时加上偏移量，还原真实值
  5.     if(i % t == 0) {
  6.         printf("%d ", x);
  7.     }
  8.     int half1 = 1.0 * u / v * x;
  9.     int half2 = x - half1;
  10.     q2[++tt2] = max(half1 - diff - q, half2 - diff - q); // 入队时减去偏移量，和原来保持一致
  11.     q3[++tt3] = min(half1 - diff - q, half2 - diff - q);
  12.     diff += q; // 累加偏移量
  13. }

另外这段代码值得注意的一点是， 在维护最大值的时候，发现最大值可能会出现在三个地方，原来队列（原始长度降序排序），分开后较长的一段，和分开后较短的一段。我们每次将分开后的蚯蚓中较长的一段放在队列2中，较短的一段放在队列3中。之后再取蚯蚓切分时，由于是按比例切分，切分后的蚯蚓的两端分别小于之前蚯蚓切分好的两段。所以不管怎么切，队列2和队列3的所有元素都可以维护单调性，保证元素下降。
通过维护多个单调队列，当前所有元素的最大值就是三个队列的队头的最大值，将添加新元素和寻找最大值的是将复杂度从优先队列的O(logn)降低为O(1)。

带有下标的排序

有时候不仅需要排序，还需要知道排序后下标的变化。下面有两个方法，方法2相对简单一些。
方法1：用pair，first存元素，second存下标

  1. typedef pair<int,int> pii;
  3. const int N = 2e5 + 10;
  5. pii a[N];
  7. for(int i = 0; i < n; i++) { // 带有下标的元素排序
  8.     scanf("%d", &a[i].first);
  9.     a[i].second = i;
  10. }
  12. sort(a, a + n);

方法2：另外开一个数组，单独存储下标

  1. const int N = 2e5 + 10;
  3. int a[N], b[N];
  5. bool cmp(int i, int j) {
  6.     return a[i] < a[j];
  7. }
  9. for(int i = 0; i < n; i++) {
  10.     scanf("%d", &a[i]);
  11.     b[i] = i;
  12. }
  14. sort(b, b + n, cmp);

最小表示

当遇到对一个数组位移后，和原数组是否相等的情况时，我们可以通过最小表示来解决，通过计算出该数组位移后最小的表示，来唯一确定一个数组。常用于字符串的最小表示，以及树的最小表示。

经典场景

  1. 项链

给出两个等长的字符串，判断一个字符串是否可以偏移得到另一个字符串，如果可以，求出偏移操作后的最小字符串表示。
这就是字符串的最小表示的模板。

  1. //#include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. using namespace std;
  6. const int N = 1e7 + 10;
  8. char a[N], b[N];
  10. void get_min(char a[], int n) {
  11.     static char s[2 * N];
  12.     for(int i = 0; i < n; i++) {
  13.         s[i] = s[i + n] = a[i];
  14.     }
  16.     int i = 0, j = 1, k = 0;
  17.     while(i < n && j < n) {
  18.         for(k = 0; k < n && s[i + k] == s[j + k]; k++);
  19.         if(k == n) {
  20.             break;
  21.         }
  23.         if(s[i + k] > s[j + k]) {
  24.             i += k + 1;
  25.             if(i == j) {
  26.                 i++;
  27.             }
  28.         }
  29.         else {
  30.             j += k + 1;
  31.             if(i == j) {
  32.                 j++;
  33.             }
  34.         }
  35.     }
  37.     int st = min(i, j);
  38.     for(int i = 0; i < n; i++) {
  39.         a[i] = s[st + i];
  40.     }
  41. }
  43. bool cmp(char a[], char b[], int n) {
  44.     for(int i = 0; i < n; i++) {
  45.         if(a[i] < b[i]) {
  46.             return true;
  47.         }
  48.         if(a[i] > b[i]) {
  49.             return false;
  50.         }
  51.     }
  53.     return false;
  54. }
  56. int main() {
  57.     scanf("%s%s", a, b);
  59.     int n = strlen(a);
  60.     get_min(a, n), get_min(b, n);
  62.     if(cmp(a, b, n) || cmp(b, a, n)) {
  63.         printf("No\n");
  64.     }
  65.     else {
  66.         printf("Yes\n");
  67.         printf("%s\n", a);
  68.     }
  70.     return 0;
  71. }
  1. 雪花

每个雪花有6个数字组成，这6个数字可以正着看，也可以逆序看，还可以位移后再看。如果两个雪花通过位移，或逆序后的数字都相同，则认为这两个雪花相同。
这道题有两种解法：第一种是直接使用hash计算出雪花的一个hash值，然后将该雪花在数组中的下标插入链表数组中，如果在插入一个新的雪花时，发现对应位置的链表不为空，需要和链表上的元素逐一判断。第二种解法是先得到原雪花和逆序后雪花的最小表示，然后两个最小表示的更小者，就可以代表原雪花经过位移，反转所有情况下的唯一表示，只要有别的雪花的最小表示和它相同，则可以认为两个雪花相同，效率相对来说更高一些。下面是解法二（字符串的最小表示）的代码。

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<algorithm>
  5. using namespace std;
  7. const int N = 1e5 + 10;
  9. int a[N][6];
  10. int d[N];
  12. bool cmp1(int *a, int *b) {
  13.     for(int i = 0; i < 6; i++) {
  14.         if(a[i] < b[i]) {
  15.             return true;
  16.         }
  17.         if(a[i] > b[i]) {
  18.             return false;
  19.         }
  20.     }
  21.     return false;
  22. }
  24. bool cmp2(int i, int j) {
  25.     return cmp1(a[i], a[j]);
  26. }
  28. void get_min(int *a) { // 最小表示法，得到每个雪花旋转情况下的任意表示
  29.     static int b[12];
  30.     for(int i = 0; i < 12; i++) {
  31.         b[i] = a[i % 6];
  32.     }
  34.     int i = 0, j = 1, k = 0;
  35.     while(i < 6 && j < 6) {
  36.         for(k = 0; k < 6 && b[i + k] == b[j + k]; k++);
  37.         if(k == 6) {
  38.             break;
  39.         }
  41.         if(b[i + k] > b[j + k]) {
  42.             i += k + 1;
  43.             if(i == j) {
  44.                 i++;
  45.             }
  46.         }
  47.         else {
  48.             j += k + 1;
  49.             if(i == j) {
  50.                 j++;
  51.             }
  52.         }
  53.     }
  55.     int st = min(i, j);
  56.     for(int i = 0; i < 6; i++) {
  57.         a[i] = b[st + i];
  58.     }
  59. }
  61. int main() {
  62.     int n;
  63.     scanf("%d", &n);
  65.     int b[6], c[6];
  66.     for(int i = 0; i < n; i++) {
  67.         for(int j = 0; j < 6; j++) {
  68.             scanf("%d", &b[j]);
  69.             c[5 - j] = b[j];
  70.         }
  71.         get_min(b);
  72.         get_min(c); // 处理雪花反转的最小表示
  73.         if(cmp1(b, c)) {
  74.             memcpy(a[i], b, sizeof b);
  75.         }
  76.         else {
  77.             memcpy(a[i], c, sizeof c);
  78.         }
  79.         d[i] = i;
  80.     }
  82.     sort(d, d + n, cmp2);
  84.     bool find = false;
  85.     for(int i = 1; i < n; i++) {
  86.         if(!cmp1(a[d[i - 1]], a[d[i]]) && !cmp1(a[d[i]], a[d[i - 1]])) {
  87.             printf("Twin snowflakes found.\n");
  88.             find = true;
  89.             break;
  90.         }
  91.     }
  93.     if(!find) {
  94.         printf("No two snowflakes are alike.\n");
  95.     }
  97.     return 0;
  98. }
  1. 树形地铁系统

给出一个01序列，0表示向从当前节点向其某个子节点走，1表示从当前节点回到父节点。现在给出2个长度相同的01串，询问这两个01串所表示的树结构是否相同。
这道题类似于求字符串的最小表示，比较最小表示是否相等，但是多了一个树的限制，即每个层次的节点肯定是先向子节点走，再回来（叶子节点除外），然后对属于该节点的下面的做一个最小表示，再把自己的结果返回给上一个层次的节点。因此从思路上看，过程中存在递归。这就是树的最小表示的模板。

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  7. string dfs(string &s, int &idx) {
  8.     idx++; // 每层入口必定是0
  9.     vector<string> segs;
  10.     while(s[idx] == '0') {
  11.         segs.push_back(dfs(s, idx)); // 将下一层次的子树的最小表示存下来
  12.     }
  13.     idx++; // 跳过结尾的1
  14.     sort(segs.begin(), segs.end());
  16.     string ans = "0"; // 添加头尾，拼接得到本层的最小表示
  17.     for(auto &seg : segs) {
  18.         ans += seg;
  19.     }
  20.     ans += "1";
  22.     return ans;
  23. }
  25. int main() {
  26.     int T;
  27.     scanf("%d", &T);
  28.     while(T--) {
  29.         string a, b;
  30.         cin >> a >> b;
  31.         int idx_a = 0, idx_b = 0;
  33.         a = "0" + a + "1", b = "0" + b + "1";
  34.         a = dfs(a, idx_a), b = dfs(b, idx_b);
  35.         if(a == b) {
  36.             printf("same\n");
  37.         }
  38.         else {
  39.             printf("different\n");
  40.         }
  41.     }
  44.     return 0;
  45. }