正常了一把，可惜没过了E

前两题也没啥好讲的，看代码就🆗

1337A Ichihime and Triangle

A.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << b << ' ' << c << ' ' << c << endl;
    }
    return 0;
}

1337B Kana and Dragon Quest game

B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int x, n, m;
        cin >> x >> n >> m;
        while (x > 0) {
            if (n && x > 20) 
                --n, x = x / 2 + 10;
            else if (m) 
                --m, x -= 10;
            else break;
        }
        if (x > 0) puts("NO");
        else puts("YES");
    }
    return 0;
}

1336A Linova and Kingdom

有一颗以$1$为根的树，把$k$个点涂成黑色，问每个黑色点到根的路径上白色点数量的和是多少。

如果一个点涂黑了，意味着这颗子树全部被涂黑了，那么讨论这个点（的子树除了自己全部涂色后）涂色对答案的贡献，即 $(dpt_i-1)sz_i-dpt_i(sz_i-1)$，排序后取前$n-k$大就是答案，$O(n\log n)$，题解提到如果用 $STL$ 的 $nth_element()$ 部分排序可以做到$O(n)$。

C.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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;

ll cnt[N], dpt[N];
vector<int> g[N];
vector<pii> ps;

void dfs(int u, int fa) {
    for (int v : g[u]) {
        if (v == fa) continue;
        dpt[v] = dpt[u] + 1;
        dfs(v, u);
        cnt[u] += cnt[v];
    }
    ++cnt[u];
    ps.emplace_back(u, (dpt[u] - 1) * cnt[u] - dpt[u] * (cnt[u] - 1));
}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    dpt[1] = 1;
    dfs(1, 0);
    ll ans = 0;
    sort(ps.begin(), ps.end(), [&](pii a, pii b) { return a.second > b.second; });
    for (int i = 0; i < k; ++i) {
        ans += ps[i].second;
    }
    cout << ans << endl;
    return 0;
}

1336B Xenia and Colorful Gems

有三种颜色的宝石，每个宝石都有权值，要求每个颜色的宝石取一个，问能取的最小的$(x-y)^2+(y-z)^2+(z-x)^2$是多少。

如果我们将取得得三个值排序，那么两边得数越接近中间的，答案就越小。因此枚举中间值，二分找另外两个数，$O(n\log n)$。

D.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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;

ll ans;
int a[3][N], n[3];

void calc(int q, int w, int e) {
    for (int i = 0; i < n[q]; ++i) {
        auto p2 = lower_bound(a[w], a[w] + n[w], a[q][i]) - a[w];
        auto p3 = upper_bound(a[e], a[e] + n[e], a[q][i]) - a[e];
        if (p3 != 0) --p3;
        if (p2 == n[w]) --p2;
        ll x = a[q][i], y = a[w][p2], z = a[e][p3];
        ans = min(ans, (x - y) * (x - y) + (x - z) * (x - z) + (y - z) * (y - z));
        p2 = upper_bound(a[w], a[w] + n[w], a[q][i]) - a[w];
        p3 = lower_bound(a[e], a[e] + n[e], a[q][i]) - a[e];
        if (p2 != 0) --p2;
        if (p3 == n[e]) --p3;
        x = a[q][i], y = a[w][p2], z = a[e][p3];
        ans = min(ans, (x - y) * (x - y) + (x - z) * (x - z) + (y - z) * (y - z));
    }
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        cin >> n[0] >> n[1] >> n[2];
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < n[i]; ++j) {
                cin >> a[i][j];
            }
            sort(a[i], a[i] + n[i]);
        }
        ans = LLONG_MAX;
        calc(0,1,2);
        calc(1,0,2);
        calc(2,1,0);
        cout << ans << endl;
    }
    return 0;
}

1336C Kaavi and Magic Spell

感觉挺开拓思维的一道题 其实是我$dp$太差想不到
有两个字符串$s,t$和一个空串$a$，现在每次操作可以把$s$的首字母添加到$a$的头或尾，问在所有的操作序列中，产生的$a$以$t$为前缀个序列个数，具体题意请看样例解释吧。

正解是区间$dp$，设$dp[l][r]$为操作第$x$个字母后，与$t[l][r]$匹配的$a$的个数，那么：

  • 当枚举到第$x$个字母时，$r=l+x-1$；
  • 当$s_x == t_l$时，也就是说可以从$dp[l+1][r]$转移到$dp[l][r]$；
  • 当$s_x == t_r$时，也就是说可以从$dp[l][r-1]$转移到$dp[l][r]$；
  • 对于上述的$l,r>m$时，因为已经不会影响匹配，就可以直接转移；
  • 当$x=1$时，需要从$dp[i][i-1]$转移一下，此时设为$1$即可；
    答案即$\sum_{i=m}^n dp[1][i]$，$O(n^2)$
E.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
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.length(), m = t.length();
    s = ' ' + s, t = ' ' + t;
    vector<vector<int>> dp(n + 2, vector<int> (n + 2));
    for (int i = 1; i <= n + 1; ++i) {
        dp[i][i - 1] = 1;
    }

    for (int i = 1; i <= n; ++i) {
        for (int l = 1; l <= n - i + 1; ++l) {
            int r = l + i - 1;
            if (l > m || s[i] == t[l]) dp[l][r] = (dp[l][r] + dp[l + 1][r]) % mod;
            if (r > m || s[i] == t[r]) dp[l][r] = (dp[l][r] + dp[l][r - 1]) % mod;
        }
    }
    
    int ans = 0;
    for (int i = m; i <= n; ++i) {
        ans = (ans + dp[1][i]) % mod;
    }
    cout << ans << endl;
    return 0;
}