Algorithm

线段树模板题

题目：POJ 3468

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<iostream>

using namespace std;

const int maxN = 101111;

int N, Q;
int a[maxN];

class TreeNode {
public:
    int l, r;
    long long tag, sum;
    TreeNode *lch, *rch;
    
    TreeNode(int l, int r): l(l), r(r) {
        tag = sum = 0;
        lch = rch = NULL;
    }
    
    void Add(long long x) {
        tag += x;
        sum += x * (r - l + 1);
    }
    
    void PushDown() {
        if (tag != 0) {
            lch->Add(tag);
            rch->Add(tag);
            tag = 0;
        }
    }
    
    void Update() {
        sum = lch->sum + rch->sum;
    }
};

TreeNode* BuildTree(int* a, int l, int r) {
    TreeNode* v = new TreeNode(l, r);
    if (l == r) {
        v->sum = a[l];
        return v;
    }
    int mid = (l + r) / 2;
    v->lch = BuildTree(a, l, mid);
    v->rch = BuildTree(a, mid + 1, r);
    v->Update();
    return v;
}

void Add(TreeNode* v, int l, int r, int x) {
    if (l <= v->l && v->r <= r) {
        v->Add(x);
        return;
    }
    v->PushDown();
    int mid = (v->l + v->r) / 2;
    if (l <= mid) Add(v->lch, l, r, x);
    if (r > mid) Add(v->rch, l, r, x);
    v->Update();
}

long long GetSum(TreeNode* v, int l, int r) {
    if (l <= v->l && v->r <= r) return v->sum;
    v->PushDown();
    int mid = (v->l + v->r) / 2;
    long long res = 0;
    if (l <= mid) res += GetSum(v->lch, l, r);
    if (r > mid) res += GetSum(v->rch, l, r);
    return res;
}

void Work() {
    cin >> N >> Q;
    for (int i = 0; i < N; i++) scanf("%d", &a[i]);
    TreeNode* root = BuildTree(a, 0, N - 1);
    for (int i = 0; i < Q; i++) {
        char op = 0;
        while (op != 'C' && op != 'Q') op = getchar();
        int l, r, x;
        scanf("%d %d", &l, &r);
        l--, r--;
        if (op == 'C') {
            scanf("%d", &x);
            Add(root, l, r, x);
        }
        else if (op == 'Q') {
            printf("%lld\n", GetSum(root, l, r));
        }
        else throw "Invalid operation.";
    }
}

int main() {
    Work();
    return 0;
}
Algorithm

Kick Start 2020 Round D

题目：https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff08

A. Record Breaker

太简单，不说了

B. Alien Piano

一个简单的动态规划

C. Beauty of tree

题意

给定一棵N个点的树，根节点为1。Amadea会随机选择一个节点，将这个点涂黑，然后从这个点开始到根的路径上，每隔A个点涂黑一个。然后，Bilva随机选择一个节点，将这个点涂黑，然后从这个点到根的路径上，每隔B个点涂黑一个。设最终被涂黑的点的个数为X。求X的数学期望。$N\le5\times10^5$

做法

显然，子树中涂的点到子树根的距离不确定，所以没法用树形概率DP的方法。我们只能从期望的计算方法来思考。Amadea和Bilva的选择共有n^2种可能，所以答案等于每种选法中被涂黑的点数之和，然后除以$n^2$。

于是可以想到，我们不是按照每种选法计算，而是去计算每个点会在多少种选法中被涂黑。对于节点v，计算它的子树中到v的距离模A为0的节点个数（设为a），以及它的子树中到v的距离模B为0的节点个数（设为b）。由容斥原理，v会被涂黑的选法个数$=a\times n+b\times n-a\times b$。

那么如何得到每个节点的a和b呢？我们可以dfs，得到每个节点的深度。在dfs过程中，我们可以维护两个cnt数组，记录当前dfs过的点的深度分别模A和B结果的个数。那么dfs完一棵子树，根据cnt数组的变化即可得到当前节点的a和b。于是dfs一遍即可，时间复杂度$O(n)$。

暴力维护a和b

其实我刚开始没想到dfs一遍就可以。我想的是暴力维护。例如计算a。每个点维护一个map，map[x]表示v的子树中，到v的距离模A为x的点的个数。合并时，使用启发式合并。显然是能做的，应该也不会超时，用hash map，总复杂度O(nlogn)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

int n, A, B;
vector<int> children[501111];
int deep[501111];
int rec[2][501111];
int ans[501111][2];

void Dfs(int v, int dep) {
    int a = rec[0][dep % A];
    int b = rec[1][dep % B];
    deep[v] = dep;
    rec[0][dep % A]++;
    rec[1][dep % B]++;
    for (int y: children[v]) {
        Dfs(y, dep + 1);
    }
    ans[v][0] = rec[0][dep % A] - a;
    ans[v][1] = rec[1][dep % B] - b;
}

double Work() {
    for (int i = 0; i < 2; i++) {
        for (int j = 1; j <= n; j++) rec[i][j] = 0;
    }
    for (int i = 1; i <= n; i++) {
        ans[i][0] = ans[i][1] = 0;
    }
    Dfs(1, 0);
    long long tot = 0;
    for (int i = 1; i <= n; i++) {
        tot += (long long)n * (ans[i][0] + ans[i][1]) - (long long)ans[i][0] * ans[i][1];
    }
    long long tmp = (long long)n * n;
    return 1.0 * tot / tmp;
}

void AAAAA() {
    int T;
    cin >> T;
    for (int  tt = 1; tt <= T; tt++) {
        cin >> n >> A >> B;
        for (int i = 1; i <= n; i++) children[i].clear();
        for (int i = 1; i <= n - 1; i++) {
            int x;
            cin >> x;
            children[x].push_back(i + 1);
        }
        printf("Case #%d: %.12f\n", tt, Work());
    }
}


int main() {
    AAAAA();
    return 0;
}

D. Locked Doors

题意

有一行n个房间，编号1到n。相邻房间之间有一扇门，门的编号为1到n-1。每个门有一个困难度Di。Di互不相同。开始时门都关着。

如果一个人开始时在房间x，那么他会在能打开的两扇门中选择一扇困难度小的门打开。打开的门会一直开着。然后他一直进行此流程，经过n-1步之后，他会打开所有的门。

现在有Q个询问，每个询问给定S和K，假设开始时人在房间S，那么他访问的第K个房间是哪个。$n,Q\le10^5$

做法

没法模拟，所以需要观察一些性质。

很容易发现，打开的门是从S开始往左右不断延伸的。如果左边要打开门L，那么此时，右边延伸到的位置R一定满足：D[R]>=max(D[L], D[L+1]…D[S])。于是二分这个L，找到对应的R，判断是否>=K即可。查询最大值用ST表。时间复杂度O(qlogn)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <stack>
#include <map>

using namespace std;

int N, Q, S, K;
int D[101111];
int log[101111];
int go[101111];
int f[101111][20];
map<int, int> pos;

const int inf = 999999999;

void Prepare() {
    for (int i = 0; i <= N; i++) pos[D[i]] = i;
    for (int i = 0; i <= N; i++) f[i][0] = D[i];
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i <= N; i++) {
            int t = i + (1 << (j - 1));
            if (t < N) f[i][j] = max(f[i][j - 1], f[t][j - 1]);
        }
    }
    log[1] = 0;
    for (int i = 2; i <= N + 2; i++) {
        if (i == (i & -i)) log[i] = log[i - 1] + 1;
        else log[i] = log[i - 1];
    }
    stack<int> s;
    s.push(N);
    for (int i = N - 1; i >= 0; i--) {
        while (D[i] > D[s.top()]) s.pop();
        go[i] = s.top();
        s.push(i);
    }
}

int Getmax(int l, int r) {
    int len = r - l + 1;
    int t = log[len];
    return max(f[l][t], f[r - (1 << t) + 1][t]);
}

int Calc(int p) {
    int x = Getmax(p, S - 1);
    int a = pos[x];
    int b = go[a];
    return b - p;
}

int Work() {
    if (K == 1) return S;
    int l = 1, r = S - 1, res = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        int num = Calc(mid);
        if (num + 1 >= K) {
            res = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    int num = Calc(res);
    if (num + 1 == K) return res;
    else return res + K;
}

void AAAAA() {
    int T;
    cin >> T;
    for (int  tt = 1; tt <= T; tt++) {
        cin >> N >> Q;
        for (int i = 1; i <= N - 1; i++) cin >> D[i];
        D[0] = inf;
        D[N] = inf;
        Prepare();
        printf("Case #%d: ", tt);
        while (Q--) {
            cin >> S >> K;
            printf("%d ", Work());
        }
        printf("\n");
    }
}

int main() {
    AAAAA();
    return 0;
}
Algorithm

辗转相除法的一个奇妙的题

题意

给定四个整数n, a, b, c，求
$$\sum_{x=1}^n\lfloor\frac{a\times x+b}{c}\rfloor$$

做法

首先，如果$a=p\times c+q$，其中$q=a模c$，那么$p$是可以从下取整符号中提取出来的，答案需要加上$p\times\frac{n(n+1)}{2}$。同理，$b=p\times c+q$时，答案需要加上$p\times n$。

因此，我们只需考虑$a=a模c$与$b=b模c$即可。接下来是一系列神奇的式子。设$k=\lfloor\frac{a\times n+b}{c}\rfloor$，则

$$
\sum_{x=1}^n\lfloor\frac{a\times x+b}{c}\rfloor
$$
$$

\sum_{x=1}^n\sum_{i=1}^k\mathbf{1}(i\le\lfloor\frac{a\times x+b}{c}\rfloor)
$$
$$

\sum_{i=1}^k\sum_{x=1}^n\mathbf{1}(x\ge\lceil\frac{i\times c-b}{a}\rceil)
$$
$$
=\sum_{i=1}^k(n-\lfloor\frac{i\times c - b - 1}{a}\rfloor)
$$

于是，$a$和$c$交换了位置，可以递归调用该函数。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def brute_force(n, a, b, c):
    res = 0
    for x in range(1, n + 1):
        res += (a * x + b) // c
    return res


def f(n, a, b, c):
    if c == 0:
        return 0
    res = (a // c) * n * (n + 1) // 2 + (b // c) * n
    a %= c
    b %= c
    k = (a * n + b) // c
    return res + k * n  - f(k, c, -b - 1, a)


n = 1001293
a = 123
b = 4564
c = 789
print(brute_force(n, a, b, c))
print(f(n, a, b, c))

输出为：

1
2
3
$ python3 temp.py
78153838770
78153838770

还要注意一点，python中的整除与C++中的不太一样。

Python中：

1
2
-5 // 2 = -3
-5 % 2 = 1

C++中：

1
2
-5 / 2 = -2
-5 % 2 = -1
Algorithm

Leetcode 1531. String Compression II

题目

https://leetcode.com/problems/string-compression-ii/

字符串缩写：比如"aaabbbcdddddddddd"可以缩写为"a3b3cd10"。只有一个字母的话不需要写1。数字按十进制。

给定一个字符串s。你可以最多删除s中的k个字符，要使删除之后的s经过缩写之后长度最短。求这个最短长度。

做法

我的智障做法

f[i][j][p][q]表示前i个字符，删去j个，最后一个字符是p（连续q个），这样的最短长度。转移时讨论下一个位置保不保留即可。状态有$100\times100\times26\times100$个，转移O(1)。交上去TLE，优化了优化过了。

好的做法

显然，我们只需要关心最后一段就行了。设f[i][j]表示前i个字符，删去j个的最短长度。然后枚举k，我们需要让k到j变成同一段。因此记录一下k到j中出现次数最多的那个，其他字符都要删掉。次数最多的那个的话，倒着循环k，顺便维护即可。时间复杂度O(n^3)。

我的代码

https://leetcode.com/submissions/detail/373673723/

Algorithm

Codeforces Round #654 (Div. 2) F. Raging Thunder

题目

https://codeforces.com/contest/1371/problem/F

有一个长度为n的传送带，每个位置有一个方向（’<’或’>’表示向左或向右）。n个位置中间以及两端共有n+1个洞。当一个球落在上时，它会被往左传送，一直传送到头或者遇到一个往右的传送带，然后就会落到中间那个洞里，或者头上的洞里。

有q个操作，每个操作给定l和r，其将[l,r]之间的传送带反向（向左改为向右，向右改为向左），然后在[l,r]每个位置上都放一个球。这些球会落到某些洞里去，要求输出球最多的那个洞有多少个球。每次操作之后，反向了的传送带仍然保留，但洞里的球会消失，不会影响下次查询。

做法

这题目出的就跟线段树似的，所以肯定用线段树做了。

先不考虑反向操作，只考虑球回落到哪个洞里。分析可以发现，形如’>>>><<’这样的结构，球就会都落到中间那个洞里。而这样的结构的分界点是’<>’。我们只需要维护这种结构的最大长度即可。因此，需要维护的东西有：

  • 左右端点的方向
  • 最左边的这种结构的长度
  • 最右边的这种结构的长度
  • 当前区间的答案

合并的时候，分两种情况（是’<>’与不是’<>’分开讨论维护即可）。

现在有反向操作，如果反向了，上面维护的结构和分界点就不对了！那该怎么办呢？但是我们建树的时候，每个区间都维护一个正的和一个反的信息，反向操作就直接swap一下就行了。

代码

https://codeforces.com/contest/1371/submission/86937856

Algorithm

Codeforces Round #654 (Div. 2) E. Asterism

题目

https://codeforces.com/contest/1371/problem/E2

有一个游戏，规则如下：

  • 有n个敌人，第i个敌人能力值为a[i]。你的初始能力值为x。
  • 如果你的能力值>=敌人的能力值，你可以击败他。
  • 当你击败一个敌人后，你的能力值+1。
  • 你任意调整打敌人的顺序（即n的全排列种）。设f(x)为可以击败所有敌人的顺序方案数。

现在，给定n和a，以及一个整数p（0<p<=n），求所有的x，使得f(x)不能被p整除。

做法

首先肯定先将a[i]排序。那么，要击败所有敌人，x至少为max{a[i]}-n+1。而由于0和n!可以被p整除，所以必有max{a[i]}-n+1 <= x <= max{a[i]}-1。也就是说，可取的x最多只有n-2个。

通过手算可以发现，设b[i]为可以放在i位置之前的敌人数，那么$f(x)=\prod_{i=0}^{n-1}(b[i]-i)$。而当x增大1时，b[i]会变成b[i+1]。

这里一定要好好利用题目的性质。我们要求出哪些f(x)不能被p整除。我这里就在想怎么维护所有的b[i]-i模p的值，想了很久也没想出来。其实这题很简单，因为最后乘的一项一定是1，而b[i]-i最多只会减少1，所以只要有某一个b[i]-i大于等于p了，就一定会被p整除。

同时，由于x增大1，b[i]变为b[i+1]，而b数组肯定是不降的，因此如果f(x)>0能被p整除，那么比x大的都一定会被p整除。

所以，我们先确定最小的f(x)>0的x，然后二分查找右端点即可。每次O(n)看一下所有的b[i]-i是否满足条件即可。时间复杂度O(nlogn)。

代码

https://codeforces.com/contest/1371/submission/86764620

Algorithm

Codeforces Global Round 9 D. Replace by MEX

题目

http://codeforces.com/contest/1375/problem/D

有一个长度为n的数组a，其中a[i]$\in$[0, n]。你可以进行一种操作：将某个位置的数字替换为整个数组的MEX。

MEX定义为：The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array.

因此，n个0到n之间的数，其MEX也一定在0到n之间。

需要找到一个长度不超过2n的操作序列，使数组变成非降的。

做法

我们的目标就是让数组变为0, 1, 2… n-1。显然，我们可以求MEX，然后如果MEX在[0, n-1]之间，那么直接将对应位置的数替换，这样就多了一个位置的数字是正确的。如果MEX是n怎么办呢？由于要求的是长度不超过2n，所以可以加一次操作，将任意一个不正确的位置替换为n，然后再重复上面的流程。

如果MEX是x，位置x一定是不正确的吗？是的，因为x一定不再当前数组里。

如果每次暴力求MEX，那么时间复杂度是O(n^2)。

其实，如果MEX是n的话，那么此时数组是一个0到n-1的排列。于是，我们可以找到其中所有的置换圈。对于每一个圈，设大小为s，那么我们只需用n进去换一遍，就能得到正确的位置，所需次数为s+1。这样最坏只需1.5n次即可（即所有的圈大小为2）。

代码

http://codeforces.com/contest/1375/submission/86274403

一些乱七八糟的知识点（C++，Linux，OS等）

静态库和动态库的区别

简单来说，静态库会在编译出的可执行文件中包含库代码的一份完整拷贝。动态库是程序运行的时候由系统动态的加载到内存中供程序调用。

参考：

进程和线程的区别

进程是具有一定功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源调度和分配的一个独立单位。

线程是进程的实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。

一个进程可以有多个线程，多个线程也可以并发执行。一个进程中的不同线程共享同一块内存空间。

常量指针和指针常量

const int *p或int const *p：不能通过指针引用修改内存中的数据。

int* const p：指向的地址不能变，但是该内存中的数据可以改变。

参考：

网络的环形拓扑结构

注意数据是单向流动的。故一个节点出问题，网络就会崩溃。

参考：

C++ iomanip中的流控制函数

参考：

不同网络层次中的数据传输单位

  • 物理层：比特（Bit）
  • 数据链路层：数据帧（Frame）
  • 网络层：分组数据包（Packet）
  • 传输层：数据段（Segment）或报文

C++ std::thread, std::mutex等相关知识

#include <thread>：包括thread类及相关函数。

#include <mutex>：包括std::mutex, std::lock_guard, std::unique_lock等类，用来保证线程同步的，防止不同的线程同时操作同一个共享数据。

参考：