Martian148's blog
martian148
2024-10-25
目录

Sakura Tears training 5

# A - A Wide, Wide Graph

CF1085D A Wide, Wide Graph (opens new window)

# Question

给定一颗 nn 个顶点的树，给定一个固定的整数 kk，定义图 GkG_k 为 nn 个顶点的图，u,vu,v 之间存在连边当且仅当在树上的距离 ≥k\ge k ，对于每个 kk 从 11 到 nn，求图 GkG_k 中的 连通分量树

# Solution

如果设树的直径为 dd ，如果 d>kd>k ，那么图肯定是 nn 个孤立的点

否则直径的端点肯定在一个连通块上的

定义树上节点 xx 到最远的树的端点距离为 dis[x]dis[x] 如果 dis[x]>kdis[x]>k 那么 xx 也和两端在同一个连通块里面的

由于 kk 递增，所以可以 O(n)O(n) 求答案

# Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    function<void(int, int, vector<int>&)> dfs = [&](int u, int f, vector<int> &d) {
        d[u] = d[f] + 1;
        for (int v : g[u]) if (v != f) dfs(v, u, d);
    };

    vector<int> d(n + 1, 0), d1(n + 1, 0), d2(n + 1, 0);
    dfs(1, 0, d);
    int u = max_element(d.begin() + 1, d.end()) - (d.begin() + 1) + 1;
    dfs(u, 0, d1);
    int v = max_element(d1.begin() + 1, d1.end()) - (d1.begin() + 1) + 1;
    dfs(v, 0, d2);
    for (int i = 1; i <= n; i++) d[i] = max(d1[i], d2[i]);
    int mxd = d1[v];
    sort(d.begin() + 1, d.end());
    int pos = 1;
    for (int i = 1; i <= n; i++) {
        if (i >= mxd) cout << n << ' ';
        else {
            while (pos <= n && d[pos] <= i) pos += 1;
            cout << pos << ' ';
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    while (T--) solve();
    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

# B - Not Adding

# Question

CF1627D Not Adding (opens new window)

# Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int m = *max_element(a.begin() + 1, a.end());
    vector<int> cnt(m + 1, 0);
    for (auto x : a) cnt[x]++;
    int num = 0;
    for (int i = m; i >= 1; i--) {
        int g = 0;
        for (int j = i; j <= m; j += i) {
            if (cnt[j])
                g = __gcd(g, j);
        }
        if (g == i) {
            if (cnt[i] == 0) {
                num += 1;
                cnt[i] = 1;
            }
        }
    }
    cout << num << endl;
    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

# C - String Deletion

# Question

CF1430D String Deletion (opens new window)

你有一个由 nn 个字符组成的 01 字符串 ss

你可以对字符串进行操作，每个操作包括两个步骤：

  1. 选择一个整数 ii ，然后删除字符sis_i
  2. 如果字符串ss不为空，删除由相同字符组成的最大长度前缀

当字符串 ss 变为空时，结束操作。你能执行的最大操作次数是多少？

# Solution

贪心，显然，要删除长度 >1>1 的连续字符中的其中 11 个

我们从前往后看，如果有 >1>1 的，就操作它，直到它被操作 22 删去或者长度 =1=1

具体实现可以用双指针或者堆来实现

# Code

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        char ch; cin >> ch;
        a[i] = ch - '0';
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    int cnt_1 = 0;
    for (int i = 1; i <= n;) {
        int j = i;
        while (j <= n && a[j] == a[i]) j++;
        if (j - i > 1) pq.push({i, j - i});
        i = j;
    }
    int ans = 0, pos = 1;
    

    while (pos <= n) {

        auto get_pair = [&] () {
            while (!pq.empty() && pq.top().first < pos) pq.pop();
            if (pq.empty()) return pii(-1, -1);
            return pq.top();
        };

        auto [id, len] = get_pair();
        if (id == -1) {
            int ans2 = 0;
            for (int i = pos; i <= n; i) {
                int j = i;
                while (j <= n && a[j] == a[i]) j++;
                ans2 += 1;
                i = j;
            }
            cout << ans + (ans2 + 1) / 2 << '\n';
            return ;
        }
        else {
            int j = pos;
            while (j <= n && a[j] == a[pos]) j++;
            pos = j;
            ans += 1;
            pq.pop();
            if (len - 1 > 1) pq.push({id, len - 1});
        }
    }
    cout << ans << '\n';
}

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    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

# D - Another Array Problem

# Question

CF1763C Another Array Problem (opens new window)

给定一个数组 aa，可以进行无数次操作：

  • 选择 i,j,i<ji,j,i<j，用 ∣ai−aj∣|a_i-a_j| 替换所有 i≤k≤ji\le k\le j 的所有 aka_k

求最后 aa 的和的最大值

# Solution

一股 CFCF 的味道的题

考虑到如果操作两次相同的 i,ji,j 中间的数会变成 00

也就说，n>4n>4 的时候，可以全部变成序列中的最大的数

然后考虑 n=3n=3

  • 可以全部变成 a1,a3,∣a2−a1∣,∣a3−a2∣a_1,a_3,|a_2-a_1|,|a_3-a_2|
  • 或者不操作

# Code

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 2) {
        cout << max({2 * abs(a[1] - a[2]), a[1] + a[2]}) << '\n';
        return ;
    }
    if (n == 3) {
        cout << max({3 * a[1], 3 * a[3], 3 * abs(a[1] - a[2]), 3 * abs(a[2] - a[3]), a[1] + a[2] + a[3]}) << '\n';
    }
    else 
        cout << n * (*max_element(a.begin() + 1, a.end())) << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    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

# E - XOR-gun

# Question

CF1415D XOR-gun (opens new window)

# Solution

诈骗题的味道

考虑到如果三个数的最高位都一样，那么把后两个数异或起来肯定小于第三个

所以 n>60n>60 时，答案肯定时 11

对于小于 6060 的部分，O(n3)O(n^3) 的暴力即可

# Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
    freopen ("E.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    if (n > 60) {
        cout << "1\n";
        return 0;
    }
    vector<int> a(n + 1), sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] ^ a[i];
    }
    int ans = INF;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            for (int k = j; k <= n; k++) {
                if ((sum[i - 1] ^ sum[j - 1]) > (sum[j - 1] ^ sum[k])) {
                    ans = min(ans, k - i - 1);
                }
            }
        }
    }
    if (ans == INF) cout << "-1\n";
    else cout << ans << '\n';
}
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

# F - Restorer Distance

# Quesiton

CF1355E Restorer Distance (opens new window)

# Solution

显然，M=min⁡(M,A+R)M=\min(M,A+R)

然后发现答案是可三分的

# Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    freopen ("F.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N, A, R ,M; cin >> N >> A >> R >> M;
    vector<int> h(N + 1);
    for (int i = 1; i <= N; i++) cin >> h[i];
    M = min(M, A + R);
    
    auto check = [&] (int mid) -> ll{
        ll sum1 = 0, sum2 = 0;
        for (int i = 1; i <= N; i++) {
            if (h[i] < mid) sum1 += mid - h[i];
            else sum2 += h[i] - mid;
        }
        ll sum = min(sum1, sum2);
        sum1 -= sum; sum2 -= sum;
        return sum1 * A + sum2 * R + sum * M;
    };

    int l = 0, r = 1e9;
    while (l < r) {
        int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        if (check(lmid) < check(rmid)) r = rmid - 1;
        else l = lmid + 1;
    }
    cout << check(l) << '\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

# G - Earn or Unlock

# Question

CF1854B Earn or Unlock (opens new window)

安德烈正在玩游戏 Tanto Cuore。

他有一副 nn 张牌，从顶部到底部的值分别为 a1,…,ana_1, \ldots, a_n 。每张牌可以是锁定的或未锁定的。初始时，只有最顶部的牌是未锁定的。

游戏进行按回合进行。每回合，安德烈选择一张未锁定的牌 — 牌上写着的值为 vv — 并执行以下两种操作中的一种：

  1. 解锁牌堆顶的前 vv 张锁定牌。如果牌堆中锁定的牌少于 vv 张，则解锁全部锁定的牌。
  2. 赚取 vv 点胜利点数。

在执行完操作后，无论哪种情况，他都要从牌堆中移除这张牌。

游戏在牌堆中剩余的所有牌都被锁定时结束，或者牌堆中没有更多的牌时结束。

安德烈可以获得的最大胜利点数是多少？

# Solution

我们发现了一个事实，如果我选了前 xx 张牌，那么有等式 s+x−1=∑i=1xais+x-1=\sum_{i=1}^x a_i

变换一下得到 s=∑i=1xai−x+1s=\sum_{i=1}^x a_i-x+1

所以就转化成了一个类似于前缀和的式子

然后就看能不能走到 xx，很显然有 01 背包，定义 dp[i[j]dp[i[j] 表示前 ii 个 a[i]a[i] 是否能到达 jj

dp[i][j]∨=dp[i−1][j<<a[i]] dp[i][j]\vee =dp[i-1][j<<a[i]]

位运算可以用 bitset 优化，ii 又只和 i−1i-1 有关，所以可以用滚动数组优化

在使用完 dp[i]dp[i] 后，应该把 dp[i][i]dp[i][i] 置为 00，因为对于前 ii 个来说，第 ii 个卡牌必须用作赚取点数

# Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    freopen ("G.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<ll> a(2 * n + 1, 0), sum(2 * n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + a[i];
    bitset<200005> dp;
    dp[1] = 1;
    ll ans = 0;
    for (int i = 1; i <= 2 * n; i++) {
        dp |= dp << a[i];
        if (dp[i]) {
            ans = max(ans, sum[i] - i + 1);
            dp[i] = 0;
        }
    }
    cout << ans << '\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
上次更新: 2024/10/30, 18:42:16
Sakura Tears training 4
2024牛客暑期多校5

← 2024牛客暑期多校5→

最近更新
01
逻辑学
12-13
02
中华传统文化
12-12
03
欧拉回路
11-14
更多文章>
Theme by Vdoing | Copyright © 2024-2024 Martian148 | MIT License