AtCoder Beginner Contest 220

发表于2021-10-13更新于2023-09-15字数统计1.8k阅读时长18分

比赛链接

D FG operation

Description

题目链接

Solution

设 DPi,jDP_{i, j} 表示计算了前 i 个数，结果为 jj 的方案数，初始条件为 DP1,a[1]=1DP_{1, a[1]}=1，然后根据题意转移即可。

Code

FG operation
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;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5, MOD = 998244353;

#define int long long

int n;
int dp[MAXN][10];
int a[MAXN];

signed main() {
    boost;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    dp[1][a[1]] = 1;
    for (int i = 2; i <= n; i++) {
        for (int pre = 0; pre < 10; pre++) {
            (dp[i][pre * a[i] % 10] += dp[i - 1][pre]) %= MOD;
            (dp[i][(pre + a[i]) % 10] += dp[i - 1][pre]) %= MOD;
        }
    }
    for (int i = 0; i < 10; i++) cout << dp[n][i] << "\n";
    return 0;
}

E Distance on Large Perfect Binary Tree

Description

题目链接
统计满二叉树上距离为 D 的点对数。

Solution

按深度从小达到考虑 （深度范围为 [1, n])，为防止重复计算，只考虑经过选定点 vv ，且不经过其父亲节点的长度为 D 的路径（类似点分治路径统计）。

深度为 1≤i≤n1\le i\le n 的满二叉树节点数为 2i−12^{i - 1}。

对每个节点 vv，以 vv 为端点，且另一端在 vv 子树中的路径数为 2d2^d，所以计入答案的点对数为 2∗2d∗2i−1=2i+d2 * 2^d*2^{i-1}=2^{i+d}。

否则设路径的一段长度为 jj， 则另一端长度为 D−jD - j，需要满足 1≤j≤n−i1\le j\le n-i 且 1≤D−j≤n−i1\le D-j\le n-i，所以 l=max(1,D+i−n)≤j≤r=min(D−1,n−i)l = max(1, D + i - n) \le j \le r =min(D - 1, n - i)。对应的计入答案的点对数为 2∗max(0,r−l+1)∗2i−1∗2j−1∗2D−j−1=2∗max(0,r−l+1)∗2i−1∗2d−1。2 * max(0, r - l + 1) * 2^{i-1} * 2^{j-1} * 2^{D - j - 1}=2*max(0, r - l + 1) * 2^{i-1}*2^{d-1}。

Code

Distance on Large Perfect Binary Tree
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 boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5, MOD = 998244353;

#define int long long

int n, d, ans;

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

signed main() {
    boost;
    cin >> n >> d;
    for (int i = 1; i <= n; i++) {
        int num = qpow(2, i - 1);
        
        if (i + d <= n) {
            ans = (ans + qpow(2, i + d)) % MOD;
        }

        int high = min(d - 1, n - i), low = max(1LL, d + i - n);

        if (low > high) continue;
        ans = (ans + num * (high - low + 1) % MOD * qpow(2, d - 1) % MOD) % MOD;
    }
    cout << (ans % MOD) << "\n";
    return 0;
}

F Distance Sums 2

Description

题目链接

Solution

二次扫描与换根 DP 模板题。

首先选择一个节点为根节点进行树形 DP，设 dpidp_i 表示 节点i节点 i 到子树中所有节点的距离和，状态转移方程为 dpi=∑j∈Sonidp[j]+szj∗wi,jdp_i = \sum\limits_{j \in Son_i}dp[j]+sz_j*w_{i,j}。

dfs 换根时，设 fif_i 表示节点 ii 到其它所有节点的距离和。对于 j∈Sonij \in Son_i，fjf_j 分为两个部分，一个是到子树节点的距离和 dpjdp_j，另一个是经过 ej,ie_{j, i} 到其它节点的距离和。可以先从 fif_i 中减去 ii 到 jj 的子树节点的距离和，即fi−dpj−szj∗wf_i - dp_j - sz_j*w，在加上 ww 乘以其它节点的数目 n−szjn-sz_j 即为答案。最终结果为 fj=dpj+(fi−dpj−szj∗w)+(n−szj)∗wf_j = dp_j + (f_i-dp_j-sz_j*w) + (n - sz_j)*w。

时间复杂度 O(n)O(n)。

Code Distance Sums 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
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 2e5 + 5, MOD = 998244353;

int n;
long long d[MAXN], f[MAXN], sz[MAXN];
vector<int> g[MAXN];

void DP(int cur, int fa) {
    sz[cur] = 1;
    for (auto& to : g[cur]) {
        if (to == fa) continue;
        DP(to, cur);
        d[cur] += d[to] + sz[to];
        sz[cur] += sz[to];
    }
}

void dfs(int cur, int fa) {
    for (auto& to : g[cur]) {
        if (to == fa) continue;
        f[to] = d[to] + (f[cur] - d[to] - sz[to]) + (n - sz[to]);
        dfs(to, cur);
    }
}


signed main() {
    boost;
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    DP(1, 0);
    f[1] = d[1];
    dfs(1, 0);
    for (int i = 1; i <= n; i++) cout << f[i] << "\n";
    return 0;
}

G Isosceles Trapezium

Description

题目链接
给定平面上 4≤n≤10004\le n \le 1000 个点，每个点有一个点权，找出一个等腰梯形，使得点权和最大。

Solution

两条线段能构成等腰梯形当且仅当它们的中垂线相同，且延长后不重叠。

首先得出所有线段 （只考虑向一个方向连线），求出中点，两端点点权和，和对应的中垂线方程（可通过求出中垂线向量得到）。然后按照中垂线分类。

对于同一类中垂线，按中点分类，记录最大的端点点权和，排序后找到前 2 大的点权和即可。

为防止浮点误差，最好预先将坐标 * 2，并且用 ax+by+cax+by+c 的形式表示中垂线。此外 map 不是按照 value 排序的，求最大 value 不要用 map.rbegin()->second。

时间复杂度 O(N2logN2)O(N^2logN^2)。

Code Isosceles Trapezium

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

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

#define int long long

constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;

int n, ans(-1);
vector<tuple<int, int, int>> perpenb; // perpendicular bisectors
vector<map<pair<int, int>, int>> midpoints; // midpoints of a perpendicular bisector
vector<tuple<int, int, int>> p;

signed main() {
    boost;
    cin >> n;
    for (signed i = 0, x, y, c; i < n; i++) {
        cin >> x >> y >> c;
        p.emplace_back(x << 1, y << 1, c);
    }
    sort(p.begin(), p.end());
    for (signed i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int xi, yi, ci, xj, yj, cj;
            tie(xi, yi, ci) = p[i], tie(xj, yj, cj) = p[j];
            long long x1 = (xi + xj) >> 1, y1 = (yi + yj) >> 1;
            long long vecx = yi - yj, vecy = xj - xi;
            long long x2 = x1 + vecx, y2 = y1 + vecy;
            int a = y2 - y1, b = x1 - x2, c = x1 * y2 - x2 * y1;
            int gcd = __gcd(a, __gcd(b, c));
            a /= gcd, b /= gcd, c /= gcd;
            perpenb.emplace_back(a, b, c);
        }
    sort(perpenb.begin(), perpenb.end());
    int cnt = unique(perpenb.begin(), perpenb.end()) - perpenb.begin();
    midpoints.resize(cnt);

    for (signed i = 0; i < n; i++)
        for (signed j = i + 1; j < n; j++) {
            int xi, yi, ci, xj, yj, cj;
            tie(xi, yi, ci) = p[i], tie(xj, yj, cj) = p[j];
            long long x1 = (xi + xj) >> 1, y1 = (yi + yj) >> 1;
            long long vecx = yi - yj, vecy = xj - xi;
            long long x2 = x1 + vecx, y2 = y1 + vecy;
            int a = y2 - y1, b = x1 - x2, c = x1 * y2 - x2 * y1;
            int gcd = __gcd(a, __gcd(b, c));
            a /= gcd, b /= gcd, c /= gcd;
            int pos = lower_bound(perpenb.begin(), perpenb.begin() + cnt, make_tuple(a, b, c)) - perpenb.begin();
            int tmp = midpoints[pos][{x1, y1}];
            midpoints[pos][{x1, y1}] = max(tmp, ci + cj);
        }
    for (auto& mp : midpoints) {
        if (mp.size() < 2) continue;
        vector<int> cs;
        for (auto& i : mp) cs.push_back(i.second);
        sort(cs.begin(), cs.end());
        ans = max(ans, cs[cs.size() - 1] + cs[cs.size() - 2]);
    }
    cout << ans << "\n";
    return 0;
}