模板整理

发表于 | 分类于 | Views

后缀数组

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
char s[N];
int sa[N], rak[N], Height[N], tax[N], tp[N];
int n, m;

void RSort() {
    for (int i = 0; i <= m; i++) tax[i] = 0;
    for (int i = 1; i <= n; i++) tax[rak[tp[i]]]++;
    for (int i = 1; i <= m; i++) tax[i] += tax[i - 1];
    for (int i = n; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i];
}
int cmp(int *f, int x, int y, int w) {
    return x + w <= n && y + w <= n && f[x] == f[y] && f[x + w] == f[y + w];
}
void getSA() {
    for (int i = 1; i <= n; i++) rak[i] = s[i], tp[i] = i;
    m = 127, RSort();
    for (int w = 1, p = 1, i; p < n; w += w, m = p) {
        for (p = 0, i = n - w + 1; i <= n; i++) tp[++p] = i;
        for (i = 1; i <= n; i++) if (sa[i] > w) tp[++p] = sa[i] - w;
        RSort(), swap(rak, tp), rak[sa[1]] = p = 1;
        for (int i = 2; i <= n; i++) rak[sa[i]] = cmp(tp, sa[i], sa[i - 1], w) ? p : ++p;
    }
    int j, k = 0;
    for (int i = 1; i <= n; Height[rak[i++]] = k)
        for (k = k ? k - 1 : k, j = sa[rak[i] - 1]; s[i + k] == s[j + k]; ++k);
}

$meet$ $in$ $the$ $middle$ 求最大团 & 最大独立集

题目链接

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
#include <bits/stdc++.h>
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define pii pair<int, int>
#define debug(a) cout << #a": " << a << endl;
#define eularMod(a, b) a < b ? a : a % b + b
#define X first
#define Y second
#define lc rt << 1
#define rc rt << 1 | 1
inline int lowbit(int x){ return x & -x; }
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e6 + 10;
const int mod = (int) 10007;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double eps = 1e-6;

int n, m;
int f[(1 << 20) + 10];
bool hasA[(1 << 20) + 10];
bool hasB[(1 << 20) + 10];
int g[(1 << 20) + 10];
bool G[50][50];
map<string, int> idx;
int tmp[100];
bool vis[100];

int getOne(int x) {
    int res = 0;
    for (; x; x -= lowbit(x))
        res++;
    return res;
}

int main() {
#ifdef purple_bro
    freopen("in.txt", "r", stdin);
//    freopen("out.txt","w",stdout);
#endif
    int n, m;
    int num = 0;
    int tot = 0;

    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++)
            G[i][j] = true;
    }

    for (int i = 1; i <= n; i++) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            for (int i = 0; i < num; i++) {
                for (int j = 0; j < num; j++)
                    G[tmp[i]][tmp[j]] = false;
            }
            num = 0;
            mst(vis, false);
        } else {
            string s;
            cin >> s;
            if (idx.find(s) == idx.end())
                idx[s] = tot++;
            int x = idx[s];
            if (!vis[x]) {
                vis[x] = true;
                tmp[num++] = x;
            }
        }
    }
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++)
            G[tmp[i]][tmp[j]] = false;
    }

    int s1 = m / 2;
    int s2 = m - s1;

    hasA[0] = hasB[0] = true;

    for (int i = 0; i < 1 << s1; i++) if (hasA[i]) {
        for (int j = 0; j < s1; j++) if (!(i & (1 << j))) {
            bool flag = true;
            for (int k = 0; k < s1; k++) if (i & (1 << k))
                flag &= G[j][k];
            hasA[i | (1 << j)] = flag;
        }
    }

//    hasA[0] = false;

    for (int i = 0; i < 1 << s1; i++) if (hasA[i]) {
        for (int j = 0; j < s2; j++) {
            bool flag = true;
            for (int k = 0; k < s1; k++) if (i & (1 << k))
                flag &= G[k][s1 + j];
            f[i] |= (flag << j);
        }
    }

    for (int i = 0; i < s2; i++)
        g[1 << i] = 1;
    for (int i = 0; i < 1 << s2; i++) {
        for (int j = 0; j < s2; j++) if (!(i & (1 << j))) {
            bool flag = true;
            for (int k = 0; k < s2; k++) if (i & (1 << k))
                flag &= G[j + s1][k + s1];
            g[i | (1 << j)] = max(g[i | (1 << j)], g[i] + flag);
        }
    }

    int res = 0;

    for (int i = 0; i < 1 << s1; i++) if (hasA[i])
        res = max(res, getOne(i) + g[f[i]]);

    printf("%d\n", res);

    return 0;
}

李超树

题目链接

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
#include <bits/stdc++.h>
#include <ext/rope>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace __gnu_cxx;
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define pii pair<int, int>
#define debug(a) cout << #a": " << a << endl;
#define eularMod(a, b) a < b ? a : a % b + b
#define X first
#define Y second
#define lc rt << 1
#define rc rt << 1 | 1
inline int lowbit(int x){ return x & -x; }
typedef long long LL;
typedef unsigned long long ULL;
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = (int) 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double eps = 1e-6;

int seg[N << 2];
double k[M];
double b[M];

bool judge(int x, int y, int pos) {
    return k[x] * (pos - 1) + b[x] > k[y] * (pos - 1) + b[y];
}
void update(int L, int R, int now, int rt) {
    if (L == R) {
        if (judge(now, seg[rt], L))
            seg[rt] = now;
        return ;
    }
    int mid = L + R >> 1;
    if (k[now] > k[seg[rt]]) {
        if (judge(now, seg[rt], mid)) {
            update(L, mid, seg[rt], lc);
            // attention !
            seg[rt] = now;
        } else
            update(mid + 1, R, now, rc);
    }
    if (k[now] < k[seg[rt]]) {
        if (judge(now, seg[rt], mid)) {
            update(mid + 1, R, seg[rt], rc);
            // attention !
            seg[rt] = now;
        } else
            update(L, mid, now, lc);
    }
}
double getAns(int x, int pos) {
    return k[x] * (pos - 1) + b[x];
}
double query(int L, int R, int pos, int rt) {
    if (L == R)
        return getAns(seg[rt], pos);
    int mid = L + R >> 1;
    double res = getAns(seg[rt], pos);
    if (pos <= mid)
        return max(res, query(L, mid, pos, lc));
    else
        return max(res, query(mid + 1, R, pos, rc));
}

int main() {
#ifdef purple_bro
    freopen("in.txt", "r", stdin);
//    freopen("out.txt","w",stdout);
#endif
    int T;
    int tot = 0;

    scanf("%d", &T);

    for (;T--;) {
        char op[20];

        scanf("%s", op);

        if (op[0] == 'P') {
            tot++;
            scanf("%lf%lf", &b[tot], &k[tot]);
            update(1, 500000, tot, 1);
        } else {
            int d;
            scanf("%d", &d);
            double res = query(1, 500000, d, 1);
            int t = res;
            printf("%d\n", t / 100);
        }
    }

    return 0;
}