ToRapture's Blog

A Programmer

0%

Posted on Edited on Disqus:

https://hihocoder.com/contest/offers108/problems

A 再买优惠

暴力或二分一下 

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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

struct Price {
    int a, b;
    bool operator < (const Price &rhs) const {
        return this->a < rhs.a;
    }
};

int main(int argc, char **argv) {
    int n, c;
    while (~scanf("%d%d", &n, &c)) {
        vector<Price> vec;
        for (int i = 0; i < n; ++i) {
            Price p;
            scanf("%d%d", &p.a, &p.b);
            vec.push_back(p);
        }
        sort(vec.begin(), vec.end());
        int pos = upper_bound(vec.begin(), vec.end(), Price{c}) - vec.begin();
        if (pos == n) {
            printf("%d\n", vec[pos - 1].b);
        } else {
            printf("%d %d %d\n", vec[pos - 1].b, vec[pos].a - c, vec[pos].b);
        }
    }
    return 0;
}


/**
3 40
20 10
50 25
100 50

10 10 25
*/

B 树与落叶

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

#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int N = 1000000 + 16;

vector<int> G[N];
int max_depth, drop_time[N], total[N], drop_cnt[N];

void init(int n) {
    for (int i = 0; i <= n; ++i) {
        G[i].clear();
        total[i] = 0;
        drop_cnt[i] = 0;
    }
    max_depth = 0;
}

void dfs(int u, int fa, int depth) {
    drop_time[u] = 1;
    max_depth = max(max_depth, depth);
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u, depth + 1);
        drop_time[u] = max(drop_time[u], drop_time[v] + 1);
    }
}

int main(int argc, char **argv) {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        init(n);
        int root = 1;
        for (int i = 1; i <= n; ++i) {
            int f;
            scanf("%d", &f);
            if (f == 0) {
                root = i;
                continue;
            }
            G[f].push_back(i);
        }
        dfs(root, -1, 1);

        int len = drop_time[root] + 1;
        for (int i = 1; i <= n; i++)
            drop_cnt[drop_time[i]]++;
        total[0] = n;
        for (int i = 1; i < len; i++) {
            total[i] = total[i - 1] - drop_cnt[i];
        }

        while (m--) {
            int d;
            scanf("%d", &d);
            int pos = lower_bound(total, total + len, d, greater<int>()) - total;
            if (pos == len) {
                printf("%d\n", len);
            } else if (pos == 0) {
                printf("%d\n", 1);
            } else {
                if (abs(total[pos - 1] - d) <= abs(total[pos] - d)) {
                    printf("%d\n", pos);
                } else {
                    printf("%d\n", pos + 1);
                }
            }
        }
    }
    return 0;
}

/**
5 2
2 0 2 3 3
4 0

1
4
*/

C 树上的最短边

我是用树链剖分做的 

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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl
#define lrrt int L, int R, int rt
#define lson L, mid, rt << 1
#define rson mid + 1, R, rt << 1 | 1
#define iall 1, n, 1

using namespace std;
typedef long long LL;

const int N = 100000 + 16;

int tree[N << 2];
vector<int> G[N];
int n, m, ans[N];
int D[N], F[N], sz[N], son[N];
int W[N], _W[N], top[N], dfs_cnt;
void dfs(int u, int fa, int dep) {
    D[u] = dep;
    F[u] = fa;
    son[u] = 0;
    sz[u] = 1;
    for(int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if(v != fa) {
            dfs(v, u, dep + 1);
            sz[u] += sz[v];
            if(son[u] == 0 || sz[v] > sz[son[u]]) son[u] = v;
        }
    }
}
void dfs_hash(int u, int tp, int fa) {
    W[u] = ++dfs_cnt;
    _W[W[u]] = u;
    top[u] = tp;
    if(son[u]) dfs_hash(son[u], tp, u);
    for(int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if(v == son[u] || v == fa) continue;
        dfs_hash(v, v, u);
    }
}
void build(lrrt) {
    if(L == R) {
        tree[rt] = 0x3F3F3F3F;
    } else {
        int mid = L + R >> 1;
        build(lson);
        build(rson);
        tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]);
    }
}
void add(lrrt, int pos, int v) {
    if(L == R) {
        tree[rt] = v;
    } else {
        int mid = L + R >> 1;
        if(pos <= mid) add(lson, pos, v);
        else add(rson, pos, v);
        tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]);
    }
}
int query(lrrt, int x, int y) {
    if(x <= L && R <= y) return tree[rt];
    else {
        int mid = L + R >> 1;
        if(x > mid) return query(rson, x, y);
        else if(y <= mid) return query(lson, x, y);
        else return min(query(lson, x, y), query(rson, x, y));
    }
}
int query(int u, int v) {
    int res = 0x3F3F3F3F;
    while(top[u] != top[v]) {
        if(D[top[u]] < D[top[v]]) swap(u, v);
        res = min(res, query(iall, W[top[u]], W[u]));
        u = F[top[u]];
    }
    if(D[u] > D[v]) swap(u, v);
    if (u != v) {
        res = min(res, query(iall, W[son[u]], W[v]));
    }
    return res;
}
void add(int u, int val) {
    add(iall, W[u], val);
}
void init() {
    for(int i = 1; i <= n; ++i) G[i].clear();
    dfs_cnt = 0;
}

int pa[N], wc[N];

int main(int argc, char **argv) {
    while(~scanf("%d%d", &n, &m)) {
        init();
        int root = 1;
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &pa[i], &wc[i]);
            if (pa[i] == 0) {
                root = i;
                continue;
            }
            G[pa[i]].push_back(i);
            G[i].push_back(pa[i]);
        }
        dfs(root, -1, 0); dfs_hash(root, root, -1);
        build(iall);
        for (int i = 1; i <= n; ++i) {
            if (wc[i] == 0)
                continue;
            add(i, wc[i]);
        }
        while (m--) {
            int u, v;
            scanf("%d%d", &u, &v);
            printf("%d\n", query(u, v));
        }
    }
    return 0;
}

/**
5 2
2 1
0 0
2 2
3 3
3 4
4 1
2 5

1
2
*/

D 01匹配

线段树 

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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

#define lrrt int L, int R, int rt
#define lson L, mid, rt << 1
#define rson mid + 1, R, rt << 1 | 1
#define iall 1, n, 1

using namespace std;
typedef long long LL;

const int N = 300000 + 16;

struct Node {
    int ans, free_one, free_zero;
    Node() {}
    Node(int ans, int free_one, int free_zero):
        ans(ans), free_one(free_one), free_zero(free_zero) {}
    Node operator &(const Node &rhs) const {
        Node ret;
        ret.ans = this->ans + rhs.ans;
        int add = min(this->free_one, rhs.free_zero);
        ret.ans += add;
        ret.free_one = this->free_one + rhs.free_one - add;
        ret.free_zero = this->free_zero + rhs.free_zero - add;
        return ret;
    }
};

int a[N];
Node tree[N << 2];

void build(lrrt) {
    tree[rt].ans = 0;
    tree[rt].free_zero = 0;
    tree[rt].free_one = 0;
    if (L == R) {
        if (a[L]) tree[rt].free_one = 1;
        else tree[rt].free_zero = 1;
        return;
    }
    int mid = (L + R) / 2;
    build(lson);
    build(rson);
    tree[rt] = tree[rt << 1] & tree[rt << 1 | 1];
}

Node query(lrrt, int x, int y) {
    if (x <= L && R <= y) {
        return tree[rt];
    }
    int mid = (L + R) / 2;
    if (y <= mid) return query(lson, x, y);
    else if (x > mid) return query(rson, x, y);
    return query(lson, x, y) & query(rson, x, y);
}

int main(int argc, char **argv) {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        build(iall);
        int m;
        scanf("%d", &m);
        while (m--) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", query(iall, l, r).ans);
        }
    }
    return 0;
}

/**
10
0 1 0 1 0 0 1 0 1 0
100
1 10

4
*/

Posted on Edited on Disqus:

按照查询的边权w排序，离线add和query，注意树剖处理边权时的特殊逻辑。 

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl
#define lrrt int L, int R, int rt
#define lson L, mid, rt << 1
#define rson mid + 1, R, rt << 1 | 1
#define iall 1, n, 1
 
using namespace std;
typedef long long LL;

const int N = 500000 + 16;

int tree[N << 2];
vector<int> G[N];
int n, m, ans[N];
int D[N], F[N], sz[N], son[N];
int W[N], _W[N], top[N], dfs_cnt;
void dfs(int u, int fa, int dep) {
    D[u] = dep;
    F[u] = fa;
    son[u] = 0;
    sz[u] = 1;
    for(int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if(v != fa) {
            dfs(v, u, dep + 1);
            sz[u] += sz[v];
            if(son[u] == 0 || sz[v] > sz[son[u]]) son[u] = v;
        }
    }
}
void dfs_hash(int u, int tp, int fa) {
    W[u] = ++dfs_cnt;
    _W[W[u]] = u;
    top[u] = tp;
    if(son[u]) dfs_hash(son[u], tp, u);
    for(int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if(v == son[u] || v == fa) continue;
        dfs_hash(v, v, u);
    }
}
void build(lrrt) {
    if(L == R) {
        tree[rt] = 0;
    } else {
        int mid = L + R >> 1;
        build(lson);
        build(rson);
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
}
void add(lrrt, int pos, int v) {
    if(L == R) {
        tree[rt] += v;
    } else {
        int mid = L + R >> 1;
        if(pos <= mid) add(lson, pos, v);
        else add(rson, pos, v);
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
}
int query(lrrt, int x, int y) {
    if(x <= L && R <= y) return tree[rt];
    else {
        int mid = L + R >> 1;
        if(x > mid) return query(rson, x, y);
        else if(y <= mid) return query(lson, x, y);
        else return query(lson, x, y) + query(rson, x, y);
    }
}
int query(int u, int v) {
    int res = 0;
    while(top[u] != top[v]) {
        if(D[top[u]] < D[top[v]]) swap(u, v);
        res += query(iall, W[top[u]], W[u]);
        u = F[top[u]];
    }
    if(D[u] > D[v]) swap(u, v);
    if (u != v) {
        res += query(iall, W[son[u]], W[v]);
    }
    return res;
}
void add(int u, int val) {
    add(iall, W[u], val);
}
void init() {
    for(int i = 1; i <= n; ++i) G[i].clear();
    dfs_cnt = 0;
}

struct Op {
    int tp, u, v, i;
    LL w;
    bool operator < (const Op &rhs) const {
        return (this->w < rhs.w) || (this->w == rhs.w && this->tp == 0);
    }
    Op(int tp, int u, int v, LL w, int i): tp(tp), u(u), v(v), w(w), i(i) {}
};
int main(int argc, char **argv) {
    while(~scanf("%d%d", &n, &m)) {
        init();
        vector<Op> vec;
        for(int i = 1; i < n; ++i) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            G[u].push_back(v);
            G[v].push_back(u);
            vec.push_back(Op(0, u, v, w, 0));
        }
        for (int i = 1; i <= m; ++i) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            vec.push_back(Op(1, u, v, w, i));
        }
        sort(vec.begin(), vec.end());
        dfs(1, 1, 0); dfs_hash(1, 1, 1);
        build(iall);
        for (auto &op : vec) {
            if (op.tp == 1) {
                if (op.u == op.v) ans[op.i] = 0;
                else ans[op.i] = query(op.u, op.v);
            } else {
                if (D[op.u] > D[op.v]) add(op.u, 1);
                else add(op.v, 1); 
            }
        }
        for (int i = 1; i <= m; ++i)
            printf("%d\n", ans[i]);
    }
    return 0;
}
 
/**
3 3
1 3 2
2 3 7
1 3 0
1 2 4
1 2 7
5 2
1 2 1000000000
1 3 1000000000
2 4 1000000000
3 5 1000000000
2 3 1000000000
4 5 1000000000
5 7 
1 2 1000000000
1 3 1000000000
2 4 1000000000
3 5 1000000000
2 3 1000000000
4 5 1000000000
1 1 10000000000
2 2 10000000000
3 3 10000000000
4 4 10000000000
5 5 10000000000

0
1
2
2
4
*/

Posted on Edited on Disqus:

Max answer 与POJ 2796 Feel Good类似，但是这个题有负数，需要特殊处理一下

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>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

#define iall 1, n, 1
#define lrrt int l, int r, int rt
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1

const int MAXN = 500000 + 16;
const LL INF = 0x7F7F7F7F7F7F7F7F;
LL a[MAXN], sum[MAXN];
LL max_tree[MAXN << 2], min_tree[MAXN << 2];
int STK[MAXN], top;
int L[MAXN], R[MAXN];
int n;

void build(lrrt) {
    max_tree[rt] = min_tree[rt] = 0;
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    build(lson);
    build(rson);
}

void add(lrrt, int x, int v) {
    if (l == r) {
        max_tree[rt] = min_tree[rt] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) add(lson, x, v);
    else add(rson, x, v);
    max_tree[rt] = max(max_tree[rt << 1], max_tree[rt << 1 | 1]);
    min_tree[rt] = min(min_tree[rt << 1], min_tree[rt << 1 | 1]);
}

LL query_min(lrrt, int x, int y) {
    if (x <= l && r <= y) {
        return min_tree[rt];
    }
    int mid = (l + r) >> 1;
    if (x > mid) return query_min(rson, x, y);
    else if (y <= mid) return query_min(lson, x, y);
    else return min(query_min(lson, x, y), query_min(rson, x, y));
}

LL query_max(lrrt, int x, int y) {
    if (x <= l && r <= y) {
        return max_tree[rt];
    }
    int mid = (l + r) >> 1;
    if (x > mid) return query_max(rson, x, y);
    else if (y <= mid) return query_max(lson, x, y);
    else return max(query_max(lson, x, y), query_max(rson, x, y));
}

LL get_max(int x, int y) {
    if (y == 0)
        return 0;
    if (x == 0) {
        return max(LL(0), query_max(iall, 1, y));
    }
    return query_max(iall, x, y); 
}

void get_lr() {
    top = 0;
    for (int i = 1; i <= n; ++i) {
        L[i] = i;
        while (top && a[i] < a[STK[top]]) {
            L[i] = L[STK[top]];
            R[STK[top]] = i - 1;
            --top;
        }
        STK[++top] = i;
    }
    while (top) {
        R[STK[top--]] = n;
    }
}

int main(int argc, char **argv) {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]); a[n + 1] = -INF;
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
        get_lr();
        build(iall);
        for (int i = 1; i <= n; ++i) add(iall, i, sum[i]);
        LL ans = -INF;
        for (int i = 1; i <= n; ++i) {
            if (a[i] >= 0) {
                LL tmp = a[i] * (sum[R[i]] - sum[L[i] - 1]);
                ans = max(ans, tmp);
            } else {
                LL sr = query_min(iall, i, R[i]);
                LL sl = get_max(L[i] - 1, i - 1); 
                LL tmp = a[i] * (sr - sl);
                ans = max(ans, tmp);
            }
        }
        printf("%lld\n", ans);
    }
}

/**
5
1 2 3 4 5
5
-1 -2 -3 -4 -5
7
1 2 3 -1 -2 -3 8
7
1 2 3 -1 -2 -3 1
9
1 2 3 -1 -2 -3 8 -100 100

*/

Posted on Edited on Disqus:

令\(sum_{i, j}\)表示从\((i, j)\)开始沿着\((i - 1, j), (i - 2, j) \dots (0, j)\)方向的连续的\(1\)的个数， \[ sum_{i, j} = \begin{cases} 0 & m_{i, j} \ne 1 \\ 1 + sum_{i - 1, j} & m_{i, j} = 1 \\ \end{cases} \] 则答案为\(\max \left\{(k - j + 1) \times \min\{sum_{i, l} | \ j \le l \le k \} \ | \ 0 \le i < n, \ 0 \le j \le k < m \right\}\)。 枚举\(i, j, k\)可以用\(O(n \times m^2)\)的复杂度实现，用单调栈优化后可以\(O(n \times m)\)复杂度实现。

\(O(n \times m^2)\)实现： 

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
class Solution {
public:
    int maximalRectangle(vector<vector<char>> &matrix) {
        int n = matrix.size();
        if (n == 0) return 0;
        int m = matrix[0].size();
        if (m == 0) return 0;
        vector<vector<int>> sum(n, vector<int>(m));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    sum[i][j] = 1;
                    if (i > 0) sum[i][j] += sum[i - 1][j];
                } else {
                    sum[i][j] = 0;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int min_sum = sum[i][j];
                for (int k = j; k < m; k++) {
                    min_sum = min(min_sum, sum[i][k]);
                    ans = max(ans, (k - j + 1) * min_sum);
                }
            }
        }
        return ans;
    }
};

\(O(n \times 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

class Solution {
public:
    int maximalRectangle(vector<vector<char>> &matrix) {
        int n = matrix.size();
        if (n == 0) return 0;
        int m = matrix[0].size();
        if (m == 0) return 0;
        vector<vector<int>> sum(n, vector<int>(m + 1));
        vector<int> L(m + 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == '1') {
                    sum[i][j] = 1;
                    if (i > 0) sum[i][j] += sum[i - 1][j];
                } else {
                    sum[i][j] = 0;
                }
            }
            sum[i][m] = -1;
        }

        stack<int> stk;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                L[j] = j;
                while (!stk.empty() && sum[i][j] < sum[i][stk.top()]) {
                    L[j] = L[stk.top()];
                    ans = max(ans, (j - L[stk.top()]) * sum[i][stk.top()]);
                    stk.pop();
                }
                stk.push(j);
            }

        }
        return ans;
    }
};

Posted on Edited on Disqus:

有数组\(A[N], 1\le N \le 3 \cdot 10^5\)， \(P\)次查询，对于每次查询给出\(pos\)和\(k\)，求\(\sum\limits_{pos + m \cdot k \le N}^{} A[pos + m \cdot k]\)。

把所有查询按\(k\)分组，\(k \le \sqrt N\)的组\(O(N)\)处理，\(k \gt \sqrt N\)的组在\(O(\sqrt N)\)时间内处理， 总复杂度为\(O(\sqrt N \cdot N \ + \ (N - \sqrt N) \cdot \sqrt N) = O(2 \cdot N \sqrt N - N) = O(N \sqrt 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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int N = 300000 + 16;

struct Query {
    int st, k, id;
    LL ans;
    Query(int st, int k, int id): st(st), k(k), id(id) {}
    Query() {}
};

LL a[N], v[N];
vector<Query> Q[N];
int main(int argc, char **argv) {
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; ++i) scanf("%I64d", &a[i]);
        for(int i = 1; i <= n; ++i) Q[i].clear();
        int q; scanf("%d", &q);
        vector<int> have;
        for(int i = 0; i < q; ++i) {
            int st, k; scanf("%d%d", &st, &k);
            have.push_back(k);
            Q[k].push_back(Query(st, k, i));
        }
        sort(have.begin(), have.end()); have.erase(unique(have.begin(), have.end()), have.end());
        int sq = sqrt(n + 1);
        for(auto k : have) {
            if(k >= sq) {
                for(auto &query : Q[k]) {
                    int pos = query.st;
                    LL res = 0;
                    while(pos <= n) {
                        res += a[pos];
                        pos += k;
                    }
                    query.ans = res;
                }
            } else {
                fill(v, v + n + 1, 0);
                for(int i = n; i >= 1; --i) {
                    v[i] = a[i];
                    if(i + k <= n) v[i] += v[i + k];
                }
                for(auto &query : Q[k]) query.ans = v[query.st];
            }
        }
        vector<LL> ans(q);
        for(auto k : have) for(auto query : Q[k]) ans[query.id] = query.ans;
        for(auto x : ans) printf("%I64d\n", x);
    }
    return 0;
}

Posted on Edited on Disqus:

简单二维偏序

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int N = 32000 + 16;

struct Point {
    int x, y;
    Point() {}
    Point(int x, int y): x(x), y(y) {}
    bool operator < (const Point &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); }
    void read() { scanf("%d%d", &x, &y); ++x, ++y; }
} P[N];

struct Bit {
    int C[N];
    int n;
    void init(int n) {
        this->n = n;
        fill(C, C + n + 1, 0);
    }
    int lowbit(int x) { return x & -x; }
    void add(int x, int v) {
        for(; x <= n; x += lowbit(x)) C[x] += v;
    }
    int sum(int x) {
        int res = 0;
        for(; x; x -= lowbit(x)) res += C[x];
        return res;
    }
    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
} bit;

int ans[N];

int main(int argc, char **argv) {
    int n;
    while(~scanf("%d", &n)) {
        for(int i = 0; i < n; ++i) P[i].read();
        fill(ans, ans + n, 0);
        sort(P, P + n);
        bit.init(N - 1);
        for(int i = 0; i < n; ++i) {
            ++ans[bit.sum(P[i].y)];
            bit.add(P[i].y, 1);
        }
        for(int i = 0; i < n; ++i) printf("%d\n", ans[i]);
    }
    return 0;
}

Posted on Edited on Disqus:

有一个\(N+1\)个结点的树\(T\)。 现在有\(Q\)个信息，每条信息为\(q:(u,v)\)，表示\(u\)到\(v\)的路径不通。 问树\(T\)至少被破坏多少个节点才能达到当前这种局面。

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
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

#define mt(a, b) memset(a, b, sizeof(a))

struct LCA { ///最近公共祖先 build O(V*logV) query O(1)
    typedef int typec; ///边权的类型
    static const int MV = 100000 + 16; ///点的个数
    static const int MR = MV << 1; ///rmq 的个数

    int Index, H[MV], dex[MR], a[MR], b[MR], F[MR], ra[MR][20], rb[MR][20];
    typec dist[MV];
    struct G {
        struct E {
            int v, next;
            typec w;
        } e[MV << 1];
        int le, head[MV];
        void init(int n) {
            le = 0;
            for(int i = 0; i <= n; i++) head[i] = -1;
        }
        void add(int u, int v, typec w) {
            e[le].v = v;
            e[le].w = w;
            e[le].next = head[u];
            head[u] = le++;
        }
    } g;
    void init_dex() {
        dex[0] = -1;
        for(int i = 1; i < MR; i++) {
            dex[i] = dex[i >> 1] + 1;
        }
    }
    void dfs(int u, int fa, int level) {
        a[Index] = u;
        b[Index++] = level;
        F[u] = fa;
        for(int i = g.head[u]; ~i; i = g.e[i].next) {
            int v = g.e[i].v;
            if(v == fa) continue;
            dist[v] = dist[u] + g.e[i].w;
            dfs(v, u, level + 1);
            a[Index] = u;
            b[Index++] = level;
        }
    }

    LCA() {
        init_dex();
    };
    void init(int n) {
        g.init(n);
    }

    void add(int u, int v, typec w) {
        g.add(u, v, w);
        g.add(v, u, w);
    }
    void build(int root) { ///传入树根
        Index = 0;
        dist[root] = 0;
        dfs(root, -1, 0);
        mt(H, -1);
        mt(rb, 0x3f);
        for(int i = 0; i < Index; i++) {
            int tmp = a[i];
            if(H[tmp] == -1) H[tmp] = i;
            rb[i][0] = b[i];
            ra[i][0] = a[i];
        }
        for(int i = 1; (1 << i) <= Index; i++) {
            for(int j = 0; j + (1 << i) < Index; j++) {
                int next = j + (1 << (i - 1));
                if(rb[j][i - 1] <= rb[next][i - 1]) {
                    rb[j][i] = rb[j][i - 1];
                    ra[j][i] = ra[j][i - 1];
                    continue;
                }
                rb[j][i] = rb[next][i - 1];
                ra[j][i] = ra[next][i - 1];
            }
        }
    }
    int getlca(int l, int r) { ///查最近公共祖先
        l = H[l];
        r = H[r];
        if(l > r) swap(l, r);
        int p = dex[r - l + 1];
        r -= (1 << p) - 1;
        return rb[l][p] <= rb[r][p] ? ra[l][p] : ra[r][p];
    }
    typec getdist(int id) { ///查根到点最短距离
        return dist[id];
    }
    typec getdist(int l, int r) { ///查两点最短距离
        return dist[l] + dist[r] - 2 * dist[getlca(l, r)];
    }
} yoshiko;

int n, q;

struct Query {
    int u, v, lca, d;
    Query(int u, int v, int lca, int d): u(u), v(v), lca(lca), d(d) {}
    Query() {}
    bool operator < (const Query &rhs) const {
        return d > rhs.d;
    }
};

bool vis[100000 + 16];

void dfs(int u) {
    vis[u] = true;
    for(int i = yoshiko.g.head[u]; ~i; i = yoshiko.g.e[i].next) {
        int v = yoshiko.g.e[i].v;
        if(v != yoshiko.F[u] && !vis[v]) dfs(v);
    }
}

int main(int argc, char **argv) {
    while(~scanf("%d", &n)) {
        ++n; yoshiko.init(n);
        for(int i = 1; i < n; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            yoshiko.add(u, v, 1);
        }
        yoshiko.build(0);
        vector<Query> Q;
        scanf("%d", &q);
        while(q--) {
            int u, v; scanf("%d%d", &u, &v);
            int lca = yoshiko.getlca(u, v);
            int dist = yoshiko.getdist(lca);
            Q.push_back(Query(u, v, lca, dist));
        }

        sort(Q.begin(), Q.end());

        int ans = 0;
        memset(vis, false, sizeof(vis));
        for(auto &query : Q) {
            if(!vis[query.u] && !vis[query.v]) {
                ++ans;
                dfs(query.lca);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Posted on Edited on Disqus:

1001 Apple 给了四个点\(A,B,C,P\)，问点\(P\)是否在\(\Delta_{ABC}\)的外接圆外。 用C++被卡了精度，用Java过的。

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
import java.math.BigDecimal;
import java.util.Scanner;

/**
 * Created by ToRapture on 2017/9/17.
 */
public class Main {

    static BigDecimal dist(Point a, Point b) {
        return a.x.subtract(b.x).multiply(a.x.subtract(b.x)).add(a.y.subtract(b.y).multiply(a.y.subtract(b.y)));
    }
    static BigDecimal circumscir(Point a, Point b, Point c, Point res) {
        BigDecimal bx = b.x.subtract(a.x);
        BigDecimal by = b.y.subtract(a.y);

        BigDecimal cx = c.x.subtract(a.x);
        BigDecimal cy = c.y.subtract(a.y);

        BigDecimal d = BigDecimal.valueOf(2L).multiply(bx.multiply(cy).subtract(by.multiply(cx)));

        BigDecimal x = cy.multiply( bx.multiply(bx).add(by.multiply(by))).subtract(by.multiply( cx.multiply(cx).add(cy.multiply(cy))))
                .divide(d).add(a.x);
        BigDecimal y = bx.multiply( cx.multiply(cx).add(cy.multiply(cy))).subtract(cx.multiply( bx.multiply(bx).add(by.multiply(by))))
                .divide(d).add(a.y);

        res.x = x;
        res.y = y;
        BigDecimal r = dist(a, res);
        return r;
    }
    static int dcmp(BigDecimal x) {
        BigDecimal eps = new BigDecimal("0.000000000000001");
        if(x.compareTo(eps) > 0) return 1;
        else if(x.compareTo(eps.multiply(new BigDecimal("-1"))) < 0) return -1;
        else return 0;

    }
    static boolean fuck(Point a, Point b, Point c, Point p) {
        if(p.equals(a) || p.equals(b) || p.equals(c)) return false;
        Point o = new Point();
        BigDecimal r = circumscir(a, b, c, o);

        if(dcmp(dist(p, o).subtract(r)) <= 0) return false;
        else return true;
    }

    static public void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while(--T >= 0) {
            Point a = new Point();
            Point b = new Point();
            Point c = new Point();
            Point p = new Point();
            a.read(scan);
            b.read(scan);
            c.read(scan);
            p.read(scan);
            if(fuck(a, b, c, p)) System.out.println("Accepted");
            else System.out.println("Rejected");

        }
        scan.close();
    }
}

class Point {
    BigDecimal x, y;
    Point() {}
    Point(BigDecimal x, BigDecimal y) {
        this.x = x;
        this.y = y;
    }
    public void read(Scanner scan) {
        x = scan.nextBigDecimal();
        y = scan.nextBigDecimal();
    }
}

1003 The Dominator of Strings Hash加乱搞过的，据说暴力strstr也能过。

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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;
struct HASH {
    typedef LL typec;
    static const int MaxN = 100000 + 16;
    static const LL key = 137;

    typec H[MaxN], xp[MaxN];

    void init(const char s[], int len) {
        H[len] = 0;
        for(int i = len - 1; i >= 0; --i) {
            H[i] = H[i + 1] * key + s[i];
        }
        xp[0] = 1;
        for(int i = 1; i <= len; ++i) {
            xp[i] = xp[i - 1] * key;
        }
    }
    typec get(int pos, int len) {
        return H[pos] - H[pos + len] * xp[len];
    }
} yoshiko;
const int N = 100000 + 16;
char buf[N];
LL H[N];
vector<int> F[256];
char fst[N];
int L[N];
int main(int argc, char **argv) {
    int T; scanf("%d", &T);
    while(T--) {
        int n; scanf("%d", &n);
        string str;
        int select = -1;
        for(int i = 0; i < n; ++i) {
            scanf("%s", buf);
            int l = strlen(buf);
            fst[i] = buf[0];
            L[i] = l;
            if(str.size() < l) {
                str = buf;
                select = i;
            }
            LL h = 0;
            for(int i = l - 1; i >= 0; --i) h = h * 137LL + buf[i];
            H[i] = h;
        }
        yoshiko.init(str.c_str(), str.size());
        for(char c = 'a'; c <= 'z'; ++c) F[c].clear();
        for(int i = 0; i < str.size(); ++i) F[str[i]].push_back(i);
        bool ok = true;

        for(int i = 0; i < n && ok; ++i) {
            if(i == select) continue;
            ok = false;
            for(auto p : F[fst[i]]) {
                if(p + L[i] <= str.size() && yoshiko.get(p, L[i]) == H[i]) {
                    ok = true;
                    break;
                }

            }
        }

        if(ok) puts(str.c_str());
        else puts("No");

    }
    return 0;
}

1008 Chinese Zodiac 签到题。

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>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

int main(int argc, char **argv) {
    map<string, int> mp;
    mp["rat"] = 0;
    mp["ox"] = 1;
    mp["tiger"] = 2;
    mp["rabbit"] = 3;
    mp["dragon"] = 4;
    mp["snake"] = 5;
    mp["horse"] = 6;
    mp["sheep"] = 7;
    mp["monkey"] = 8;
    mp["rooster"] = 9;
    mp["dog"] = 10;
    mp["pig"] = 11;

    map<int, string> pm;
    for(auto it : mp) pm[it.second] = it.first;

    int T; cin >> T;
    while(T--) {
        string a, b;
        cin >> a >> b;
        int c = 0;
        if(a == b) c = 12;
        else {
            int pos = mp[a];
            while(pos != mp[b]) {
                ++c;
                pos = pos + 1;
                pos %= 12;
            }
        }
        cout << c << endl;
    }
    return 0;
}

1009 Smallest Minimum Cut 求最小割中割边数最小的割的边数。

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>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;
struct Dinic {  //时间复杂度O(min(n * sqrt(n), sqrt(m)) * m)
    static const int maxn = 3000 + 16;
    static const int INF = 0x7F7F7F7F;
    struct Edge {
        int from, to;
        LL cap, flow;
        Edge(int from, int to, LL cap, LL flow):
            from(from), to(to), cap(cap), flow(flow) {}
        Edge() {}
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn], cur[maxn];

    int n, m, s, t; //n与m不需要特殊赋值，s与t在调用主过程的时候传就可以

    void init(int n = maxn - 1) {
        this->n = n;
        for(int i = 0; i <= n; ++i) G[i].clear();
        edges.clear();
    }

    void add_edge(int from, int to, LL cap) {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool BFS() {
        memset(vis, false, sizeof(vis));
        queue<int> Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = true;
        while(!Q.empty()) {
            int x = Q.front(); Q.pop();
            for(int i = 0; i < G[x].size(); ++i) {
                Edge &e = edges[G[x][i]];
                if(!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    LL DFS(int x, LL a) {
        if(x == t || a == 0) return a;
        LL flow = 0, f;
        for(int &i = cur[x]; i < G[x].size(); ++i) {
            Edge &e = edges[G[x][i]];
            if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if(a == 0) break;
            }
        }
        return flow;
    }
    LL MaxFlow(int s, int t) {
        this->s = s; this->t = t;
        LL flow = 0;
        while(BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, INF);
        }
        return flow;
    }
} Dinic;

const LL BIG = 10000000LL;

int main(int argc, char **argv) {
    int T; scanf("%d", &T);
    while(T--) {
        int n, m; scanf("%d%d", &n, &m);
        int s, t; scanf("%d%d", &s, &t);
        Dinic.init(n);
        while(m--) {
            int u, v, c; scanf("%d%d%d", &u, &v, &c);
            Dinic.add_edge(u, v, c * BIG + 1);
        }
        printf("%lld\n", Dinic.MaxFlow(s, t) % BIG);
    }
    return 0;
}

1011 A Cubic number and A Cubic Number 好像也是签到题。 

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
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;

typedef long long LL;

int main(int argc, char **argv) {
    int T; cin >> T;
    while(T--) {
        double d; cin >> d;
        double p = powf(d, 1.0 / 3);
        LL s = p - 1;
        if(s < 0) s = 0;
        bool fuck = false;
        for(LL i = s; ; i++) {
            LL x = i * i * i;
            LL y = (i + 1) * (i + 1) * (i + 1);
            if(y - x == d) {
                puts("YES");
                fuck = true; break;
            } else if(y - x > d) break;
        }
        if(!fuck) puts("NO");
    }
    return 0;
}

Posted on Edited on Disqus:

求字符串\(str\)中包含某个字符的互不相同的子串个数。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int maxn = 100000 + 16;
/*********************************************
*********************
** 后缀数组 Suffix Array
** INIT：solver.call_fun(char* s);
** CALL: solver.lcp(int i,int j); //后缀 i 与后缀 j 的最
长公共前缀
** SP_USE: solver.LCS(char *s1,char* s2); //最长公
共字串
**********************************************
********************/
struct SuffixArray {
    int r[maxn];
    int sa[maxn], rank[maxn], height[maxn];
    int t[maxn], t2[maxn], c[maxn], n;
    int m;//模板长度
    void init(char s[]) {
        n = strlen(s);
        for (int i = 0; i < n; i++) r[i] = int(s[i]);
        m = 128;
    }
    int cmp(int *r, int a, int b, int l) {
        return r[a] == r[b] && r[a + l] == r[b + l];
    }
    /**
    字符要先转化为正整数
    待排序的字符串放在 r[]数组中，从 r[0]到 r[n-1]，
    长度为 n，且最大值小于 m。
    所有的 r[i]都大于 0,r[n]无意义算法中置 0
    函数结束后，结果放在 sa[]数组中(名次从 1..n)，
    从 sa[1]到 sa[n]。s[0]无意义
    **/
    void build_sa() {
        int i, k, p, *x = t, *y = t2;
        r[n++] = 0;
        for (i = 0; i < m; i++) c[i] = 0;
        for (i = 0; i < n; i++) c[x[i] = r[i]]++;
        for (i = 1; i < m; i++) c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
        for (k = 1, p = 1; k < n; k *= 2, m = p) {
            for (p = 0, i = n - k; i < n; i++) y[p++] = i;
            for (i = 0; i < n; i++) if (sa[i] >= k)
                    y[p++] = sa[i] - k;
            for (i = 0; i < m; i++) c[i] = 0;
            for (i = 0; i < n; i++) c[x[y[i]]]++;
            for (i = 1; i < m; i++) c[i] += c[i - 1];
            for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;
        }
        n--;
    }
    /**
    height[2..n]:height[i]保存的是 lcp(sa[i],sa[i-1])
    rank[0..n-1]:rank[i]保存的是原串中 suffix[i]的名
    次
    **/
    void getHeight() {
        int i, j, k = 0;
        for (i = 1; i <= n; i++) rank[sa[i]] = i;
        for (i = 0; i < n; i++) {
            if (k) k--;
            j = sa[rank[i] - 1];
            while (r[i + k] == r[j + k]) k++;
            height[rank[i]] = k;
        }
    }
    int d[maxn][20];
//元素从 1 编号到 n
    void RMQ_init(int A[], int n) {
        for (int i = 1; i <= n; i++) d[i][0] = A[i];
        for (int j = 1; (1 << j) <= n; j++)
            for (int i = 1; i + (1 << (j - 1)) <= n; i++)

                d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
    }
    int RMQ(int L, int R) {
        int k = 0;
        L = rank[L];
        R = rank[R];
        if(L > R) swap(L, R);
        L++;
        while ((1 << (k + 1)) <= R - L + 1) k++;
        return min(d[L][k], d[R - (1 << k) + 1][k]);
    }
    void LCP_init() {
        RMQ_init(height, n);
    }
    int lcp(int i, int j) {
        if (rank[i] > rank[j]) swap(i, j);
        return RMQ(rank[i] + 1, rank[j]);
    }
    void call_fun(char s[]) {
        init(s);//初始化后缀数组
        build_sa();//构造后缀数组 sa
        getHeight();//计算 height 与 rank
        LCP_init();//初始化 RMQ
    }
    int so(int n) {
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            ans += (n - sa[i] - height[i]);
        }
        return ans;
    }
} yoshiko;

char s[maxn];
int R[maxn];
int main(int argc, char **argv) {
    int T; scanf("%d", &T);
    for(int cas = 1; cas <= T; ++cas) {
        char ch[4];
        scanf("%s%s", ch, s);
        int n = strlen(s);
        for(int i = n - 1; i >= 0; --i) {
            if(i == n - 1) {
                if(s[i] == ch[0]) R[i] = i;
                else R[i] = n;
            } else {
                R[i] = R[i + 1];
                if(s[i] == ch[0]) R[i] = i;
            }
        }
        yoshiko.call_fun(s);
        LL ans = 0;
        for(int i = 1; i <= n; ++i) {
            LL tmp = max(0, n - max(yoshiko.sa[i] + yoshiko.height[i], R[yoshiko.sa[i]]));
            ans += tmp;
        }
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

Posted on Edited on Disqus:

求至少可重叠重复\(K\)次的最长子串的长度。 解法为二分长度后对height数组分组。

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
149
150
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int maxn = 2000000 + 16;
/*********************************************
*********************
** 后缀数组 Suffix Array
** INIT：solver.call_fun(char* s);
** CALL: solver.lcp(int i,int j); //后缀 i 与后缀 j 的最
长公共前缀
** SP_USE: solver.LCS(char *s1,char* s2); //最长公
共字串
**********************************************
********************/
struct SuffixArray {
    int r[maxn];
    int sa[maxn], rank[maxn], height[maxn];
    int t[maxn], t2[maxn], c[maxn], n;
    int m;//模板长度
    void init(int s[], int n) {
        this->n = n;
        for (int i = 0; i < n; i++) r[i] = int(s[i]);
        m = 1000000 + 16;
    }
    int cmp(int *r, int a, int b, int l) {
        return r[a] == r[b] && r[a + l] == r[b + l];
    }
    /**
    字符要先转化为正整数
    待排序的字符串放在 r[]数组中，从 r[0]到 r[n-1]，
    长度为 n，且最大值小于 m。
    所有的 r[i]都大于 0,r[n]无意义算法中置 0
    函数结束后，结果放在 sa[]数组中(名次从 1..n)，
    从 sa[1]到 sa[n]。s[0]无意义
    **/
    void build_sa() {
        int i, k, p, *x = t, *y = t2;
        r[n++] = 0;
        for (i = 0; i < m; i++) c[i] = 0;
        for (i = 0; i < n; i++) c[x[i] = r[i]]++;
        for (i = 1; i < m; i++) c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
        for (k = 1, p = 1; k < n; k *= 2, m = p) {
            for (p = 0, i = n - k; i < n; i++) y[p++] = i;
            for (i = 0; i < n; i++) if (sa[i] >= k)
                    y[p++] = sa[i] - k;
            for (i = 0; i < m; i++) c[i] = 0;
            for (i = 0; i < n; i++) c[x[y[i]]]++;
            for (i = 1; i < m; i++) c[i] += c[i - 1];
            for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;
        }
        n--;
    }
    /**
    height[2..n]:height[i]保存的是 lcp(sa[i],sa[i-1])
    rank[0..n-1]:rank[i]保存的是原串中 suffix[i]的名
    次
    **/
    void getHeight() {
        int i, j, k = 0;
        for (i = 1; i <= n; i++) rank[sa[i]] = i;
        for (i = 0; i < n; i++) {
            if (k) k--;
            j = sa[rank[i] - 1];
            while (r[i + k] == r[j + k]) k++;
            height[rank[i]] = k;
        }
    }
    int d[maxn][20];
//元素从 1 编号到 n
    void RMQ_init(int A[], int n) {
        for (int i = 1; i <= n; i++) d[i][0] = A[i];
        for (int j = 1; (1 << j) <= n; j++)
            for (int i = 1; i + (1 << (j - 1)) <= n; i++)

                d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
    }
    int RMQ(int L, int R) {
        int k = 0;
        L = rank[L];
        R = rank[R];
        if(L > R) swap(L, R);
        L++;
        while ((1 << (k + 1)) <= R - L + 1) k++;
        return min(d[L][k], d[R - (1 << k) + 1][k]);
    }
    void LCP_init() {
        RMQ_init(height, n);
    }
    int lcp(int i, int j) {
        if (rank[i] > rank[j]) swap(i, j);
        return RMQ(rank[i] + 1, rank[j]);
    }
    void call_fun(int s[], int n) {
        init(s, n);//初始化后缀数组
        build_sa();//构造后缀数组 sa
        getHeight();//计算 height 与 rank
        LCP_init();//初始化 RMQ
    }
    int so(int n) {
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            ans += (n - sa[i] - height[i]);
        }
        return ans;
    }
} solver;

int a[maxn];
int n, k;

bool fuck(int x) {
    int sum = 0;
    for(int i = 2; i <= n; ++i) {
        if(solver.height[i] >= x) ++sum;
        else {
            if(sum + 1 >= k) return true;
            sum = 0;
        }
    }
    if(sum + 1 >= k) return true;
    return false;
}

int main(int argc, char **argv) {
    while(~scanf("%d%d", &n, &k)) {
        for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
        solver.call_fun(a, n);
        int res = 0, L = 0, R = n;
        while(L <= R) {
            int mid = L + R >> 1;
            if(fuck(mid)) res = mid, L = mid + 1;
            else R = mid - 1;
        }
        printf("%d\n", res);
    }
    return 0;
}