发表更新算法8 分钟读完 (大约1135个字)

Codeforces Round 870 (Div. 2)【A - E】

只有 B 题非常顺利地做出来了……

比赛链接：https://codeforces.com/contest/1826

A. Trust Nobody

题解

排序后枚举说谎的人数 liarsliars ，若存在一种合法情况，那么 a[n−1−liars]a[n - 1 - liars] 及之前的数一定都小于等于 liarsliars ， a[n−liars]a[n - liars] 及之后的数一定都大于 liarsliars 。

代码

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

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    if (count(a.begin(), a.end(), 0) == n) {
        cout << 0 << "\n";
        return;
    }

    for (int liars = 1; liars < n; liars++) {
        if (a[n - 1 - liars] <= liars and a[n - liars] > liars) {
            cout << liars << "\n";
            return;
        }
    }

    cout << -1 << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

B. Lunatic Never Content

题解

贪心，对每一对对称的数 (a,b)(a, b) ，对 abs(a−b)abs(a - b) 取模后得到的数相等，对所有数则对所有的差取 gcdgcd 。

代码

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

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int g = 0;
    for (int i = 0; i < n / 2; i++) {
        g = gcd(g, abs(a[i] - a[n - 1 - i]));
    }
    cout << g << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

C. Dreaming of Freedom

题解

若 nn 的最小非 11 因子 pminp_{min} 小于等于 mm ，则可以每次都分这么多堆，否则每次分都会令 mm 的值减小，最后为 11 。

证明：当 m≠1m \ne 1 时，若分 pminp_{min} 堆不会令 mm 减少，则 pmin % m=0p_{min}\ \%\ m = 0 ，即 pminp_{min} 为 mm 的倍数，与 pminp_{min} 为 nn 的最小因子矛盾，不成立。

代码

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

constexpr int N = 1e6 + 10;

vector<int> minp(N), primes;

void Init() {
    for (int i = 2; i < N; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto x : primes) {
            if (i * x < N) {
                minp[i * x] = x;
            } else {
                break;
            }
            if (x == minp[i]) {
                break;
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    if (n == 1) {
        cout << "YES" << "\n";
        return;
    }

    cout << (minp[n] <= m ? "NO" : "YES") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Init();

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

D. Running Miles

题解

observation：左右端点一定都为最大值，否则可以缩短区间来增大答案。

所以原式为： bl+bm+br−(r−l)b_l + b_m + b_r - (r - l)

=(bl+l)+bm+(br−r)= (b_l + l) + b_m + (b_r - r)

即枚举中间值，取 bi+ib_i + i 的最大前缀和 br−rb_r - r 的最大后缀即可。

代码

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

void solve() {
    int n;
    cin >> n;

    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    vector<int> pre(n + 1, INT_MIN);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = max(pre[i], b[i] + i);
    }

    vector<int> suf(n + 1, INT_MIN);
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = max(suf[i + 1], b[i] - i);
    }

    int ans = INT_MIN;
    for (int i = 1; i + 1 < n; i++) {
        ans = max(ans, b[i] + pre[i] + suf[i + 1]);
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

E. Walk the Runway

题解

计算每两个人的前后关系（即如果第 jj 个人能在第 ii 个人之后，在所有 mm 个数组中都有 rki<rkjr_{ki} \lt r_{kj} ）后得到一张有向图，对该图用拓扑排序或记忆化搜索来进行 dpdp 。

直接计算的话时间复杂度为 O(n3m)O(n^3m) ，对每个数组排序后用双指针和 bitset 进行优化，时间复杂度为 O(n2m64)O{(\frac{n^2m}{64})} 。

代码

拓扑排序：

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    cin >> m >> n;

    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    vector edge(5001, bitset<5001>(string(5001, '1')));

    for (int i = 0; i < m; i++) {
        vector<array<int, 2>> r(n);
        for (int j = 0; j < n; j++) {
            cin >> r[j][0];
            r[j][1] = j;
        }
        sort(r.begin(), r.end());

        bitset<5001> to(string(5001, '1'));

        for (int j = 0; j < n; ) {
            to[r[j][1]] = 0;
            int k = j + 1;
            while (k < n and r[k][0] == r[j][0]) {
                to[r[k][1]] = 0;
                k += 1;
            }
            while (j < k) {
                edge[r[j][1]] &= to;
                j += 1;
            }
        }
    }

    vector G(n, vector<int>());
    vector<int> deg(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (edge[i][j]) {
                G[i].push_back(j);
                deg[j]++;
            }
        }
    }

    queue<int> que;
    vector<long long> dp(n);

    for (int i = 0; i < n; i++) {
        if (deg[i] == 0) {
            que.push(i);
            dp[i] = p[i];
        }
    }
    while (not que.empty()) {
        int u = que.front();
        que.pop();

        for (auto v : G[u]) {
            dp[v] = max(dp[v], dp[u]);
            if (--deg[v] == 0) {
                que.push(v);
                dp[v] += p[v];
            }
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << "\n";

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    cin >> m >> n;

    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    vector edge(5001, bitset<5001>(string(5001, '1')));

    for (int i = 0; i < m; i++) {
        vector<array<int, 2>> r(n);
        for (int j = 0; j < n; j++) {
            cin >> r[j][0];
            r[j][1] = j;
        }
        sort(r.begin(), r.end());

        bitset<5001> to(string(5001, '1'));

        for (int j = 0; j < n; ) {
            to[r[j][1]] = 0;
            int k = j + 1;
            while (k < n and r[k][0] == r[j][0]) {
                to[r[k][1]] = 0;
                k += 1;
            }
            while (j < k) {
                edge[r[j][1]] &= to;
                j += 1;
            }
        }
    }

    long long ans = 0;
    vector<long long> dp(n);
    function<long long(int)> dfs = [&](int u) {
        if (dp[u]) {
            return dp[u];
        }
        long long res = 0;
        for (int v = 0; v < n; v++) {
            if (edge[u][v]) {
                res = max(res, dfs(v));
            }
        }
        return dp[u] = res + p[u];
    };
    for (int i = 0; i < n; i++) {
        ans = max(ans, dfs(i));
    }
    cout << ans << "\n";

    return 0;
}

Codeforces Round 870 (Div. 2)【A - E】

https://www.kanoon.cn/2023/05/07/CF-1826/

作者

Kanoon

发布于

2023-05-07

更新于

2023-05-07

许可协议

#

评论

最新文章

分类

×