区间合并#

1
using pii = pair<int, int>;
2
vector<pii> a, res;
3

4
sort(a.begin(), a.end());
5
auto [st, ed] = a[0];
6
for (int i = 1; i < a.size(); ++i) {
7
    auto [st1, ed1] = a[i];
8
    if (st1 <= ed) {
9
        ed = max(ed, ed1);
10
    } else {
11
        res.push_back({st, ed});
12
        st = st1;
13
        ed = ed1;
14
    }
15
}
16
res.push_back({st, ed});

读题#

灵感#

1. 代码上串行，如果数据互相独立可视作并行
2. 第k个都是实虚指针
3. 移动隔板可看作合并空白区间

取整#

中点#

中点m取n的时候，偶数n，m在偏右，如遍历左边取到m的话，奇偶都是左边偏大，取n - 1的时候，奇数左偏大，偶数左右相等

中点m由n时，

1. 偶数n，m偏右中点，遍历左边取m的话，左偏大，不取的话，一样大。
2. 奇数n，m不偏不倚，遍历左边取m的话，左偏大，不取的话，右偏大

取的话

左[l, m]，右[m + 1, r]

不取的话

左[l, m - 1], 右[m, r]

中点m由n-1时

1. 偶数n，m偏左中点，遍历左边取m的话，一样大，不取的话，右偏大
2. 奇数n，m不偏不倚，遍历左边取m的话，左偏大，不取的话，右偏大

取的话

左[l, m]，右[m + 1, r]

不取的话

左[l, m - 1]，右[m, r]

和中点m由n时的取不取情况是镜像的，但是表达式只取决于左边取不取中点

$\lfloor \frac{n-1}{2} \rfloor$能把$1,2,3,4,5,6,\ldots$映射到$0,0,1,1,2,2,\ldots$

循环#

1
// n = 0 时也要输出 "0"，至少执行一次
2

3
do {
4

5
  digits.push_back(n % 10);
6

7
  n /= 10;
8

9
} while (n > 0);

1
do {
2

3
  cin >> x;
4

5
} while (x < 1 || x > 100); // 至少读一次，不合法就重来

1
// 找到下一个不同的元素
2

3
do { ++j; } while (j < n && a[j] == a[i]);

配置环境#

学校的破烂电脑扩展不更新的话Intelligence直接失效，没网的话要用Vscode只能用Code Runner

1
tasks:[
2
    {
3
        "type" : "cppbuild",
4
        "label" : "build",
5
        "command" : "g++",
6
        "args" : [
7
            "-g",
8
            "${file}",
9
            "-o",
10
            "${workspaceFolder}/bin/${fileBaseNameNoExtension}.exe"
11
        ]
12
    }
13
]

性能相关#

一些卡常的性能细节

离散化#

分两种，一种哈希，一种二分

1
struct discretization {
2
  unordered_map<string, int> m;
3

4
  discretization(const vector<string>& a) {
5
    for (int i = 0; i < a.size(); ++i) {
6
      m[a[i]] = i;
7
    }
8
  }
9

10
  int operator[](string x) {
11
    return m[x];
12
  }
13
} dt;

1
struct discretization {
2
  vector<int> help;
3

4
  discretization(const vector<int>& a) : help(a) {
5
    sort(help.begin(), help.end());
6
    help.erase(unique(help.begin(), help.end()));
7
  }
8

9
  int operator[](int x) {
10
    return ( lower_bound(help.begin(), help.end(), x) - help.begin() );
11
  }
12
}

元素迁移到完全二叉树上#

设完全二叉树元素数量为$m = 2^n - 1 + c$，要扩展到满二叉树，其中n为1-base的满足$c \ge 0$的最大层值，即$m < 2^{n + 1} - 1 + c$

故$2^n - 1 \le m < 2^{n + 1} - 1$，如果元素1-base的话那就是从上一层最后一个元素到该层的非最后一个元素

则 $n = floor(log_2(m + 1))$，

假如是满足$c > 0$而不是$c \ge 0$，则有$2^n - 1 < m \le 2^{n + 1} - 1$，即$2^n \le m < 2^{n + 1}$，1-base的话就是从该层第一个元素到该层最后一个元素。

则$n = floor(log_2(m))$， 理论上来讲$n = floor(log_2(m))$，需要开$1 << (n + 1) = 1 << (floor(log_2(m) + 1)$即$1 << bit\_width(m)$大小的数组