TOI 2020 初選小題解

Created2021-03-05Updated2021-03-05

題單

昨天看到蛋餅把去年初選的題目都丟到TIOJ了
最近也把pE精神掉了，想說就寫寫看，沒多久就把五題都寫完了
於是就來打個題解吧
雖然只剩下兩天就是ㄌ= =

pA

連結

題解

簽到題，直接做就好了

code

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
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lli long long int
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) {\
    for (auto A : x) {\
        cout << A << ' ';\
    }\
    cout << endl;\
}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
const int mod = 1e9 + 7, N = 2000000;

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int now = 0;
    for (char c : s) {
        if ('a' <= c && c <= 'z') {
            if (now) {
                for (int i = 0; i < now; ++i) cout << c;
                now = 0;
            } else {
                cout << c;
            }
        } else {
            now = now * 10 + c - '0';
        }
    }
}

pB

連結

題解

這題我是用重剖寫的，寫完發現單純樹DP也可做，作法其實差不多

重剖

重剖的時候，目標是要求出所有過重心的最長與嚴格次長
方法就是對於重心的每一棵子樹，算出這個子樹的最長與嚴格次長
合併的時候就用類似找樹直徑的做法，維護目前已經跑過的子樹中，最長與嚴格次長的距離
那麼需要更新的答案就會有三種：

  1. 原本的最長 + 當前最長
  2. 原本的最長 + 當前次長
  3. 原本的次長 + 當前最長

這樣做完就結束了~
實作上可能有些細節需要注意，需要好好維護「嚴格」次長

樹DP

樹DP的做法其實跟找直徑很類似
就從原本只維護最長改成多維護一個嚴格次長
合併的方法跟前面重剖一樣，分成三種case更新
好好維護完就結束了

實作上一樣要好好處理「嚴格」的問題

code

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
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 100001, K = 111;

vector <pii> adj[N];
int sz[N];
bool vis[N];

void dfs1(int v, int pa) {
    sz[v] = 1;
    for (pii A : adj[v]) if (A.X != pa && !vis[A.X]) {
        dfs1(A.X, v);
        sz[v] += sz[A.X];
    }
}

int dfs2(int v, int pa, int n) {
    for (pii A : adj[v]) if (A.X != pa && !vis[A.X]) {
        if (sz[A.X] > n / 2) {
            return dfs2(A.X, v, n);
        }
    }
    return v;
}

int dep[N];
pii ans;

void update(pii &a, pii b) {
    int c[5] = {0, a.X, a.Y, b.X, b.Y};
    sort(c, c + 5);
    a.X = c[4];
    for (int i = 3; i >= 0; --i) {
        if (c[i] ^ c[4]) {
            a.Y = c[i];
            break;
        }
    }
}

void add_ans(int x) {
    if (ans.X < x) ans = mp(x, ans.X);
    else if (ans.X != x && ans.Y < x) ans.Y = x;
}

pii dfs3(int v, int pa) {
    if (pa == -1) dep[v] = 0;
    pii mx = {dep[v], 0};
    for (pii A : adj[v]) if (A.X != pa && !vis[A.X]) {
        dep[A.X] = dep[v] + A.Y;
        add_ans(dep[A.X]);
        pii tmp = dfs3(A.X, v);
        if (pa == -1) {
            add_ans(mx.X + tmp.X);
            add_ans(mx.Y + tmp.X);
            add_ans(mx.X + tmp.Y);
        }
        update(mx, tmp);
    }
    return mx;
}

void cd(int v, int pa) {
    dfs1(v, pa);
    int c = dfs2(v, pa, sz[v]);
    dfs3(c, -1);
    vis[c] = true;
    for (pii A : adj[c]) if (!vis[A.X]) {
        cd(A.X, c);
    }
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0, u, v, w; i < n - 1; ++i) {
        cin >> u >> v >> w;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }
    cd(0, -1);
    cout << ans.Y << endl;
}

pC

連結

題解

事實上認真看題目就會發現兩條重要的式子
m≡(y2−y1)(x2−x1)−1(modM)m \equiv(y_2 - y_1)(x_2 - x_1)^{-1} \pmod M
x1+x2+x3≡m2(modM)x_1 + x_2 + x_3 \equiv m^2 \pmod M

所以做法就是

  1. 用快速冪算模逆元，再算出mm
  2. 帶入第二條式子，算出x3x_3
  3. 用y1≡mx1+ky_1 \equiv mx_1 + k算出kk，再用x3x_3回推出y3y_3

然後就做完了

code

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
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lli long long int
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) {\
    for (auto A : x) {\
        cout << A << ' ';\
    }\
    cout << endl;\
}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
const int mod = 1e9 + 7, N = 2000000;

lli modpow(lli a, lli b, lli m) {
    lli ans = 1;
    for (; b; b >>= 1, a = a * a % m) {
        if (b & 1) ans = ans * a % m;
    }
    return ans;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        lli mod, a, b, x1, y1, x2, y2;
        cin >> mod >> a >> b >> x1 >> y1 >> x2 >> y2;
        lli M = (y2 - y1) * modpow(x2 - x1, mod - 2, mod) % mod;
        if (M < 0) M += mod;
        lli K = y1 - M * x1 % mod;
        if (K < 0) K += mod;
        lli xsum = M * M % mod;
        lli x3 = (xsum - x1 - x2 + mod + mod) % mod;
        cout << x3 << ' ' << (x3 * M + K) % mod << endl;
    }
}

pD

連結

題解

可以發現只要每個點到原點的直線按照斜率排序好，並將相同斜率的點並在一起
這個問題就會轉換成「給一個環狀序列，問最大的連續區間和」

所以問題只在於

  1. 要怎麼處理斜率
  2. 要怎麼算環狀區間和

處理斜率？

問題同於要把點給極角排序
講一下兩種做法

  1. atan2

內建函數atan2會回傳一個點的極角，用法：

1
double atan2(int y, int x);

所以只要事先將x座標為負的點轉180度，再按照atan2的數值排序就好

  1. cross

首先一樣先把x座標為負的點轉180度，接著假設極角排序完後，順序會是順時針
那麼∀i<j,pt[i]×pt[j]≤0\forall i < j, pt[i] \times pt[j] \leq 0會成立
所以就直接把這個當作排序的依據，直接做就好

然後因為浮點數是垃圾，所以通常我會用第二種

環狀區間和？

首先先不考慮環狀，把她視為一般的陣列，那麼

環狀最大區間和 = max(陣列的最大連續和, 總陣列和 - 陣列的最小連續和)

前者是不考慮環狀的答案，後者是考慮環狀的答案

所以就用greedy算最大連續和的方法做兩次
再算一算答案就出來了~

code

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
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lli long long int
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) {\
    for (auto A : x) {\
        cout << A << ' ';\
    }\
    cout << endl;\
}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
const int mod = 1e9 + 7, N = 2000000;

struct pt {
    int x, y, v;
    lli operator ^ (const pt &o) {
        return 1ll * x * o.y - 1ll * y * o.x;
    }
    bool operator < (const pt& o) {
        return (*this ^ o) < 0;
    }
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <pt> A;
    for (int i = 0, x, y, v; i < n; ++i) {
        cin >> x >> y >> v;
        if (x < 0) x = -x, y = -y;
        else if (x == 0 && y < 0) y = -y;
        A.pb({x, y, v});
    }
    sort(all(A));
    vector <int> a;
    int al = 0;
    for (int i = 0, j = 0; i < n; i = j) {
        int val = 0;
        while (j < n && (A[i] ^ A[j]) == 0) val += A[j++].v;
        a.pb(val);
        al += val;
    }
    int mx = 0, mn = 0, now = 0;
    for (int i = 0; i < a.size(); ++i) {
        now += a[i];
        mx = max(mx, now);
        if (now < 0) now = 0;
    }
    now = 0;
    for (int i = 0; i < a.size(); ++i) {
        now += a[i];
        mn = min(mn, now);
        if (now > 0) now = 0;
    }
    cout << max(mx, al - mn) << endl;
}

pE

連結

題解

  • 先備知識：AC自動機

首先先把所有的小字串丟到一個AC自動機裡
建完fail陣列之後就能考慮這個dp式：
dp[i][j]dp[i][j]代表考慮大字串前ii個字元，且現在位於AC自動機的位置jj，最大的答案
可能有點抽象，但我不知道要怎麼進一步解釋@@
這樣轉移式的話就會考慮第i+1i + 1個字元能放甚麼字元，然後用類似AC自動機match的方式，計算加入字元後，AC自動機會移動到的位置，並加上新的AC自動機位置的小字串價值總和

複雜度會是O(n×∑∣S∣)\mathcal{O}(n \times \sum{|S|})

code

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>
using namespace std;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lli long long int
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) {\
    for (auto A : x) {\
        cout << A << ' ';\
    }\
    cout << endl;\
}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
const int mod = 1e9 + 7, N = 2000000;

int chg(char c) {
    if (c == 'r') return 1;
    else if (c == 'b') return 2;
    return 0;
}

struct AC {
    vector <vector <int>> ch;
    vector <int> cnt, f;
    AC () {extend();}
    void extend() {
        ch.pb(vector <int>(3, 0));
        cnt.pb(0);
        f.pb(0);
    }
    int getnxt(int u, int v) {
        if (ch[u][v]) return ch[u][v];
        extend();
        return ch[u][v] = ch.size() - 1;
    }
    void insert(string s, int v) {
        int now = 0;
        for (char c : s) {
            now = getnxt(now, chg(c));
        }
        cnt[now] += v;
    }
    void build_fail() {
        queue <int> q;
        for (int i : {0, 1, 2}) if (ch[0][i]) q.push(ch[0][i]);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int i : {0, 1, 2}) if (ch[v][i]) {
                int u = ch[v][i], k = f[v];
                while (k && !ch[k][i]) k = f[k];
                if (ch[k][i]) k = ch[k][i];
                f[u] = k;
                cnt[u] += cnt[k];
                q.push(u);
            }
        }
    }
} ac;

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, v;
    cin >> n >> m;
    string s;
    for (int i = 0; i < m; ++i) {
        cin >> s >> v;
        ac.insert(s, v);
    }
    ac.build_fail();
    cin >> s;
    vector <int> dp, pre;
    m = ac.ch.size();
    pre.assign(m, -1 << 30);
    pre[0] = 0;
    for (int i = 0; i < n; ++i) {
        dp.assign(m, -1 << 30);
        for (int j = 0; j < m; ++j) {
            if (pre[j] < 0) continue;
            if (s[i] == 'x') {
                for (int k : {0, 1, 2}) {
                    int now = j;
                    while (now && !ac.ch[now][k]) now = ac.f[now];
                    if (ac.ch[now][k]) now = ac.ch[now][k];
                    dp[now] = max(dp[now], pre[j] + ac.cnt[now]);
                }
            } else {
                int now = j, k = chg(s[i]);
                while (now && !ac.ch[now][k]) now = ac.f[now];
                if (ac.ch[now][k]) now = ac.ch[now][k];
                dp[now] = max(dp[now], pre[j] + ac.cnt[now]);
            }
        }
        swap(dp, pre);
    }
    cout << *max_element(all(pre)) << endl;
}