补一下题解

Pattern Matching

有一些串，$*$是通配符，求一个大串满足可以和所有小串匹配。

把小串按$*$分割成小段，那么有些段是前缀，有些是后缀，先把后缀前缀求出来，再把小段按先后顺序拼起来，就能保证满足要求了。
如果有合法的前缀后缀，必定是其最长的那个。
$O(n)$

Pattern Matching.cpp
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>
using namespace std;

int n;
string ts[55];
vector<string> pre, suf, mid;

void prase() {
    pre.clear(); suf.clear(); mid.clear();
    for (int k = 0; k < n; ++k) {
        string &s = ts[k];
        int la = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '*') {
                if (la == 0) pre.emplace_back(s.substr(la, i - la));
                else mid.emplace_back(s.substr(la, i - la));
                la = i + 1;
            }
        }
        suf.emplace_back(s.substr(la));
    }
}

bool check(string &s) {
    auto cmp = [&](string &a, string &b) { return a.length() > b.length(); };
    sort(pre.begin(), pre.end(), cmp);
    sort(suf.begin(), suf.end(), cmp);
    for (int i = 1; i < pre.size(); ++i) {
        if (pre[0].find(pre[i]) != 0) return true;
    }
    for (int i = 1; i < suf.size(); ++i) {
        if (suf[i].empty()) break;
        if (suf[0].rfind(suf[i]) != suf[0].length() - suf[i].length()) return true;
    }
    s = pre[0];
    for (string &t : mid) {
        s += t;
    }
    s += suf[0];
    return false;
}

int main() {
    int TT;
    cin >> TT;
    for (int cas = 1; cas <= TT; ++cas) {
        string ans;
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> ts[i];
        prase();
        if (check(ans))
            ans = '\*';
        printf("Case #%d: %s\n", cas, ans.c_str());
    }
    return 0;
}

Pascal Walk

要求在杨辉三角上走至多 $500$步，要求经过的点的和为$x$，且不走重复点。

杨辉三角第$i$行的和为$2^{i-1}$，那么假设前$30$行都走，那么和已经有$2^{31}-1 (>10^9)$了。
因此只需要在前$30$行内走$x$二进制下位$1$的行就可以得到，但因为不能跳跃，所一一定会多从两边的$1$的格子多走，那么转而对$x-30$求上述操作，其中多走的$1$的格子就计入额外要走的$30$内，最后把额外要走的走完。
$O(n)$

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

int main() {
    int TT;
    cin >> TT;
    for (int cas = 1; cas <= TT; ++cas) {
        int n;
        cin >> n;
        printf("Case #%d:\n", cas);
        if (n <= 30) {
            for (int i = 1; i <= n; ++i) {
                printf("%d 1\n", i);
            }
        } else {
            int t = n - 30, cc = 30, j = 1, i;
            for (i = 1; i <= 30; ++i) {
                if (t >> (i - 1) & 1) {
                    if (j != i) {
                        while (j < i)
                            printf("%d %d\n", i, j++);
                    } else {
                        while (j > 1)
                            printf("%d %d\n", i, j--);
                    }
                } else --cc;
                printf("%d %d\n", i, j);
                if (j == i) ++j;
            }
            while (cc--) {
                printf("%d %d\n", i++,j);
                if (j == i - 1) ++j;
            }
        }
    }
    return 0;
}

Square Dance

这道题的话就是暴力模拟了，不过每次考虑下一轮删谁的时候，由于每轮删只影响相邻的$4$个人，因此只考虑上轮删除的相邻位置的人，注意写时的细节就好。
$O(RC)$

Square Dance.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;

int x, y;
int u[N], d[N], l[N], r[N], v[N], vis[N];

inline int po(int a, int b){
    return a * y + b + 1;
}

double calc(int t) {
    vector<int> tp;
    if (u[t]) tp.emplace_back(v[u[t]]);
    if (d[t]) tp.emplace_back(v[d[t]]);
    if (l[t]) tp.emplace_back(v[l[t]]);
    if (r[t]) tp.emplace_back(v[r[t]]);
    double ss = 0;
    for (int k : tp) ss += k;
    if (tp.empty()) return 0.0;
    return ss / tp.size();
}

inline void init(int t) {
    if (i) u[t] = t - y;
    else u[t] = 0;
    if (i + 1 < x) d[t] = t+ y;
    else d[t] = 0;
    if (j) l[t] = t-1;
    else l[t] = 0;
    if (j + 1 < y) r[t] = t + 1;
    else r[t] = 0;
    vis[t] = INF32;
}

int main() {
    int TT;
    cin >> TT;
    for (int cas = 1; cas <= TT; ++cas) {
        int cc = 2;
        ll sum = 0;
        cin >> x >> y;
        for (int i = 0; i < x; ++i) {
            for (int j = 0; j < y; ++j) {
                int t = po(i, j);
                init(t);
                cin >> v[po(i, j)];
                sum += v[po(i, j)];
            }
        }
        ll ans = sum;
        queue<int> Q;
        for (int i = 0; i < x; ++i) {
            for (int j = 0; j < y; ++j) {
                int t = po(i, j);
                if (calc(t) > v[t]) {
                    vis[t] = 0;
                    sum -= v[t];
                    Q.emplace(t);
                }
            }
        }
        while (++cc) {
            if (Q.empty()) break;
            ans += sum;
            queue<int> q;
            while (!Q.empty()) {
                int t = Q.front();
                Q.pop();
                if (u[t]) d[u[t]] = d[t], q.emplace(u[t]);
                if (d[t]) u[d[t]] = u[t], q.emplace(d[t]);
                if (l[t]) r[l[t]] = r[t], q.emplace(l[t]);
                if (r[t]) l[r[t]] = l[t], q.emplace(r[t]);
            }
            while (!q.empty()) {
                int t = q.front();
                q.pop();
                if (vis[t] <= cc) continue;
                if (calc(t) > v[t]) {
                    vis[t] = cc;
                    sum -= v[t];
                    Q.emplace(t);
                }
            }
        }
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}