ACM►字符串►字符串Hash

CodeForce727E - Games on a CD（字符串双hash模板）

题目链接：

http://codeforces.com/problemset/problem/727/E

题目大意：

给出一个长度为 $N \times k$ 的字符串，可以将其看成一个环首尾相接。问这个字符串是否可以由下面给出的 g 个字符串组成，保证字符串不同并且长度均为 k，每个字符串只能用一次。

$1\le N, k \le 10^5$ $n \cdot k, g \cdot k \le 2 \times 10^6$

题目分析：

这题只要会字符串 Hash 就会做了，首先把原串复制一遍放到结尾。因为每个串的长度都为 k 所以从 0 到 k 枚举起点，然后不断的跳到后面 k 个位置，判断 g 个字符串是否匹配上这一段子串并且没有被使用，如果找到一组解就输出答案。

复杂度$O(N\log n)$这里把 Hash 后的 pair 映射成整数，多了一个 log。

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX = 200000 + 100;

//--------------------双哈希---------------------------------------
const int MOD[] = {1000000007, 1000000009};
const int P = 10000017;

vector<ll> hashValue[2][MAX];
string str[MAX];
ll powNum[2][MAX];

//对一个字符串进行 hash 并保留前缀和
inline void init(int n) {
    for (int k = 0; k < 2; k++) {
        hashValue[k][n].clear();
        hashValue[k][n].push_back(0);
        for (int i = 1; i <= str[n].size(); i++) {
            hashValue[k][n].push_back((hashValue[k][n][i - 1] * P + str[n][i - 1]) % MOD[k]);
        }
    }
}

//获得某个字符串的任一子串的 hash 值
inline pair<int, int> getHash(int n, int l = 0, int r = -1) {
    if (r == -1) r = str[n].size() - 1;
    l++, r++;
    vector<int> ans;
    for (int k = 0; k < 2; k++) {
        ans.push_back((int) (((hashValue[k][n][r] - hashValue[k][n][l - 1] * powNum[k][r - l + 1]) % MOD[k] + MOD[k]) %
                             MOD[k]));
    }
    return make_pair(ans[0], ans[1]);
}

//初始化幂，计算过程中使用
void init_pow() {
    for (int k = 0; k < 2; k++) {
        powNum[k][0] = 1;
        for (int i = 1; i < MAX; i++) {
            powNum[k][i] = powNum[k][i - 1] * P % MOD[k];
        }
    }
}

//将 hash 得到的 pair 映射成整数
vector<int> store;
map<pair<int, int>, int> hashName;

inline int getID(pair<int, int> n, int index = 0) {
    if (hashName.count(n)) return hashName[n];
    store.push_back(index);
    return hashName[n] = store.size() - 1;
}
//--------------------双哈希------------------------------------------------

bool ok[MAX];

int main() {
    init_pow();

    ios::sync_with_stdio(false);

    int n, k, g;
    cin >> n >> k;
    cin >> str[0];
    str[0] = str[0] + str[0];
    init(0);

    cin >> g;
    for (int i = 1; i <= g; i++) {
        cin >> str[i];
        init(i);
        getID(getHash(i), i);
    }

    //枚举起点
    for (int st = 0; st < k; st++) {
        vector<int> ans;
        bool flag = true;
        //计算从起点到终点中，是否可以有 g 个字符串组成
        for (int i = st; i < st + str[0].size() / 2; i += k) {
            pair<int, int> v = getHash(0, i + 1, i + k);
            if (!hashName.count(v)) {
                flag = false;
                break;
            }
            int idx = getID(v);
            if (ok[idx]) {
                flag = false;
                break;
            }
            ans.push_back(idx);
            ok[idx] = true;
        }
        if (flag) {
            printf("YES\n");
            for (int i = 0; i < ans.size(); i++) {
                printf("%d ", store[ans[i]]);
            }
            return 0;
        }
        for (int i = 0; i < ans.size(); i++) {
            ok[ans[i]] = false;
        }
    }

    printf("NO\n");
}

解题过程：

Hash 过程的代码完全参照卿学姐的视频写的，非常感谢！

PPT链接

ACM►数学►线性基

线性基小结

感谢

Sengxian’s Blog

前言

感觉 Sengxian 的博客里面写的太好了，然后这里只打算添加一下自己的理解了。

首先所谓的线性基，就是把若干个整数，看成 n 维 01 向量（通常 n 不会超过 64，即 long long 的范围），然后求这些向量的一个极大无关组。需要注意的一点是，对于这里的 01 向量，只有异或运算。

不过一般为了方便处理，我们会把极大无关组进行列变换化最简形。一个向量空间可以有多个基，但是化为最简形后基是唯一的。化为最简形后和原来是等价的，由化最简形后的向量组可以表示的向量都可以由原向量组来表示。

下面是利用高斯消元求解线性基的代码，由 Sengxian 的代码改过来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void cal(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = MAX_BASE; j >= 0; j--) {
            if (data[i] >> j & 1) {
                if (b[j]) data[i] ^= b[j];
                else {
                    b[j] = data[i];
                    for (int k = j - 1; k >= 0; k--) if (b[k] && b[j] >> k & 1) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; k++) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
            }
        }
    }
}

SGU-275

给出 N 个数，求 N 个数异或可以得到的最大值，数的范围在 long long 内。

求出线性基，然后异或就是答案，这里 Sengxian 博客有证明，不过这里补充一点，对于上面算法得到的线性基是唯一的。

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

typedef long long ll;

const int MAX_BASE = 63;

ll b[200];
ll a[11234];

void cal(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = MAX_BASE; j >= 0; j--) {
            if (a[i] >> j & 1) {
                if (b[j]) a[i] ^= b[j];
                else {
                    b[j] = a[i];
                    for (int k = j - 1; k >= 0; k--) if (b[k] && b[j] >> k & 1) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; k++) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
            }
        }
    }
}

int main() {
    int n;
    while (~scanf("%d", &n)) {

        memset(b, 0, sizeof(b));
        for (int i = 0; i < n; i++) {
            scanf("%lld", a + i);
        }
        cal(n);
        ll ans = 0;
        for (int i = 0; i <= MAX_BASE; i++) {
            if (b[i] >> i & 1) ans ^= b[i];
        }
        printf("%lld\n", ans);
    }

}

CF-895C

给出 N 个数的集合，问能取出多少不同的子集，使得乘积是平方数。输入的数字小于 70 。

对平方数进行质因数分解，会发现每个质因子的幂都是偶数。现在对输入的 N 个数进行质因数分解，对每个质因子只对它的幂的奇偶性有关，可以计算小于 70 的质因子只有 20 个，那么我们用一个 01 变量来表示每个数质因子奇偶性的情况。

然后我们对这 N 个 01 向量求线性基，那么答案就是 $2^{N - BaseSize} - 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
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 112345;
const int MOD = 1e9 + 7;
const int MAX_BASE = 20;

bool now_prime[200];

vector<int> primes;

void get_primes() {
    for (int i = 2; i <= 70; i++) {
        if (now_prime[i]) continue;
        primes.push_back(i);
        for (int j = i * 2; j <= 70; j += i) {
            now_prime[j] = true;
        }
    }
}

int raw_data[MAX];
int data[MAX];

int solve(int n) {
    int rst = 0;
    for (int i = 0; i < primes.size(); i++) {
        while (n % primes[i] == 0) {
            rst ^= (1 << i);
            n /= primes[i];
        }
    }
    return rst;
}

int b[200];

void cal(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = MAX_BASE; j >= 0; j--) {
            if (data[i] >> j & 1) {
                if (b[j]) data[i] ^= b[j];
                else {
                    b[j] = data[i];
                    for (int k = j - 1; k >= 0; k--) if (b[k] && b[j] >> k & 1) b[j] ^= b[k];
                    for (int k = j + 1; k <= MAX_BASE; k++) if (b[k] >> j & 1) b[k] ^= b[j];
                    break;
                }
            }
        };
    };
}

int pow_mod(ll a, int k) {
    ll rst = 1;
    while (k) {
        if (k & 1) rst = rst * a % MOD;
        a = a * a % MOD;
        k >>= 1;
    }
    return (int)rst;
}

int main() {
    get_primes();
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", raw_data + i);
        data[i] = solve(raw_data[i]);
    }
    cal(n);
    int cnt = 0;
    for (int i = 0; i <= MAX_BASE; i++) {
        if (b[i]) cnt++;
    }
    printf("%d\n", (pow_mod(2, n - cnt) - 1 + MOD) % MOD);
}
ACM►数据结构►K-D树

K-D树小结

资料&感谢

Sengxian’s Blog

QSC算法讲堂

介绍

K-D 树是 K 维树（k-dimensional tree）的缩写，可以用来寻找 K 维空间中距离一个点最近的若干个点，不过在 ACM 中一般用来处理平面的最近点对问题。

K-D 树实质上是一颗二叉树，所以可以做到插入删除点都是 $O(\log n)$，在建树的时候每次按一个维度排序后，取中间点把空间划分为两部分，在这个维度上小于中间点的放到左儿子，大于中间点的放到右儿子。

这里为了简单，首先从一维的 K-D 树入手。

一维的 K-D 树

一维 K-D 树

上图是一颗一维的 K-D，对于一维的情况，所有的点都是数轴上的点，那么这时候
K-D 树就是一颗普通的二叉搜索树（Binary Search Tree）。

二维的 K-D 树

二维 K-D 树

这时候就是交替的按 x 维和 y 维排序进行划分的。上面就是对点集 (2,3), (5,4), (9,6), (4,7), (8,1), (7,2)的划分。

上面的划分对应的树型结构就是这样的，对于第一层，左子树的点的 x 坐标都小于根节点，右子树的点的 x 坐标都大于根节点。对于第二层，左子树的点的 y 坐标都小于根节点，右子树的点的 y 坐标都大于根节点，以此类推。

构建

K-D 树的每个节点不仅要保存当前点的坐标信息，还要维护当前子树每个维度上的边界点。

这里 Sengxian 巨巨写的非常好，就直接引用了。

在构造 1 维 BST 树时，一个 1 维数据根据其与树的根结点进行大小比较，来决定是划分到左子树还是右子树。
同理，我们也可以按照这样的方式，将一个 $k$ 维数据与 k-d树 的根结点进行比较，只不过不是对 $k$ 维数据进行整体的比较，而是选择某一个维度 $D_i$，然后比较两个数据在该维度 $D_i$ 上的大小关系，即每次选择一个维度 $D_i$ 来对 $k$ 维数据进行划分，相当于用一个垂直于该维度 $D_i$ 的超平面将 $k$ 维数据空间一分为二，平面一边的所有 $k$ 维数据在 $D_i$ 维度上的值小于平面另一边的所有 $k$ 维数据对应维度上的值。
也就是说，我们每选择一个维度进行如上的划分，就会将 $k$ 维数据空间划分为两个部分，如果我们继续分别对这两个子 $k$ 维空间进行如上的划分，又会得到新的子空间，对新的子空间又继续划分，重复以上过程直到每个子空间都不能再划分为止。以上就是构造 k-d树 的过程。
那么如果是二维特殊情况，就变得非常好理解了，通俗的来说就是通过过已有点的横线，竖线来划分二维平面。
上述过程中涉及到两个重要的问题：

  1. 每次对子空间的划分时，怎样确定在哪个维度上进行划分？
  2. 在某个维度上进行划分时，怎样确保在这一维度上的划分得到的两个子集合的数量尽量相等，即左子树和右子树中的结点个数尽量相等？

对于第一个问题，有很多种方法可以选择划分维度（axis-aligned splitting planes），所以有很多种创建 k-d树 的方法。 最典型的方法如下：
随着树的深度轮流选择维度来划分。例如，在二维空间中根节点以 x 轴划分，其子节点皆以 y 轴划分，其孙节点又以 x 轴划分，其曾孙节点则皆为 y 轴划分，依此类推。
另外的划分方法还有最大方差法（max invarince），在这里不做介绍。

而对于第二个问题，也是在 BST 中会遇到的一个问题。在 BST 中，我们是将数据的中位数作为根节点，然后再左右递归下去建树，这样可以得到一棵平衡的二叉搜索树。
同样，在 k-d树 中，若在维度 $D_i$ 上进行划分时，根节点就应该选择该维度 $D_i$ 上所有数据的中位数，这样递归子树的大小就基本相同了。

K-D 树单个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct Node {
    int l, r;
    int id;
    //d 数组储存当前点，minn 和 maxn 表示当前节点维护的矩形的边界
    int d[DIM], minn[DIM], maxn[DIM];

    //对节点进行初始化
    inline void maintain() {
        for (int i = 0; i < DIM; i++) {
            minn[i] = maxn[i] = d[i];
        }
        l = r = 0;
    }
} tree[MAX];

//通过修改全局变量 D，实现按不同维度排序
bool operator<(const Node &a, const Node &b) {
    return a.d[D] < b.d[D];
}

建树

1
2
3
4
5
6
7
8
9
10
11
12
int build(int l, int r, int now) {
    int mid = (l + r) >> 1;
    D = now;
    //将中间数放到 mid 位置，小于中间数的放左边，大于的放右边，不保证左右边有序，类似快排的一部分，复杂度O(N)
    nth_element(tree + l, tree + mid, tree + r + 1);
    //初始化节点信息
    tree[mid].maintain();
    if (l < mid) tree[mid].l = build(l, mid - 1, (now + 1) % DIM);
    if (mid < r) tree[mid].r = build(mid + 1, r, (now + 1) % DIM);
    //维护子树信息
    pushUp(mid);
    re

插入

1
2
3
4
5
6
7
8
9
10
11
12
void insert(int &o, int k, int now) {
    //如果当前节点为空，就直接将赋值
    if (o == 0) {
        o = k;
        return;
    }
    //否则根据 now 维的大小进行二分查找
    if (tree[k].d[now] < tree[o].d[now]) insert(tree[o].l, k, (now + 1) % DIM);
    else insert(tree[o].r, k, (now + 1) % DIM);
    //插入节点后更新信息
    pushUp(o);
}

查找

最近点

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

//当前查找的点距离节点维护的矩阵的最近距离
int partionMin(int o, int k) {
    int rst = 0;
    for (int i = 0; i < DIM; i++) {
        if (tree[k].d[i] > tree[o].maxn[i]) rst += tree[k].d[i] - tree[o].maxn[i];
        if (tree[k].d[i] < tree[o].minn[i]) rst += tree[o].minn[i] - tree[k].d[i];
    }
    return rst;
}

void query(int o, int k) {
    //通过当前节点储存的点更新答案
    int dm = abs(tree[o].d[0] - tree[k].d[0]) + abs(tree[o].d[1] - tree[k].d[1]);
    if (dm < ans) ans = dm;
    //计算左右子树距离当前点可能的最近的答案
    int dl = tree[o].l ? partionMin(tree[o].l, k) : INF;
    int dr = tree[o].r ? partionMin(tree[o].r, k) : INF;

    //通过搜索顺序进行剪枝
    if (dl < dr) {
        //如果最近可能的点都大于答案，那么不可能更新答案
        if (dl < ans) query(tree[o].l, k);
        if (dr < ans) query(tree[o].r, k);
    } else {
        if (dr < ans) query(tree[o].r, k);
        if (dl < ans) query(tree[o].l, k);
    }
}

初始化答案为无穷，从根节点开始，首先通过节点储存的点去更新答案。然后计算左右子树维护的矩形区域离当前查询的点的最近可能距离，然后首先搜距离近的，再搜远的，实际上就是一个剪枝。复杂度一般是$O(\log n)$，最差可能是$O(n \sqrt{n})$。

上面是曼哈顿距离，对于欧式几何距离用下面计算，也就是一个点到矩形的最近距离

1
2
3
4
5
6
7
8
9
inline ll partionMin(int o, int k) {
    if (tree[o].minn[2] > tree[k].d[2]) return INF;
    ll rst = 0;
    for (int i = 0; i < 2; i++) {
        if (tree[k].d[i] > tree[o].maxn[i]) rst += sqr(tree[k].d[i] - tree[o].maxn[i]);
        if (tree[k].d[i] < tree[o].minn[i]) rst += sqr(tree[o].minn[i] - tree[k].d[i]);
    }
    return rst;
}

扩展成求到某个点最近的 k 个点也比较容易，查询的时候维护一个最大堆就可以了，之前的剪枝，就是对对顶进行比较了，如果大于堆顶一定不可能更新答案。

题集

BZOJ 2648

裸的 K-D 树题，求到某个点的最近曼哈顿距离。

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
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int MAX = 500010;
const int DIM = 2;
const int INF = 0x3f3f3f3f;
 
struct Node {
    int l, r;
    int d[DIM], minn[DIM], maxn[DIM];
 
    inline void maintain() {
        for (int i = 0; i < DIM; i++) {
            minn[i] = maxn[i] = d[i];
        }
        l = r = 0;
    }
} tree[MAX * 2];
 
int D;
 
bool operator<(const Node &a, const Node &b) {
    return a.d[D] < b.d[D];
}
 
int root = 0, pos = 1;
 
inline void pushUp(int p) {
    int son[2] = {tree[p].l, tree[p].r};
    for (int i = 0; i < 2; i++) {
        if (!son[i]) continue;
        for (int j = 0; j < DIM; j++) {
            tree[p].maxn[j] = max(tree[son[i]].maxn[j], tree[p].maxn[j]);
            tree[p].minn[j] = min(tree[son[i]].minn[j], tree[p].minn[j]);
        }
    }
}
 
int build(int l, int r, int now) {
    int mid = (l + r) >> 1;
    D = now;
    nth_element(tree + l, tree + mid, tree + r + 1);
    tree[mid].maintain();
    if (l < mid) tree[mid].l = build(l, mid - 1, (now + 1) % DIM);
    if (mid < r) tree[mid].r = build(mid + 1, r, (now + 1) % DIM);
    pushUp(mid);
    return mid;
}
 
int ans;
 
int partionMin(int o, int k) {
    int rst = 0;
    for (int i = 0; i < DIM; i++) {
        if (tree[k].d[i] > tree[o].maxn[i]) rst += tree[k].d[i] - tree[o].maxn[i];
        if (tree[k].d[i] < tree[o].minn[i]) rst += tree[o].minn[i] - tree[k].d[i];
    }
    return rst;
}
 
void query(int o, int k) {
    int dm = abs(tree[o].d[0] - tree[k].d[0]) + abs(tree[o].d[1] - tree[k].d[1]);
    if (dm < ans) ans = dm;
    int dl = tree[o].l ? partionMin(tree[o].l, k) : INF;
    int dr = tree[o].r ? partionMin(tree[o].r, k) : INF;
    if (dl < dr) {
        if (dl < ans) query(tree[o].l, k);
        if (dr < ans) query(tree[o].r, k);
    } else {
        if (dr < ans) query(tree[o].r, k);
        if (dl < ans) query(tree[o].l, k);
    }
}
 
void insert(int &o, int k, int now) {
    if (o == 0) {
        o = k;
        return;
    }
    if (tree[k].d[now] < tree[o].d[now]) insert(tree[o].l, k, (now + 1) % DIM);
    else insert(tree[o].r, k, (now + 1) % DIM);
    pushUp(o);
}
 
int read() {
    int t;
    scanf("%d", &t);
    return t;
}
 
int main() {
    int n, m;
    n = read();
    m = read();
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < DIM; j++) tree[i].d[j] = read();
    }
 
    root = build(1, n, 0);
 
    pos = n + 1;
    int op;
    while (m--) {
        op = read();
        for (int j = 0; j < DIM; j++) tree[pos].d[j] = read();
        if (op == 1) {
            tree[pos].maintain();
            insert(root, pos, 0);
            pos++;
        } else {
            ans = INF;
            query(root, pos);
            printf("%d\n", ans);
        }
    }
    return 0;
}

BZOJ 1941

求每个点的最近点和最远的的距离差值最小的，用 K-D 树求每个点的最远点和最近点。

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
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int MAX = 500010;
const int DIM = 2;
const int INF = 0x3f3f3f3f;
 
struct Node {
    int l, r;
    int d[DIM], minn[DIM], maxn[DIM];
 
    inline void maintain() {
        for (int i = 0; i < DIM; i++) {
            minn[i] = maxn[i] = d[i];
        }
        l = r = 0;
    }
} tree[MAX * 2];
 
int D;
 
bool operator<(const Node &a, const Node &b) {
    return a.d[D] < b.d[D];
}
 
int root = 0, pos = 1;
 
inline void pushUp(int p) {
    int son[2] = {tree[p].l, tree[p].r};
    for (int i = 0; i < 2; i++) {
        if (!son[i]) continue;
        for (int j = 0; j < DIM; j++) {
            tree[p].maxn[j] = max(tree[son[i]].maxn[j], tree[p].maxn[j]);
            tree[p].minn[j] = min(tree[son[i]].minn[j], tree[p].minn[j]);
        }
    }
}
 
int build(int l, int r, int now) {
    int mid = (l + r) >> 1;
    D = now;
    nth_element(tree + l, tree + mid, tree + r + 1);
    tree[mid].maintain();
    if (l < mid) tree[mid].l = build(l, mid - 1, (now + 1) % DIM);
    if (mid < r) tree[mid].r = build(mid + 1, r, (now + 1) % DIM);
    pushUp(mid);
    return mid;
}
 
int ansMin, ansMax;
 
int partionMin(int o, int k) {
    int rst = 0;
    for (int i = 0; i < DIM; i++) {
        if (tree[k].d[i] > tree[o].maxn[i]) rst += tree[k].d[i] - tree[o].maxn[i];
        if (tree[k].d[i] < tree[o].minn[i]) rst += tree[o].minn[i] - tree[k].d[i];
    }
    return rst;
}
 
int partionMax(int o, int k) {
    int rst = 0;
    for (int i = 0; i < DIM; i++) {
        rst += max(abs(tree[k].d[i] - tree[o].minn[i]), abs(tree[k].d[i] - tree[o].maxn[i]));
    }
    return rst;
}
 
void queryMin(int o, int k) {
    int dm = abs(tree[o].d[0] - tree[k].d[0]) + abs(tree[o].d[1] - tree[k].d[1]);
    if (o == k) dm = INF;
    if (dm < ansMin) ansMin = dm;
    int dl = tree[o].l ? partionMin(tree[o].l, k) : INF;
    int dr = tree[o].r ? partionMin(tree[o].r, k) : INF;
    if (dl < dr) {
        if (dl < ansMin) queryMin(tree[o].l, k);
        if (dr < ansMin) queryMin(tree[o].r, k);
    } else {
        if (dr < ansMin) queryMin(tree[o].r, k);
        if (dl < ansMin) queryMin(tree[o].l, k);
    }
}
 
void queryMax(int o, int k) {
    int dm = abs(tree[o].d[0] - tree[k].d[0]) + abs(tree[o].d[1] - tree[k].d[1]);
    if (dm > ansMax) ansMax = dm;
    int dl = tree[o].l ? partionMax(tree[o].l, k) : 0;
    int dr = tree[o].r ? partionMax(tree[o].r, k) : 0;
    if (dl > dr) {
        if (dl > ansMax) queryMax(tree[o].l, k);
        if (dr > ansMax) queryMax(tree[o].r, k);
    } else {
        if (dr > ansMax) queryMax(tree[o].r, k);
        if (dl > ansMax) queryMax(tree[o].l, k);
    }
}
 
int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &tree[i].d[0], &tree[i].d[1]);
        }
 
        root = build(1, n, 0);
 
        int ans = INF;
 
        for (int i = 1; i <= n; i++) {
            ansMax = 0;
            ansMin = INF;
            queryMax(root, i);
            queryMin(root, i);
            ans = min(ans, ansMax - ansMin);
        }
        printf("%d\n", ans);
    }
    return 0;
}

BZOJ 4066

给出一个$n \times n$的棋盘，每次对其中的一个点修改中，询问一个矩形，求矩形内点的和。

这里插入的点的数量有点多，可能导致树的形态太差，所以插入点树每过 10000 就暴力重构一下。

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
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int MAX = 200010;
const int DIM = 2;
const int INF = 0x3f3f3f3f;
 
struct Node {
    int l, r;
    int d[DIM], minn[DIM], maxn[DIM];
    int sum, v;
 
    inline void maintain() {
        for (int i = 0; i < DIM; i++) {
            minn[i] = maxn[i] = d[i];
        }
        sum = v;
        l = r = 0;
    }
} tree[MAX * 2];
 
int D;
 
bool operator<(const Node &a, const Node &b) {
    return a.d[D] < b.d[D];
}
 
int root = 0, pos = 1;
 
inline void pushUp(int p) {
    int son[2] = {tree[p].l, tree[p].r};
    for (int i = 0; i < 2; i++) {
        if (!son[i]) continue;
        for (int j = 0; j < DIM; j++) {
            tree[p].maxn[j] = max(tree[son[i]].maxn[j], tree[p].maxn[j]);
            tree[p].minn[j] = min(tree[son[i]].minn[j], tree[p].minn[j]);
        }
    }
    tree[p].sum = tree[son[0]].sum + tree[p].v + tree[son[1]].sum;
}
 
int build(int l, int r, int now) {
    int mid = (l + r) >> 1;
    D = now;
    nth_element(tree + l, tree + mid, tree + r + 1);
    tree[mid].maintain();
    if (l < mid) tree[mid].l = build(l, mid - 1, (now + 1) % DIM);
    if (mid < r) tree[mid].r = build(mid + 1, r, (now + 1) % DIM);
    pushUp(mid);
    return mid;
}
 
int ans;
int xl, xr, yl, yr;
 
void query(int o) {
    if (xr < tree[o].minn[0] || tree[o].maxn[0] < xl  ||
        yr < tree[o].minn[1] || tree[o].maxn[1] < yl)
        return;
 
    if (xl <= tree[o].minn[0] && tree[o].maxn[0] <= xr &&
        yl <= tree[o].minn[1] && tree[o].maxn[1] <= yr) {
        ans += tree[o].sum;
        return;
    }
 
    if (xl <= tree[o].d[0] && tree[o].d[0] <= xr &&
        yl <= tree[o].d[1] && tree[o].d[1] <= yr)
        ans += tree[o].v;
 
    if (tree[o].l) query(tree[o].l);
    if (tree[o].r) query(tree[o].r);
}
 
void insert(int &o, int k, int now) {
    if (o == 0) {
        o = k;
        return;
    }
    if (tree[k].d[now] < tree[o].d[now]) insert(tree[o].l, k, (now + 1) % DIM);
    else insert(tree[o].r, k, (now + 1) % DIM);
    pushUp(o);
}
 
int read(bool type = true) {
    int t;
    scanf("%d", &t);
    if (type) t ^= ans;
    return t;
}
 
int main() {
    int n;
    scanf("%d", &n);
    int op;
    while (true) {
        op = read(0);
        if (op == 3) break;
        if (op == 1) {
            for (int j = 0; j < DIM; j++) tree[pos].d[j] = read();
            tree[pos].v = read();
            tree[pos].maintain();
            insert(root, pos, 0);
            pos++;
            if (pos % 10000 == 0) root = build(1, pos - 1, 0);
        } else {
            xl = read();
            yl = read();
            xr = read();
            yr = read();
 
            ans = 0;
            query(root);
            printf("%d\n", ans);
        }
    }
    return 0;
}

HDU 5992

三维 K-D 树，求二维平面是距离某个点最近的点，并且第三维不超过某个值。

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

using namespace std;

typedef long long ll;

const int MAX = 200010;
const int DIM = 3;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct Node {
    int l, r;
    int id;
    int d[DIM], minn[DIM], maxn[DIM];
} tree[MAX];

int D;

bool operator<(const Node &a, const Node &b) {
    return a.d[D] < b.d[D];
}

int root;

inline void pushUp(int p) {
    int son[2] = {tree[p].l, tree[p].r};
    for (int i = 0; i < 2; i++) {
        if (!son[i]) continue;
        for (int j = 0; j < DIM; j++) {
            tree[p].maxn[j] = max(tree[son[i]].maxn[j], tree[p].maxn[j]);
            tree[p].minn[j] = min(tree[son[i]].minn[j], tree[p].minn[j]);
        }
    }
}

int build(int l, int r, int now) {
    int mid = (l + r) >> 1;
    D = now;
    nth_element(tree + l, tree + mid, tree + r + 1);
    for (int i = 0; i < 3; i++) tree[mid].maxn[i] = tree[mid].minn[i] = tree[mid].d[i];
    if (l < mid) tree[mid].l = build(l, mid - 1, (now + 1) % DIM);
    if (mid < r) tree[mid].r = build(mid + 1, r, (now + 1) % DIM);
    pushUp(mid);
    return mid;
}

inline ll sqr(const ll &x) {
    return x * x;
}

inline ll dis(const Node &a, const Node &b) {
    return sqr((ll) a.d[0] - (ll) b.d[0]) + sqr((ll) a.d[1] - (ll) b.d[1]);
}

inline ll partionMin(int o, int k) {
    if (tree[o].minn[2] > tree[k].d[2]) return INF;
    ll rst = 0;
    for (int i = 0; i < 2; i++) {
        if (tree[k].d[i] > tree[o].maxn[i]) rst += sqr(tree[k].d[i] - tree[o].maxn[i]);
        if (tree[k].d[i] < tree[o].minn[i]) rst += sqr(tree[o].minn[i] - tree[k].d[i]);
    }
    return rst;
}

ll ans1;
int ans2, ansNode;

void query(int o, int k) {
    ll dm = dis(tree[o], tree[k]);
    if (tree[o].d[2] <= tree[k].d[2] && (dm < ans1 || dm == ans1 && tree[o].id < ans2)) {
        ans1 = dm;
        ans2 = tree[o].id;
        ansNode = o;
    }
    ll dl = tree[o].l ? partionMin(tree[o].l, k) : INF;
    ll dr = tree[o].r ? partionMin(tree[o].r, k) : INF;
    if (dl < dr) {
        if (dl <= ans1) query(tree[o].l, k);
        if (dr <= ans1) query(tree[o].r, k);
    } else {
        if (dr <= ans1) query(tree[o].r, k);
        if (dl <= ans1) query(tree[o].l, k);
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < DIM; j++) scanf("%d", &tree[i].d[j]);
            tree[i].l = tree[i].r = 0;
            tree[i].id = i;
        }
        root = build(1, n, 0);
        while (m--) {
            for (int j = 0; j < DIM; j++) scanf("%d", &tree[n + 1].d[j]);
            ans1 = INF;
            query(root, n + 1);
            printf("%d %d %d\n", tree[ansNode].d[0], tree[ansNode].d[1], tree[ansNode].d[2]);
        }
    }
}

HDU 4347

求 k 维的最近 m 个点。

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

using namespace std;

typedef long long ll;

const int MAX = 50000 + 100;
const int MAXDIM = 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int DIM;

struct Node {
    int l, r;
    int id;
    int d[MAXDIM], minn[MAXDIM], maxn[MAXDIM];
    inline void maintain() {
        for (int i = 0; i < DIM; i++) {
            minn[i] = maxn[i] = d[i];
        }
        l = r = 0;
    }
} tree[MAX];

int D;
priority_queue<pair<ll, int> > q;

bool operator<(const Node &a, const Node &b) {
    return a.d[D] < b.d[D];
}

int root;

inline void pushUp(int p) {
    int son[2] = {tree[p].l, tree[p].r};
    for (int i = 0; i < 2; i++) {
        if (!son[i]) continue;
        for (int j = 0; j < DIM; j++) {
            tree[p].maxn[j] = max(tree[son[i]].maxn[j], tree[p].maxn[j]);
            tree[p].minn[j] = min(tree[son[i]].minn[j], tree[p].minn[j]);
        }
    }
}

int build(int l, int r, int now) {
    int mid = (l + r) >> 1;
    D = now;
    nth_element(tree + l, tree + mid, tree + r + 1);
    tree[mid].maintain();
    if (l < mid) tree[mid].l = build(l, mid - 1, (now + 1) % DIM);
    if (mid < r) tree[mid].r = build(mid + 1, r, (now + 1) % DIM);
    pushUp(mid);
    return mid;
}

inline ll sqr(const ll &x) {
    return x * x;
}

inline ll dis(const Node &a, const Node &b) {
    ll rst = 0;
    for (int i = 0; i < DIM; i++) {
        rst += sqr((ll) a.d[i] - (ll) b.d[i]);
    }
    return  rst;
}

inline ll partionMin(int o, int k) {
    ll rst = 0;
    for (int i = 0; i < DIM; i++) {
        if (tree[k].d[i] > tree[o].maxn[i]) rst += sqr(tree[k].d[i] - tree[o].maxn[i]);
        if (tree[k].d[i] < tree[o].minn[i]) rst += sqr(tree[o].minn[i] - tree[k].d[i]);
    }
    return rst;
}

void query(int o, int k) {
    ll dm = dis(tree[o], tree[k]);

    if (dm < q.top().first) {
        q.pop();
        q.push(make_pair(dm, o));
    }

    ll dl = tree[o].l ? partionMin(tree[o].l, k) : INF;
    ll dr = tree[o].r ? partionMin(tree[o].r, k) : INF;
    if (dl < dr) {
        if (dl <= q.top().first) query(tree[o].l, k);
        if (dr <= q.top().first) query(tree[o].r, k);
    } else {
        if (dr <= q.top().first) query(tree[o].r, k);
        if (dl <= q.top().first) query(tree[o].l, k);
    }
}

int main() {
    int n;
    while (~scanf("%d %d", &n, &DIM)) {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < DIM; j++) {
                scanf("%d", &tree[i].d[j]);
            }
        }
        root = build(1, n, 0);
        int t, m;
        scanf("%d", &t);
        while (t--) {
            for (int i = 0; i < DIM; i++) {
                scanf("%d", &tree[n + 1].d[i]);
            }
            scanf("%d", &m);
            while (!q.empty()) q.pop();
            for (int i = 0; i < m; i++) q.push(make_pair(INF, -1));
            query(root, n + 1);
            vector<int> ans;
            while (!q.empty()) {
                ans.push_back(q.top().second);
                q.pop();
            }
            printf("the closest %d points are:\n", m);
            for (int i = ans.size() - 1; i >= 0; i--) {
                for (int j = 0; j < DIM; j++) {
                    printf("%d%c", tree[ans[i]].d[j], j == DIM - 1 ? '\n' : ' ');
                }
            }
        }
    }
}
ACM►命题

SDUTOJ4079 - Cirno のさんすう教室(模拟)

题目链接：

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2326/pid/4079

题目大意：

给出若干个类似 “A + B = C” 的等式（ABC均为一位的正整数），其中每个等式有可能至多有一个位置为 “?”，运算符只有”+ - *”。

题目需要输出每个复原后的等式，有可能等式本来就不需要复原，保证问号也为一位的正整数。

题目分析：

不难发现每个问号都有一个唯一的解，然后就是一道小学的算术题了。

分情况判断：

  • ? + B = C，那么 ? = C - B
  • A * ? = C，那么 ? = C / A
  • 以此类推….

这里可能好多同学读字符的时候出了问题，这里说一下，scanf函数里面添加一个空白字符，在读取的时候可以忽略掉若干个空白字符，比如我scanf(“ %c”, &ch)，就可以读取 “ 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
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        char a, b, c, d, e;
        scanf(" %c %c %c %c %c", &a, &b, &c, &d, &e);
        a -= '0', c -= '0', e -= '0';
        if (b == '+') {
            if (a == '?' - '0') {
                a = e - c;
            } else if (c == '?' - '0') {
                c = e - a;
            } else {
                e = a + c;
            }
        } else if (b == '-') {
            if (a == '?' - '0') {
                a = e + c;
            } else if (c == '?' - '0') {
                c = a - e;
            } else {
                e = a - c;
            }
        } else {
            if (a == '?' - '0') {
                a = e / c;
            } else if (c == '?' - '0') {
                c = e / a;
            } else {
                e = a * c;
            }
        }
        printf("%c %c %c %c %c\n", a + '0', b, c + '0', d, e + '0');
    }
}
ACM►命题

SDUTOJ4071 - 绿博的帽子（前缀和）

题目链接：

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/4071.html

题目大意：

<<<<<<< HEAD

给出 n 个数 $a_1, a_2, a_3 \dots a_n$，进行 q 次询问，每次输出 $\sum_{k = l}^r $$a_k$。

给出 n 个数 $a_1, a_2, a_3 \dots a_n$，进行 q 次询问，每次输出 $\sum_{k = l}^r a_k$。

ced470192faae13e215fb3b57e28efad2f01fa7f

$1 \le n, m, l, r \le 100000, l \le r \le n$

题目分析：

题意很简单，但是如果直接用 for 循环去求 l 到 r 的和的话会超时，可以计算一下，最多有 100000 次询问，每次最差计算 100000 次，这样总共时间复杂度是 $10^{10}$，计算机一秒大概只能计算$10^{9}$次，所以肯定会超时。

<<<<<<< HEAD

这时候我们定义$S_i = \sum_{k=1}^i ​$ $a_k​$，这样我们可以用一个 for 循环求出所有的 Si，这样对于每一个 l, r 的询问，我们用 $S_r​$ $- S_{l - 1}​$即是答案，这样总共的时间复杂度是 $10^5​$。

这时候我们定义$S_i = \sum_{k=1}^i a_k$，这样我们可以用一个 for 循环求出所有的 Si，这样对于每一个 l, r 的询问，我们用 $S_r - S_{l - 1}$即是答案，这样总共的时间复杂度是 $10^5$。

ced470192faae13e215fb3b57e28efad2f01fa7f

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
#include <stdio.h>

const int MAX = 112345;
int S[MAX];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", S + i);
        }
        for (int i = 1; i <= n; i++) {
            S[i] += S[i - 1];
        }
        int q;
        scanf("%d", &q);
        while (q--) {
            int l, r;
            scanf("%d %d", &l, &r);
            printf("%d\n", S[r] - S[l - 1]);
        }
    }
}
历程

ICPC青岛站总结

前言

老师要求每场比赛后要写一份总结…有点小学的时候强行每天写日记的感觉了。于是看看能不能写出点东西，就放在博客上了。

经历

总的来说体验一般吧，不论是坐车还是吃饭什么的，没有去哈尔滨或者杭州那么遥远的感觉，毕竟还没出省，（然后没有比赛的感觉？）。感觉两天时间一会就过去了，仿佛还没打比赛。然后到现在去青岛的经历都记不太清了…

比赛

热身赛的时候还是打算先练练手了，最后排名好像是在银牌区，算是认真打了下。最后在想 C 题，突然奇想用线段树的维护信息方式去写字典树，然后好像就可以做了，不过到比赛结束还没有调出来有点可惜，回来的后补掉了一个类似的题。

正式赛惯例还是我来敲签到题，这两场的发挥还算正常，做完签到题能够在银牌区，不过出打印图形的题的时候算是失误了一下，出的比较慢，当时好像在 90 名左右。之后就去看那个字符串题了，按照后缀数组的暴力做法让队友敲了一个半小时才调过了样例，然后我试了下造的大数据，发现 1000 的数据两就差不多 TLE 了，然后就交，这时候我一直在想简单的算法，感觉 A 的人那么多，不可能这么多队都会后缀数组，然后写了一个最差情况下可能 T 的算法，交上去就 A 了。这时候排名 50 左右，银牌是肯定稳了，毕竟一个小时不可能滚上去 50 多个队。最后一小时读了一个题，然后一点思路都没有，最后一个小时算是很绝望了…

感受

这场比赛感觉题出的是真的不好，前三题是一点难度都没有，只要手速快点，胆子大点就莫名其妙的前 100 名了，这样随随便便就拿到的名次感觉都对不起平时的训练。不过有银牌还是非常开心的，自我评价我们队的水平也就是介于铜牌和银牌之间。

ACM►DP

51nod1378 - 夹克老爷的愤怒（树型DP+贪心）

题目链接：

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1378

题目大意：

给出一张 N 个节点树形图，从中选若干个节点，使得途中任一节点距离最近的选中节点的距离不超过 K。

$1\le N\le 1e5, 0 \le K \le N$

题目分析：

树型DP，贪心的放，刚开始对于一颗子树，如果深度等于 K 那么肯定选中这颗子树的根节点。这时候这个选中的节点不仅对子孙节点有贡献，还对祖先或兄弟节点有贡献，这时候我们用一个数组 DP[i] 记录某个点可以做出多少贡献，或一个点需要多少的贡献。

比如选中了 u 节点，那么他具有 k 的贡献，他的父亲和孩子都有 k - 1的贡献。对于一个叶子节点视它为 0 点贡献，那么他的祖先就需要 -1 点贡献。

对于每个节点需要维护的是一颗子树的信息，要满足以它为根的子树里面的所有节点的需求。

通过以下方式进行转移：

minn = min(dp[child]), maxn = max(dp[child]);

如果当前节点为叶子节点，那么 minn = maxn = 0

1
2
3
4
5
6
if minn <= -k				#这时 u 的子树中已经有一个节点需求为 -k，如果不选中当前节点肯定无解
    dp[u] = k, ans++		
else if maxn + minn > 0		#这时 u 的子树中有一个节点的贡献可以满足其他节点的需求
    dp[u] = maxn - 1
else 						#如果不满足这两种情况，那么贪心的想，需求向祖先节点需求
	dp[u] = minn - 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
#include <bits/stdc++.h>

using namespace std;

const int MAX = 100000 + 100;
const int INF = 0x3f3f3f3f;

vector<int> edge[MAX];

int dp[MAX];

int ans = 0;
int n, k;

void dfs(int u, int fa) {
    int minn = INF;
    int maxn = -INF;
    bool ok = false;
    for (auto v : edge[u]) {
        if (v == fa) continue;
        dfs(v, u);
        ok = true;
        minn = min(dp[v], minn);
        maxn = max(dp[v], maxn);
    }

    if (!ok) maxn = minn = 0;
    if (minn <= -k) dp[u] = k, ans++;
    else if (maxn + minn > 0) dp[u] = maxn - 1;
    else dp[u] = minn - 1;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(0, -1);
    if (dp[0] < 0) ans++;
    printf("%d\n", ans);
}

解题过程：

在白书上看到了一个类似的题，然后扩展了一下，去群里问了下做法，感觉应该是很经典的题，然后人形题库 qls 就给出 51nod 上的原题，于是就补了一下。还是有一个坑点的，如果直接不考虑叶子节点的话，对于 k = 0 的情况需要特判。

ACM►数据结构►线段树

HDU4819 - Mosaic（二维线段树-单点更新区间查询 + 模板）

题目链接：

https://vjudge.net/problem/HDU-4819

题目大意：

给出一个 n n 的矩阵，每个位置有一个整数值。进行 q 次操作，每次选矩阵的一个元素为中心，取以这个元素为中心的 L L 的最大值和最小值，将这个元素的值赋值成最大值最小值的平均值。

$n \le 800, q \le 100000$

题目分析：

裸的二维线段树，单点修改，询问区间最值。

其实二维的线段树就是一个行线段树套列线段树，注意进行更新的时候，不能直接赋值修改，只修改行线段树叶子节点里面列线段树的叶子节点，然后向上合并。

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 1010;

#define lson o<<1
#define rson o<<1|1
#define MID int m = (l + r) >> 1


//列线段树，用来维护列的节点
struct Nodey {
    int Max, Min;

    Nodey operator+(const struct Nodey &t) {
        Nodey rst;
        rst.Max = max(Max, t.Max);
        rst.Min = min(Min, t.Min);
        return rst;
    }
};

int locy[MAX], locx[MAX];


//行线段树，用来维护行的节点
struct Nodex {
    Nodey sty[MAX << 2];

    void build(int o, int l, int r) {
        sty[o].Max = -INF;
        sty[o].Min = INF;
        if (l == r) {
            locy[l] = o;
            return;
        }
        MID;
        build(lson, l, m);
        build(rson, m + 1, r);
    }

    Nodey query(int o, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return (Nodey) {-INF, INF};
        if (ql <= l && r <= qr) return sty[o];
        MID;
        return query(lson, l, m, ql, qr) + query(rson, m + 1, r, ql, qr);
    }
} stx[MAX << 2];

int n;

void build(int o, int l, int r) {
    stx[o].build(1, 1, n);
    if (l == r) {
        locx[l] = o;
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m + 1, r);
}


//进行单点更新，这里首先更新了叶子节点，然后向上合并父亲节点；
void Modify(int x, int y, int val) {
    int tx = locx[x];
    int ty = locx[y];
    stx[tx].sty[ty].Min = stx[tx].sty[ty].Max = val;
    for (int i = tx; i; i >>= 1) {
        for (int j = ty; j; j >>= 1) {
            if (i == tx && j == ty) continue;
            if (j == ty) {
                //如果当前更新的列就是需要更新的叶子节点，那么由当前行的两个儿子节点来更新信息
                stx[i].sty[j] = stx[i << 1].sty[j] + stx[i << 1 | 1].sty[j];
            } else {
                //否则由当前列的如果儿子节点来更新
                stx[i].sty[j] = stx[i].sty[j << 1] +  stx[i].sty[j << 1 | 1];
            }
        }
    }
}

Nodey query(int o, int l, int r, int ql, int qr, int y1, int y2) {
    if (qr < l || r < ql) return (Nodey) {-INF, INF};
    if (ql <= l && r <= qr) return stx[o].query(1, 1, n, y1, y2);
    MID;
    return query(lson, l, m, ql, qr, y1, y2) + query(rson, m + 1, r, ql, qr, y1, y2);
}


int main() {
    int T;
    scanf("%d", &T);
    int Case = 0;
    while (T--) {
        Case++;
        printf("Case #%d:\n", Case);
        scanf("%d", &n);
        build(1, 1, n);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int a;
                scanf("%d", &a);
                Modify(i, j, a);
            }
        }
        int q;
        int x, y, L;
        scanf("%d", &q);
        while (q--) {
            scanf("%d %d %d", &x, &y, &L);
            int x1 = max(x - L / 2, 1);
            int x2 = min(x + L / 2, n);
            int y1 = max(y - L / 2, 1);
            int y2 = min(y + L / 2, n);
            Nodey ans = query(1, 1, n, x1, x2, y1, y2);
            int t = (ans.Max + ans.Min) / 2;
            printf("%d\n", t);
            Modify(x, y, t);
        }
    }
}

解题过程：

晚上模拟赛的题，感觉是一个二维线段树的裸题，但是不会，马上要去CCPC秦皇岛了，现学的。

历程

CCPC2017哈理工比赛总结

前言

算是第一次参加的区域赛，老师又让写一份总结，于是凑一块写在这里好了。

经历

出发前准备的算是挺充分，当时还一直纠结着哈尔滨冷不冷，要带多厚的衣服过去，最后就随便带了几件，然后出发当天去超市买了一堆的东西，给手机缓存了几部动漫（路人女主，末日时，来自深渊，笨女孩…）。得出经验，只需要提前半小时能够到达火车站就好了。

在火车上一晚上看完了笨女孩，然后白天的路上看完了末日时。期间还有打打王者荣耀和斗地主，感觉好颓啊，最逗的是一个别的队的傻子，和我们斗地主积分输成负的时候，就要清理下手机的数据，重新变成1000分。路上还算是挺好的，不过一天三顿吃泡面有点绝望，发现买的零食都不怎么好吃。另外值得一提的就是路上遇到了一个别人家的熊孩子，特别烦。

到了哈尔滨刚下车也不算太冷，在火车站刚下车就见识到了东北的民风彪悍，门卫大爷开玩笑都是 “你过来，看我不揍你！”。然后晚上就搭车去旅馆了，还算是顺利。（不过我们的房间厕所没有门是几个意思啊？！）

晚上一起去吃了夜宵（算是？），没好吃的然后回宿舍订了外卖，发现外卖能直接送到酒店的房间里，体验贼好！

第二天睡到了九点半（晚上终末少女的旅行更新了，然后看了一集），发现步行只需要半小时就到学校了，报名领取发票也挺顺利的，然后在门外的牌子前面合影就去吃饭了。伙食感觉还行，至少有不少肉，能吃饱…米饭给的是有点少。

下午就是一个关于游戏开发的演讲，然后不知不觉的睡着了…

回去的时候就没什么意思了，因为时间问题结果没去成中央大街，只买了点超市里散卖的红肠。

比赛

热身赛的时候前两题出的是比较顺的，我强行要攒人品，然后全场第一发的WA是我交的，然后测了测Java后，把所有题都WA了一发。然后就开始认真出题了，第一题就是个暴力，然后另一个是猜结论，我还强行打了一个表，最后没出B题有点可惜，赛后我还以为是要用线段树进行区间加，后来看大佬们的解释，发现改一下递推的方式就可以用前缀和优化掉了。

之后是正式赛，第一题，一个平时随手切的水题，比赛的时候居然卡了接近半小时，然后第二题也不算太难，卡了两个小时，最后吃午饭的时候讨论了下才A出来，可以说是相当绝望了，排名一直在100左右，觉得已经凉了，最后两个小时也没有出题。

不过最后的时候，居然能有铜牌，当时就很开心了，觉得打的这么差居然还有个牌子…

反思

可能是第一次参加区域赛，状态不是很好，比赛也缺乏一些讨论，好多题型没见过，比如热身赛的DP用前缀和优化，之前没见过…

还有好多题都是没用到复杂的数据结构算法，都是需要一些思维和技巧的题，感觉之后还是要加大点刷题量，多学一点套路和技巧，多打打CF。

ACM►图论►2-SAT

2-SAT问题（模板）

简介

2-SAT （2-satisfiability）是描述一个这样的问题，有 n 个 bool 变量 $x_i$，并且有 m 个需要满足的条件，比如： “$x_1$为真或$x_2$为假”，“ $x_1$ 为真或$x_2$为真”之类的条件，这里”或“是指两个条件中至少有一个为真。SAT的问题是确定这 n 个变量的值，使得满足所有的条件。

解法

以下主要参考Sengxian’s Blog和刘汝佳的白书。

有一个比较容易理解的解法，首先将每一个变量当成两个图中的顶点，比如 $x_i$ 拆成 $2i$ 和 $2i + 1$ 两个节点，分表表示 $x_i$ 为假和真。比如标记了 $2i + 1$ 这个节点表示 $x_i$ 这个变量为真，如果标记了 $2i $ 则表示 $x_i$ 为假。

对于 “$x_i$ 为真或 $x_j$ 为假”这个条件，我们添加一条 $2i$ 到 $2j$ 的边，表示如果 $x_i$ 为假的话，那么要使得条件成立 $x_j$ 一定要为假。另外同理也要添加一条 $2j + 1$ 到 $2i + 1$的边。注意上面的都是有向边，这里的边可以当做逻辑上的推导出的意思。

这样根据上面建完图后，接下来逐一考虑没有标记的变量，设为 $x_i$。我们先假定它为假，然后标记节点 $2i$，并且沿着有向边标记所有能标记的节点。如果标记过程中发现某个变量所对应的两个节点都被标记了，则 “ $x_i$ 为假” 这个假定不成立，需要改成 “ $x_i$ 为真”，然后退回到标记 “ $x_i$ 为假” 之前的状态，重新操作。注意，如果当前考虑的变量不管是真是假都会引起矛盾，可以证明整个 2-SAT 问题无解（即使调整以前赋值的其他变量都没用），所以这个算法是没有回溯过程的，这样最差的复杂度是 $O(N \cdot M)$。

其实对于 2-SAT 问题还 $O(M)$ 的算法，不过对于 2-SAT 问题一般是考的建图方式，不卡时间，这里给出几个链接：

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
struct TwoSat {
    static const int MAX_NODE = 1000;
    vector<int> G[MAX_NODE];
    int n, stk[MAX_NODE], sz;
    bool mark[MAX_NODE];

    void init(int _n) {
        n = _n;
        for (int i = 0; i < n * 2; ++i) G[i].clear();
        memset(mark, 0, sizeof(mark));
    }

    void addClause(int x, int xVal, int y, int yVal) {
        x = x * 2 + xVal, y = y * 2 + yVal;
        G[x ^ 1].push_back(y);
        G[y ^ 1].push_back(x);
    }

    bool dfs(int x) {
        if (mark[x ^ 1]) return false;
        if (mark[x]) return true;
        stk[sz++] = x;
        mark[x] = true;
        for (int i = 0; i < (int)G[x].size(); ++i)
            if (!dfs(G[x][i])) return false;
        return true;
    }

    bool solve() {
        for (int i = 0; i < n * 2; i += 2)
            if (!mark[i] && !mark[i ^ 1]) {
                sz = 0;
                if (!dfs(i)) {
                    while (sz > 0) mark[stk[--sz]] = false;
                    if (!dfs(i ^ 1)) return false;
                }
            }

        return true;
    }
};

扩展

上面描述的条件都只是 “或”，即是两个之中有一个成立，这里可以通过多个“或”条件的组合产生其他的逻辑条件。

条件 转化 实现
$a=b$ $a \vee \lnot b \bigwedge \lnot a \vee b $ add_clause(a, 1, b, 0); add_clause(a, 0, b, 1);
$a \neq b$ $a \vee b \bigwedge \lnot a \vee \lnot b$ add_clause(a, 0, b, 0); add_clause(a, 1, b, 1);
$a = b = true$ $a \vee \lnot b \bigwedge \lnot a \vee b \bigwedge a \vee b$ add_clause(a, 1, b, 1); add_clause(a, 1, b, 0); add_clause(a, 0, b, 1);
$a = b = false$ $a \vee \lnot b \bigwedge \lnot a \vee b \bigwedge \lnot a \vee \lnot b$ add_clause(a, 0, b, 0); add_clause(a, 1, b, 0); add_clause(a, 0, b, 1);