ACM►DP

CodeChef MOU2H - Mountain Holidays 2 （DP）

题目链接：

https://www.codechef.com/problems/MOU2H

题目大意：

理解题意后就是求一个序列中有多少个不同的子序列。

解题过程：

刚开始看错了题意，样例过不去，后来去翻了博客，才看懂题意，看懂题意后就好做了，就是一个简单的动态规划。

题目分析：

因为要求不同子序列的个数。

定义状态$dp[i]$为前[i]个数中，不同子序列的个数。那么对于dp[i]可以由已下方式转移而来，记$pre[A[i]]$为A$[i]$这个数字上次出现的下标，如果未出现为$-1$。

定义$dp[0]$为$1$代表一个空串。

那么dp[i]可由以下状态转移而来：

$$
dp[i] =
\begin{cases}
dp[i-1]\times 2 , &pre[A[i]] = -1 \
dp[i-1] \times 2 - dp[pre[A[i]]-1], &pre[A[i]] \neq -1
\end{cases}
$$

如果前i-1个数的不同子串个数为N，那么加上第i个数之后，对于前i个不同的子串加上第i个数后都构成了一个新的串，那么对于前i个数的不同子串为，前i-1的不同子串个数+新构成的子串个数。

不过如果第i个数曾经出现过的话，需要去重处理，如果3这个数字，在$5$和$9$这个位置都出现过的话，那么前$4$个数的子串后面加上第$5$个数和加上第$9$个数，构成的子串相同，这里需要减去最近出现的前一个位置的不同子串个数。
这里需要仔细理解下，$dp[i]$代表的是前$i$个元素构成的不同子串的个数，不是以元素$i$结尾的最大子串个数。

这里介绍一个骚操作，数组的下标可以为负数，对于下面代码。

1
2
3
int a[3] = {1, 2, 3};
int *p = a+1;
cout << p[-1] << endl;

输出的结果为1

AC代码：

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
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1123456;
const int INF = MAX<<2;
const int MOD = 1000000009;

int H[MAX];
int reserve[MAX*10], *pre = reserve+INF;
int dp[MAX];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", H+i);
        }
        for (int i = 1; i < n; i++) {
            H[i] = H[i+1] - H[i];
            pre[H[i]] = -1;
        }
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = (dp[i-1]<<1)%MOD;
            if (pre[H[i]] != -1) {
                dp[i] = (dp[i] - dp[pre[H[i]]-1] + MOD)%MOD;
            }
            pre[H[i]] = i;
        }
        printf("%d\n", (dp[n-1]-1+MOD)%MOD);
    }
}
ACM►数据结构►线段树

HDU4027 - Can you answer these queries? （线段树）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4027

题目分析：

区间开根号下取整，询问区间和。

解题过程：

注意，进行更新和询问的操作的时候要注意$x$和$y$的大小，这里被坑了，差点以为自己清奇的脑洞不对……

发现好多人都是转化为单点更新，自己比较耿直，写了好长的区间更新代码，也算是一题多解吧。

题目分析：

单点更新解法：

首先要注意到对于开根号操作，这里的输入数据大小不会超过$2^{64}$要不就没法玩了，这样的话，对于每个数顶多开$64$次根号。

这样暴力进行单点更新最多也就$O(64\times nlog(n))$，加上剪枝就可以过，对于每个区间，如果这个区间内的所有数都为$1$，那么这个区间开根号后区间和也没变化了，可以剪枝。

区间更新解法：

因为要进行区间更新，所以要用到lazy标记，但是用lazy标记要保证两个条件，一是标记可以叠加，二是打上标记后可以直接的更新区间维护的信息。

对于开根号操作，好像是不符合第二个条件，对于一个区间打上lazy标记后，不能直接计算出新的区间和。这里想到可以预处理前缀和，因为每个数最多也就开$64$次根号，预处理完对于开$1$到$64$次根号所有的前缀和，这里加下判断，如果所有数都为$1$的话，那么就不需要继续往下计算了。

有了前缀合，那么对于一段区间如果这段区间内所有数字开根号的次数都相同，那么我就可以用前缀和计算出区间和了。所以当一段区间内所有数的开根号次数都一样的话，就可以打lazy标记了。

然后注意更新和合并区间的过程，更新有可能会使一段区间内开根号次数不同，或变得相同，合并区间时要处理一下。

AC代码：

单点更新：

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
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

#define lson root<<1
#define rson root<<1|1
#define MID int m = (l + r) / 2

typedef long long LL;

const int MAX = 112345;

struct Info {
    LL value;
}tree[MAX<<2];

LL data[MAX];

void build(int root, int l, int r) {
    if (l == r) {
        tree[root].value = data[l];
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m+1, r);
    tree[root].value = tree[lson].value + tree[rson].value;
}

void updata(int root, int l, int r, int ul, int ur) {
    if (r < ul || ur < l || tree[root].value <= (r-l+1))
        return;
    if (ul <= l && r <= ur && l == r) {
        tree[root].value = sqrt(tree[root].value);
        return;
    }
    MID;
    updata(lson, l, m, ul, ur);
    updata(rson, m+1, r, ul, ur);
    tree[root].value = tree[lson].value + tree[rson].value;
}

LL query(int root, int l, int r, int ul, int ur) {
    if (r < ul || ur < l)
        return 0;
    if (ul <= l && r <= ur) {
        return tree[root].value;
    }
    MID;
    return query(lson, l, m, ul, ur) + query(rson, m+1, r, ul, ur);
}

int main() {
    int n, m, cases = 0;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &data[i]);
        }
        build(1, 1, n);
        scanf("%d", &m);
        printf("Case #%d:\n", ++cases);
        while (m--) {
            int top, x, y;
            scanf("%d %d %d", &top, &x, &y);
            if (x > y)
                swap(x, y);
            if (top) {
                printf("%lld\n", query(1, 1, n, x, y));
            }
            else {
                updata(1, 1, n, x ,y);
            }
        }
        putchar('\n');
    }
}

区间更新：

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<stdio.h>
#include<math.h>
#include <algorithm>
using namespace std;

#define lson root<<1
#define rson root<<1|1
#define MID int m = (l+r)/2

const int MAX = 112345;
typedef long long LL;

LL pre[64][MAX];

int times;

struct Info {
    int lazy, l, r, num;
    bool ok;
    LL value;
    Info() {
        lazy = l = r = ok = num = value = 0;
    }
    void maintain(int v) {
        num += v;
        //如果开根号大于times次，那么和开times次相同
        if (num > times)
            num = times;
        value = pre[num][r] - pre[num][l-1];
    }
}tree[MAX*4];

void push_down(int root) {
    if (tree[root].lazy) {
        int v = tree[root].lazy;
        tree[lson].lazy += v;
        tree[rson].lazy += v;
        //打完lazy标记后重新计算下区间和
        tree[lson].maintain(v);
        tree[rson].maintain(v);
        tree[root].lazy = 0;
    }
}

Info operator + (const Info & a, const Info & b) {
    Info rst;
    rst.l = a.l;
    rst.r = b.r;
    //如果左右儿子开根号次数相同，并且区间内所有元素开根号次数都相同，那么父节点区间内开根号次数都相同
    rst.ok = (a.num == b.num) && a.ok && b.ok;
    if (rst.ok) {
        rst.num = a.num;
        rst.maintain(0);
    }
    return rst;
}

void updata(int root, int l, int r, int ul, int ur) {
    //如果区间内所有元素都为1，那么可以跳过更新
    if(r-l+1==tree[root].value) return;
    //如果区间在更新的区间内，并且区间内所有元素开根号次数都相同，那么可以打lazy标记
    if (ul <= l && r <= ur && tree[root].ok) {
        tree[root].lazy += 1;
        tree[root].maintain(1);
        return;
    }
    MID;
    push_down(root);
    if (ul <= m) updata(lson, l, m, ul, ur);
    if (m+1 <= ur) updata(rson, m+1, r, ul, ur);

    tree[root] = tree[lson] + tree[rson];
}

void build(int root, int l, int r) {
    tree[root].l = l;
    tree[root].r = r;
    tree[root].value = 0;
    tree[root].lazy = 0;
    tree[root].ok = 1;
    tree[root].num = 0;
    if (l == r) {
        tree[root].maintain(0);
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m+1, r);
    tree[root].value = tree[lson].value + tree[rson].value;
}

LL query(int root, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr && tree[root].ok) {
        return tree[root].value;
    }
    MID;
    push_down(root);
    LL sum = 0;
    if (ql <= m) sum += query(lson, l, m, ql, qr);
    if (m+1 <= qr) sum += query(rson, m+1, r, ql, qr);
    return sum;
}

int main() {
    int n, cases = 0;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &pre[0][i]);
            pre[1][i] = sqrt(pre[0][i]);
            pre[0][i] += pre[0][i-1];
        }

        //处理前缀和
        for (int i = 1; i <= 64; i++) {
            bool flag = 0;
            for (int j = 1; j <= n; j++) {
                if (pre[i][j] != 1)
                    flag = 1;
                pre[i+1][j] = sqrt(pre[i][j]);
                pre[i][j] += pre[i][j-1];
            }
            //如果所有元素均为1，就不用处理后面的前缀和了
            if (!flag) {
                //times为最多多少次，所有数字均变为1
                times = i;
                break;
            }
        }

        build(1, 1, n);
        int m;
        scanf("%d", &m);
        printf("Case #%d:\n", ++cases);
        while (m--) {
            int top, x, y;
            scanf("%d %d %d", &top, &x, &y);
            if (x > y)
                swap(x, y);
            if (top) {
                printf("%lld\n", query(1, 1, n, x, y));
            }
            else {
                updata(1, 1, n, x, y);
            }
        }
        putchar('\n');
    }
}
ACM►数据结构►线段树

HDU1394 - Minimum Inversion Number（线段树）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1394

题目大意：

给定一个由$0$到$n-1$组成，长度为$n$每个元素唯一的序列，可以进行一种操作，把第一个元素放到最后一个位置。求经过若干次操作后的，最小逆序对数。

解题过程：

这题之前写过一个暴力解法的题解，现在用线段树来解决一下。

题目分析：

这里用线段树主要是求解初始状态的逆序对数，对于每次的操作有一个结论可以用。

要求逆序对数，那么对于每个数我要求在这个数之前有多少个大于这个数的元素。

因为序列的元素是从$0$到$n-1$的，那么我用$n$个叶子节点去维护这些值是否出现过，出现置$1$否则为$0$，对于非叶子节点就维护区间内数字出现的个数，那么我要查询比$a$大的数有几个，那么我只需要查询$[a, n]$这个区间的值就好了。

这题比较容易做，其他题可能也会用到这个思想，不过数字不是从$0$到$n-1$的，需要离散化一下。

AC代码：

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
#include <bits/stdc++.h>
using namespace std;

#define lson root<<1
#define rson root<<1|1
#define MID int m = (l + r) / 2

const int MAX = 5000+10;

int data[MAX], tree[MAX<<2];

void build(int root, int l, int r) {
    if (l == r) {
        tree[root] = 0;
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m+1, r);
    tree[root] = tree[lson] + tree[rson];
}

void updata(int root, int l, int r, int pos) {
    if (pos < l || pos > r)
        return;
    if (l == r) {
        tree[root] = 1;
        return;
    }
    MID;
    updata(lson, l, m, pos);
    updata(rson, m+1, r, pos);
    tree[root] = tree[lson] + tree[rson];
}

int query(int root, int l, int r, int ql, int qr) {
    if (qr < l || r < ql)
        return 0;
    if (ql <= l && r <= qr) {
        return tree[root];
    }
    MID;
    return query(lson, l, m, ql, qr) + query(rson, m+1, r, ql, qr);
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        build(1, 1, n);
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &data[i]);
            data[i] += 1;
            //这里处理了一下，下标从1开始比较方便
            //大于data[i]，查询[data[i], n]区间的值就是i之前比data[i]大的元素的个数
            sum += query(1, 1, n, data[i], n);
            updata(1, 1, n, data[i]);
        }
        int rst = sum;
        for (int i = 1; i <= n; i++) {
            sum += n - data[i];
            sum -= data[i] - 1;
            rst = min(sum, rst);
        }
        printf("%d\n", rst);
    }
}
ACM►知识小结

线段树小结

前言：

实验室要开展每周的算法讲堂活动，大概是每周一个集训队员来给大家将一个知识点，于是我去讲线段树来开头了，但是自己好弱啊，自从寒假集训后就一直没敲过线段树代码了，于是这几天一直在照着金巨巨的博客刷线段树的题（也是抄的金巨巨的模板…）。

这里总结一些做到的题，一些线段树的基本思路，也当做理一下总结的思路。

用到的一些宏定义：

1
2
3
#define lson root<<1
#define rson root<<1|1
#define MID int m = (l + r) / 2

线段树的基本概念：

如果把线段树当做一个数据结构的话，那么可以这样解释线段树：

首先线段树是一颗二叉树，特殊的是线段树的每个节点，用来维护一段区间的信息，通常的写法都是这样，假设父节点维护的区间是$[a, b]$，那么他的左右儿子维护的区间分别是$[a, (a+b)/2], [(a+b)/2+1, b]$。

一个节点维护的信息通常有，区间和，区间连续子串和，区间最大值，区间最小值等。

建树过程：

构造一颗线段树的过程，可以参考分治算法的步骤：

  1. 假设要计算区间$[a, b]$中需要维护的信息，我们将这个问题分解成计算$[a, (a+b)/2], [(a+b)/2+1, b]$中需要维护的信息两个子问题，这样子问题与原问题的形式一样，只是规模更小.
  2. 对于第一步分解出的每个子问题，继续使用第一步进行分解得到规模更小的子问题，直到问题的规模足够小，可以直接求解。通常来讲是区间长度为$1$的时候，这样容易计算出需要维护的信息，比如区间和、区间极值等可以以$O(1)$的时间直接计算出。
  3. 最后一步是将上面分解出的子问题的解，合并成原问题的解，通常这一步也是最难的一步。

下面是建树的代码，完美的符合了上述过程。
这里需要注意的一点是，对于每个节点，要么他是一个叶子节点，要么他是一个同时具有左右儿子的节点。

1
2
3
4
5
6
7
8
9
10
void build (int root ,int l, int r) {
    if (l == r) {
        tree[root].maintain(data[l], l);
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m+1, r);
    tree[root] = tree[lson] + tree[rson];
}

通过上述分治的步骤，我们也可以另一种方式理解线段树：
我们要解决一个大问题，然后我们用分治的方法是解决这个问题，不过这里我们要把每一步解决的子问题的解都记录下来。这样所有子问题的解，和原问题的解就构成了一颗线段树。

更新：

线段树的更新过程，也是递归来实现的。这里以单点更新来举例，因为线段树是储存着许多子问题的解的，所以对一个点进行更新，可能会对多个子问题有影响，这里我们也用分治算法去更新。

假设要对$[1,n]$的区间下标为$p$的点进行更新。那么对于$[1,n]$区间可以先对他的两个儿子节点$[1,(1+n)/2], [(1+n)/2+1, r]$进行更新，$[1,n]$区间可由更新后的两个儿子节点组合而成。对他的两个儿子节点也进行如下操作，直到一个节点可以直接计算出更新后的变化。

下面是更新的代码，符合上述过程，不过这里加入了一个剪枝，如果需要更新的点不在当前节点维护的区间，那么这次更新对当前节点一点没有影响，不需要继续向下更新。

1
2
3
4
5
6
7
8
9
10
11
12
void updata(int root, int l, int r, int pos, int v) {
    if (pos < l || r < pos)
        return;
    if (l == r) {
        tree[root].maintain(v, pos);
        return;
    }
    MID;
    updata(lson, l, m, pos, v);
    updata(rson, m+1, r, pos, v);
    tree[root] = tree[lson] + tree[rson];
}

查询：

查询过程其实就是用已经解决的子问题的解去构造新问题的解的过程。

比如之前说过，对于一个维护$[1,n]$区间的线段树，它里面就存着着分治解决$[1,n]$这个问题的所有子问题的解。那么对于每次查询区间$[l,r],1\leq l \leq r \leq n$，都是一个规模小于$[1,n]$的问题。那么对于这个问题的解，可以用解决$[1,n]$问题的子问题的解构造出来。

以下是查询过程中的代码，就是遍历原问题的所有子问题的解，去构造新问题的解，这里加入了剪枝，如果一个区间和需要查询的区间没有交集，那么就可以剪枝。

1
2
3
4
5
6
7
8
9
Info query(int root, int l, int r, int ql, int qr) {
    if (qr < l || r < ql)
        return Info();
    if (ql <= l && r <= qr) {
        return tree[root];
    }
    MID;
    return query(lson, l, m, ql, qr) + query(rson, m+1, r, ql, qr);
}

合并：

所谓合并就是合并两个节点为一个节点，也就是合并子问题，构造原问题解的过程。

比如我分别知道$[a, b]$和$[b+1, c]$区间的最大值为$x_1, x_2$，那么区间$[a, b]$的最大值，那么就是$max(x_1, x_2)$。这样就用这两段区间的解构造出了另一个区间的解。

这里重载了加号，用起来比较方便。

1
2
3
4
5
Info operator + (const Info & a, const Info & b) {
    Info rst;
    rst.value = max(a.value, b.value);
    return rst;
}

当然这只是一个简单的例子，在许多线段树中合并起来非常麻烦，比如求一段区间内的最大的连续子串和。

对于区间$[1, n]$，那么最长连续子串和一定来自于以下的三种：

  • 区间$[1,(n+1)/2]$的最长连续子串和；
  • 区间$[(n+1)/2+1, n]$的最长连续子串和；
  • 区间$[1,(n+1)/2]$的从右端开始的最长连续子串和加上区间$[(n+1)/2+1,n]$从左端开始的最长连续子串和。

对于每段区间需要维护三个信息，从左端开始的最长连续子串和，从右端开始的最长连续子串和，最长连续子串和。分别记为lmax,rmax,value。

那么合并两个区间的代码如下：

1
2
3
4
5
6
7
8
Info operator + (const Info & a, const Info & b) {
    Info rst;
    rst.lmax = max(a.lmax, a.sum + b.lmax);
    rst.rmax = max(b.rmax, a.rmax + b.sum);
    rst.sum = a.sum + b.sum;
    rst.value = max(max(a.value, b.value), a.rmax + b.lmax);
    return rst;
}

这里为了方便操作，记录了区间的和。

ACM►知识小结

匹配、覆盖、独立集、二分图与网络流

概念：

设图 $G = {V, E}$

  • 匹配：在$G$中两两没有公共端点的边集合$M\subseteq E$
  • 边覆盖：$G$中任意顶点都至少是$F$中某条边的端点的边集合$F\subseteq E$
  • 独立集：在$G$中两两互不相连的顶点集合$S\subseteq V$
  • 顶点覆盖：$G$中的任意边都有至少一个端点属于$S$的顶点集合$S\subseteq V$

定理：

  1. 对于不存在独立点的图，$|\text{最大匹配数}|+|\text{最小边覆盖}|=|V|$
  2. $|\text{最大独立集}|+|\text{最小顶点覆盖}|=|V|$
  3. 对于二分图，$|\text{最大匹配}| = |\text{最小顶点覆盖}|$

不严谨的理解：

一：

可以想象，最小边覆盖可以通过最大匹配加边来完成，但是要加多少条边呢？

假设图$G$的最大匹配为$M$，那么这时还有$|V|-2\times|M|$个点没有覆盖，这时需要$|V|-2\times |M|$条边进行覆盖这些点。可以贪心的想，要尽可能的用一条边覆盖尽量多的点，但是一条边覆盖两个点的情况是不存在的，因为如果一条边可以覆盖两个新的点，那么当前的匹配就不是最大匹配了，与假设矛盾。所以每个点都要加一条边进行覆盖。

由此可知，图G的最小边覆盖为：$|F| = |M|+|V|-2\times|M| = |V|-|M|$
移项可得：$|F|+|M|=|V|$

关于为什么不能有孤立的点呢，因为这些孤立点一条边都没有，最后$|V| > |F|+|M|$

二：

可以这样理解，现在图G要删除一些点，构造最小顶点覆盖，要删除哪些点呢？

一个思路是删除一组两两独立的点，因为这样删除点，不会导致一条边的两个端点都被删去。如果一条边的两个端点都被删去了，那么删去的点也就不是互相独立的了。这样要构造最小的顶点覆盖，就要尽量多的删去两两独立的点，那么就是$V$删去最大独立集了。

三：暂时还没找到比较容易理解的方式

ACM►搜索►BFS

ZOJ3781 - Paint the Grid Reloaded（缩点+最短路）

题目链接：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3781

题目大意：

给定一个$N\times M$的矩阵，每个格子涂着黑色或白色。现在有一种涂色操作，每次涂色可以将一个格子与这个格子连通的格子涂成一个颜色。连通是指上下左右的边相接。

求最少的操作次数，将这个矩阵涂成一种颜色。

解题过程：

很久以前比赛的题，当时看到这个题一点想法都没有，后来补题看到了是缩点和求最长路，感觉非常神奇，也是第一次接触缩点的思想。

题目分析：

因为每次操作可以将相邻的格子涂成一个颜色，那么我可以将相同颜色连通的格子缩成一个点，与这一块连通格子相邻的相反颜色的点建边。

我们以一块连通块为中心，不断重复的将这一连通块涂成相反的颜色，那么最终会把整个矩阵涂成一个颜色。因为将这个连通块涂成反色的话，这个连通块就会和周围反色的连通块连成一个更大的连通块。

那么最少的操作次数，就遍历所有的点，以某个点为起点，BFS求出的最大步数为以这个点为起点的最少操作数。

为什么这样操作是最少的呢？这样建图构成的是一个二分图，然后想一下就知道了。

AC代码：

BFS染色：

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
99
100
101
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1600+5, INF = 0x3f3f3f3f;

int n, m, top;
char map_data[MAX][MAX];
int data[MAX][MAX], vis[MAX];
int dirc[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
vector<int> G[MAX];

//判断是否出界
inline bool edge(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}


//用来BFS给图染色
void bfs(int x, int y) {
    queue<pair<int, int> > q;
    data[x][y] = top;
    q.push(make_pair(x, y));
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = x + dirc[i][0];
            int ty = y + dirc[i][1];
            if (edge(tx, ty) && map_data[x][y] == map_data[tx][ty] && !data[tx][ty]) {
                q.push(make_pair(tx, ty));
                data[tx][ty] = top;
            }
            else if (edge(tx, ty) && data[tx][ty] && data[tx][ty] != data[x][y]) {
                int a = data[x][y], b = data[tx][ty];
                G[a].push_back(b);
                G[b].push_back(a);
            }
        }
    }
}


//染色
void flood_fill() {
    memset(data, 0, sizeof(data));
    top = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!data[i][j]) {
                top++;
                bfs(i, j);
            }
        }
    }
}

//找出以当前点为起点的最长路
int check_depth(int u) {
    queue<pair<int, int> > q;
    q.push(make_pair(u, 0));
    memset(vis, 0, sizeof(vis));
    vis[u] = 1;
    int max_depth = 0;
    while (!q.empty()) {
        u = q.front().first;
        int depth = q.front().second;
        max_depth = max(depth, max_depth);
        q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (!vis[v]) {
                q.push(make_pair(v, depth+1));
                vis[v] = 1;
            }
        }
    }
    return max_depth;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);

        for (int i = 0; i <= n*m; i++) {
            G[i].clear();
        }

        for (int i = 0; i < n; i++) {
            scanf("%s", map_data[i]);
        }
        flood_fill();
        int ans = INF;
        for (int i = 1; i <= top; i++) {
            ans = min(check_depth(i), ans);
        }
        printf("%d\n", ans);
    }
}

DFS染色：

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
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1600+5, INF = 0x3f3f3f3f;

int n, m, top;
char map_data[MAX][MAX];
int data[MAX][MAX], vis[MAX];
int dirc[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

vector<int> G[MAX];

inline bool edge(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

void dfs(int x, int y, int num, char c) {
    for (int i = 0; i < 4; i++) {
        int tx = x + dirc[i][0];
        int ty = y + dirc[i][1];
        if (!edge(tx, ty))
            continue;
        if (!data[tx][ty] && map_data[tx][ty] == c) {
            data[tx][ty] = num;
            dfs(tx, ty, num, c);
        }
        else if (map_data[tx][ty] != c && data[tx][ty]) {
            int v = data[tx][ty];
            G[v].push_back(num);
            G[num].push_back(v);
        }
    }
}

void flood_fill() {
    memset(data, 0, sizeof(data));
    top = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!data[i][j]) {
                data[i][j] = ++top;
                dfs(i, j, top, map_data[i][j]);
            }
        }
    }
}

int check_depth(int u) {
    queue<pair<int, int> > q;
    q.push(make_pair(u, 0));
    memset(vis, 0, sizeof(vis));
    vis[u] = 1;
    int max_depth = 0;
    while (!q.empty()) {
        u = q.front().first;
        int depth = q.front().second;
        max_depth = max(depth, max_depth);
        q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (!vis[v]) {
                q.push(make_pair(v, depth+1));
                vis[v] = 1;
            }
        }
    }
    return max_depth;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);

        for (int i = 0; i <= n*m; i++) {
            G[i].clear();
        }

        for (int i = 0; i < n; i++) {
            scanf("%s", map_data[i]);
        }
        flood_fill();
        int ans = INF;
        for (int i = 1; i <= top; i++) {
            ans = min(check_depth(i), ans);
        }
        printf("%d\n", ans);
    }
}
ACM►图论►最短路

POJ3259 - Wormholes（连通图判断负环）

题目链接；

http://poj.org/problem?id=3259

题目大意：

给出N个图，每个图有两种边，一个是无向的正权边，一种是有向的负权边，保证所给的图为连通图，求是否存在负环。

解题过程：

刚开始以为给出的图不连通，然后用Floyd超时，后来问了学长，翻了下POJ的讨论，发现大家都是默认为图连通做的……

然后敲了下Bellman和SPFA判断负环就A了。

题目分析：

因为保证图联通，那么可以假设从任意一点出发。

Bellman：如果松弛操进行N次依然可以松弛，那么存在负环。
SPFA：如果一个点入队次数大于等于N次，那么处在负环。

AC代码：

Bellman：

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
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;

struct Node {
    int u, v, w;
}edge[2500*10];

LL dist[1123];

int main() {
    int f;
    scanf("%d", &f);
    while (f--) {
        int n, m, w;
        scanf("%d %d %d", &n, &m, &w);
        for (int i = 0; i < m; i++) {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            edge[i*2] = {u, v, c};
            edge[i*2+1] = {v, u, c};
        }
        m *= 2;
        for (int i = 0; i < w; i++) {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            edge[i+m] = {u, v, -c};
        }

        bool flag = false;
        memset(dist, 0x3f, sizeof(dist));
        dist[1] = 0;
        for (int k = 0; k <= n; k++) {
            for (int j = 0; j < m + w; j++) {
                int u = edge[j].u;
                int v = edge[j].v;
                int w = edge[j].w;
                if (dist[v] > dist[u] + w) {
                    if (k == n)
                        flag = true;
                    dist[v] = dist[u] + w;
                }
            }
        }


        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
}

SPFA：

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
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef long long LL;


vector<pair<int, int> > edge[1123];
int dist[1123], cnt[1123];
bool vis[1123];

int main() {
    int f;
    scanf("%d", &f);
    while (f--) {
        int n, m, w;
        scanf("%d %d %d", &n, &m, &w);
        for (int i = 0; i <= n; i++) {
            edge[i].clear();
        }
        for (int i = 0; i < m; i++) {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            edge[u].push_back(make_pair(v, c));
            edge[v].push_back(make_pair(u, c));
        }
        for (int i = 0; i < w; i++) {
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            edge[u].push_back(make_pair(v, -c));
        }

        bool flag = false;
        memset(dist, 0x3f, sizeof(dist));
        memset(cnt, 0, sizeof(cnt));
        queue<int> q;
        q.push(1);
        dist[1] = 0;
        vis[1] = true;

        while (!q.empty()) {
            int u = q.front();
            for (int i = 0; i < edge[u].size(); i++) {
                int v = edge[u][i].first;
                int w = edge[u][i].second;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    if (++cnt[v] >= n) {
                        flag = true;
                        break;
                    }
                    if (!vis[v]) {
                        q.push(v);
                    }
                }
            }
            q.pop();
            vis[u] = false;
        }

        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
}
ACM►DP

UVA12511 - Virus（DP+最长公共上升子序列）

题目链接：

https://vjudge.net/problem/UVA-12511

题目大意：

给定两个序列，求出两个序列的最长公共上升子序列（严格上升）。

解题过程：

比赛的时候没有做出来，非常咸鱼的一场比赛，当时是想错了状态。当时想的状态是定义$dp[i][j]$，意味以第一个串第前i个元素，第二个串前j个元素的最长公共上升子序列长度。

但是这样定义状态有后效性，比如当前我知道$dp[i][j]$要以这个状态进行转移的话，需要他是以那个状态转移而来的，换句话说，我转移的时候要知道他是以前j个数中那一个结尾的。

如果换一种方式，$dp[i][j]$代表以第一个序列前i个元素并且以第i个结束，第二个序列前j个元素并且以第j个元素结尾的最长上升子序列的长度。

这样加入的限制太多，不容易找出状态转移方程，或者转移起来太麻烦。

题目分析：

这里以$dp[i][j]$表示第一个序列中前i个元素，第二个序列前j个元素并且以第j个元素为结尾的最长上升子序列。

这样对比前两种状态表示方式有两种好处，一是无后效性，$dp[i][j]$的第二维就确定了这个序列是以那一个元素结尾。二是容易进行转移，对于$dp[i][j]$可由两种方式转移而来：

$$
dp[i][j] =
\begin{cases}
dp[i-1][j] , &a[i] \ne b[i] \
max(dp[i-1][k])+1, &k \in [1, j-1] \wedge b[k] < b[j] \wedge a[i] = b[i]
\end{cases}
$$

这里的k可以在循环中找出，时间复杂度为$O(n^2)$.

AC代码：

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
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1123;

int dp[MAX][MAX], a[MAX], b[MAX];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        scanf("%d", &m);
        for (int i = 1; i <= m; i++) {
            scanf("%d", &b[i]);
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            int maxn = 0;
            for (int j = 1; j <= m; j++) {
                //不相等时的转移
                dp[i][j] = dp[i-1][j];
                //更新maxn变量，表示当前小于a[i]的dp[i-1][k]的最大值
                if (a[i] > b[j] && maxn < dp[i-1][j])
                    maxn = dp[i-1][j];
                //相等的话
                if (a[i] == b[j])
                    dp[i][j] = maxn+1;
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            ans = max(ans, dp[n][i]);
        }
        printf("%d\n", ans);
    }
}
CS课程

使用OpenMP实现并行归并排序（Report）

归并排序算法：

归并排序算法是一种经典的分治算法。

分治

分治算法分为由三部分组成：
分解：将原问题分解为一系列子问题；
解决：递归的解决各个子问题。若子问题足够小，那么直接求解。
合并：将子问题的结果合并成原问题。

归并排序步骤

归并排序完全依照了上述模式，直观的操作如下：
分解：将n个元素分成各含n/2个元素的子序列；
解决：用合并排序法对两个子序列递归地排序；
合并：合并两个已经排序的子序列，已得到排序结果。
这里递归的边界是序列长度为1时，显然是有序的。

合并过程

这里最关键的步骤，是合并步骤里如何合并两个有序的序列，并保证合并后的序列依然有序。

假设有序的序列为递增的，A、B为需要合并的序列，C为合并后的结果序列，p、q分别为A和B的下标，top为C的下标。定义如果一个下标大于序列的长度后，表示的值为无穷大。

初始状态：p、q、top均为0.

操作：选择A[p]和B[q]中的小的元素，加入到C[top]中，然后让较小的元素所在的序列的下标加一，top加一。当A[p]和B[q]均为无穷大时，结束操作。

由于每次操作均是比较A[p]和B[q]，然后取较小者加入C中，显然时间复杂度是O(n)的。

归并排序时间复杂度分析：

假设归并排序一个长度为n的序列需要的时间为T(n)。
首先归并排序分如下三个步骤：
分解：这一步是把序列分为两个子序列，只需要常量时间，O(1)；
解决：递归的解决规模为n/2的两个子问题，时间为2*T(n/2)；
合并：上面已经证明，只需时间O(n)。

那么接下来可以UI递归的表示出所需的时间T(n):
当n = 1是，T(n) = O(1)；
否则：T(n) = 2*T(n/2) + O(n)。

可以证明出上述的T(n)其实就是O(n*log(n))。

T(n) = 2T(n/2) + O(n)
= 2(2T(n/4) + O(n/2) + O(n)
= 4T(n/4) + 2O(n/2) + O(n)
= 4T(n/4) + 2O(n)
= 8T(n/8) + 8O(n/8) + 2O(n)
= 8T(n/8) + 3O(n)
= xT(1) + yO(n)

显然y即为n除多少次才为1，y = log2(n)，x等于2^y，那么T(n) = O(n*log(n))。

一个容易理解的代码：

Python is very beautiful！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def merge_sort(array):
    if len(array) > 1:
        mid = len(array) / 2
        left = merge_sort(array[:mid])
        right = merge_sort(array[mid:])
        return merge(left, right)
    return array


def merge(left, right):
    rst = []
    while len(left) > 0 or len(right) > 0:
        if len(right) == 0 or len(left) != 0 and left[0] < right[0]:
            rst.append(left.pop(0))
        else:
            rst.append(right.pop(0))
    return rst

串行过程：

串行排序代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void merge_sort(int *A, int x, int y, int *T) {
    if (y - x > 1) {
        int m = x + (y-x)/2;
        int p = x, q = m, i = x;
        merge_sort(A, x, m, T);
        merge_sort(A, m, y, T);
        
        while (p < m || q < y) {
            if (q >= y || (p < m && A[p] <= A[q])) {
                T[i++] = A[p++];
            }
            else {
                T[i++] = A[q++];
            }
        }
        for (i = x; i < y; i++) {
            A[i] = T[i];
        }
    }
}

串行求和代码：

1
2
3
4
5
6
7
int get_sum(int* data, int N) {
    int sum = 0, i;
    for (i = 0; i < N; i++) {
        sum += data[i];
    }
    return sum;
}

运行时间：

num_elements sort time sum time
100 0.000012 0.000001
1000 0.000166 0.000005
10000 0.002162 0.000045
100000 0.022915 0.000384
1000000 0.216075 0.003397
10000000 2.404543 0.034109
100000000 27.204318 0.340051

ignore the input time.

并行过程：

归并排序算法的并行化：

首先，归并排序的步骤分为已下三步：

分解：将n个元素分成各含n/2个元素的子序列；
解决：用合并排序法对两个子序列递归地排序；
合并：合并两个已经排序的子序列，已得到排序结果。

然后发现，按照这个思路很难并行化，因为许多过程有依赖的，比如当[1, 1], [2, 2] 区间没有合并之前，那么[1, 2], [3, 4]区间是不能进行合并的。

但是我们可以把归并的步骤反过来。原来归并是要不断的分解一个序列，直到分解成长度为1的区间，最后依次合并。我们现在假设有N个区间，要分别合并，最后合并成一个区间。那么我现在的操作是没有前后依赖的，对于任意两个区间，只需要合并就好，不用考虑其他的线程。

这样排序的过程就类似一颗线段树（严格的来讲并不是），自底向上的不断合并。

这里写图片描述

排序代码：

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
//合并两个区间
void merge(int l1, int r1, int r2, int* data, int* temp) {
    int top = l1, p = l1, q = r1;
    while (p < r1 || q < r2) {
        if (q >= r2 || (p < r1 && data[p] <= data[q])) {
            temp[top++] = data[p++];
        }
        else {
            temp[top++] = data[q++];
        }
    }
    for (top = l1; top < r2; top++) {
        data[top] = temp[top];
    }
}

void merge_sort(int l, int r, int* data, int N) {
    int i, j, t, *temp;
    temp = (int*)malloc(N * sizeof(int));
    //这里做了一些优化，预处理合并了单个的区间，略微提高的速度
	#pragma omp parallel for private(i, t) shared(N, data)
    for (i = 0; i < N/2; i++)
        if (data[i*2] > data[i*2+1]) {
            t = data[i*2];
            data[i*2] = data[i*2+1];
            data[i*2+1] = t;
        }

	//i代表每次归并的区间长度，j代表需要归并的两个区间中最小的下标
    for (i = 2; i < r; i *= 2) {
		#pragma omp parallel for private(j) shared(r, i)
        for (j = 0; j < r-i; j += i*2) {
            merge(j, j+i, (j+i*2 < r ? j+i*2 : r), data, temp);
        }
    }
}

求和代码：

1
2
3
4
5
6
7
8
int get_sum(int* data, int N) {
    int sum = 0, i;
    #pragma omp parallel for private(i) reduct(+:sum)
    for (i = 0; i < N; i++) {
        sum += data[i];
    }
    return sum;
}

运行时间：

num_elements sort time sum time
100 0.000164 0.000009
1000 0.000209 0.000009
10000 0.002318 0.000052
100000 0.010589 0.000166
1000000 0.110090 0.001279
10000000 1.093572 0.013541
100000000 11.872408 0.127646

ignore the input time.

运行时间分析：

排序时间对比：

这里写图片描述

求和时间对比：

这里写图片描述

结论：

增加线程数在是可以加快程序的运行速度的，但是随着线程的增加，加速的效果逐渐变得不明显，双线程与单线程的差异较大，整体上多线程的用时为单线程的一半。

ACM►搜索►BFS

HDU3085 - Nightmare Ⅱ（双向BFS）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3085

题目大意：

在一个N*M的网格里，有两个人 G 和 M，并且有两只鬼。
G每秒可以走一步，G每秒可以走三步，每只鬼可以分裂，分裂到周围的的两格。假设#为鬼分裂后为1，如下图所示。每只分裂后的新鬼可以继续分裂。

0 0 1 0 0
0 1 1 1 0
1 1 # 1 1
0 1 1 1 0
0 0 1 0 0

解题过程：

没做个两个人走的步数不同的bfs，这几天又比较咸鱼，于是去搜了题解。

http://acm.zzkun.com/archives/823

dalao的博客。

题目分析：

先预处理距离，这里可以了解下哈密顿距离。

然后用两个队列进行bfs，bfs操作可以写成一个函数，队列为传进来的参数，每次bfs的时候只bfs一层。层数在外面计数，传进来当参数。

inline 关键字，可以替换宏定义的函数，和宏定义的函数等价。

Node v(1, 2) 可以直接这样创建变量并初始化。

AC代码：

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 <bits/stdc++.h>
using namespace std;

struct Node {
    int x, y;
    //构造方法可以带默认值
    Node(int x = 0, int y = 0):x(x),y(y){}
};

const int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};
const int MAX = 800+5;

int N, M, dist[MAX][MAX];
char data[MAX][MAX];
queue<Node> q[2];
bool vis[MAX][MAX][2];
Node mm, gg, z1, z2;

void init() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            //求两个幽灵到每个点的哈密顿距离，取最短的那个
            int t1 = (abs(i - z1.x) + abs(j - z1.y) + 1) / 2;
            int t2 = (abs(i - z2.x) + abs(j - z2.y) + 1) / 2;
            dist[i][j] = min(t1, t2);
        }
    }
}


//用作判断是否在边界内，这里用内联函数非常合适
inline bool in(int x, int y) {
    return x >= 1 && x <= N && y >= 1 && y <= M && data[x][y] != 'X';
}


//全局的队列，bfs函数只是用来操作一层
bool bfs(int x, int step) {
    int sz = q[x].size();
    while (sz--) {
        Node u = q[x].front(); q[x].pop();
        if (step >= dist[u.x][u.y])
            continue;
        for (int i = 0; i < 4; i++) {
            //可以直接这样调用构造方法
            Node v(u.x + dir[i][0], u.y + dir[i][1]);
            if (in(v.x, v.y) && !vis[v.x][v.y][x] && step < dist[v.x][v.y]) {
                if (vis[v.x][v.y][!x])
                    return true;
                vis[v.x][v.y][x] = true;
                q[x].push(v);
            }
        }
    }
    return false;
}

int solve() {
    while (!q[0].empty()) q[0].pop();
    while (!q[1].empty()) q[1].pop();
    q[0].push(mm), q[1].push(gg);
    memset(vis, 0, sizeof(vis));
    vis[mm.x][mm.y][0] = vis[gg.x][gg.y][1] = true;
    int step = 0;
    while (!q[0].empty() && !q[1].empty()) {
        ++step;
        //对gg bfs三层，mm bfs一层，如果相遇就返回当前的时间
        if (bfs(0, step) || bfs(0, step) || bfs(0, step) || bfs(1, step))
            return step;
    }
    return -1;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &N, &M);
        mm = gg = z1 = z2 = Node(0, 0);
        for (int i = 1; i <= N; i++) {
            scanf("%s", data[i]+1);
            for (int j = 1; j <= M; j++) {
                if (data[i][j] == 'G')
                    gg = Node(i, j);
                if (data[i][j] == 'M')
                    mm = Node(i, j);
                if (data[i][j] == 'Z') {
                    if (!z1.x)
                        z1 = Node(i, j);
                    else
                        z2 = Node(i, j);
                }
            }
        }
        init();
        printf("%d\n", solve());
    }
}