Codeforces1003(Div4 A-F)

TwindT Ranking++
  2025-02-10 21:25:11 2025-02-10 21:25:11 创建   2025-02-17 11:07:30 2025-02-17 11:07:30 更新      

A. Skibidus and Amog’u

题目链接:https://codeforces.com/contest/2065/problem/A

没有什么特别的,根据题目直接模拟即可

1
2
3
4
5
6
7
8
void solve() {
    string s;
    cin >> s;

    int len = s.length();
    for (int i = 0;i < len - 2;i++) cout << s[i];
    cout << "i" << '\n';
}

B. Skibidus and Ohio

题目链接:https://codeforces.com/contest/2065/problem/B

我们发现如果至少存在一组使得 s[i] == s[i + 1] 那么我们就可以一直操作直到剩最后一个字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    string s;
    cin >> s;

    int len = s.length();
    for (int i = 0;i < len - 1;i++) {
        if (s[i] == s[i + 1]) {
            cout << 1 << '\n';
            return;
        }
    }

    cout << len << '\n';
}

C. Skibidus and Fanum Tax (C1,C2)

题目链接:https://codeforces.com/contest/2065/problem/C2

由于对每个 a[i] 都可以独立地使用任意一个 b[j] (且可以重复使用),因此对于每个 i,如果我们选择操作,

实际上可以得到任意形如 b − a[i] 的数，其中 b 来自数组 b;

而我们的目标是 “给后面的数留出空间”;因此在满足”至少不比前一个数小”的前提下，越小越好.

一种自然的思路是动态规划:

  • 1.不操作: 若 a[i] >= dp[i - 1], 则可以令 dp[i] = a[i].

  • 2.操作: 如果存在某个b使得操作后的值满足b >= dp[i - 1] + a[i]那么我们可以从数组 b 中选择满足条件的最小值b(我们记为b*), 这样得到的操作结果是 dp[i] = b*-a[i].

最终, 若对某个位置 i 上, 两种选择都不满足条件 (即都无法使 v[i] >= dp[i - 1]),

则说明无法构造出一个非递减序列;

否则, 最后存在一种方案使得整个序列非递减.

对于操作选项, 我们需要找到满足 b >= dp[i - 1] + a[i] 的最小的 b ,

因此我们可以先对数组 b 排序, 再用二分查找来寻找下界.

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
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= m;i++) cin >> b[i];
    sort(b.begin(), b.end());

    int dp = -INF;
    for (int i = 1;i <= n;i++) {
        int sen = INF;
        
        if (a[i] >= dp) sen = a[i];

        int mid = dp + a[i];
        auto pos = lower_bound(b.begin() + 1, b.end(), mid);
        if (pos != b.end()) sen = min(sen, *pos - a[i]);

        if (sen == INF) {
            cout << "NO\n";
            return;
        }

        dp = sen;
    }

    cout << "YES\n";
}

D. Skibidus and Sigma

题目链接:https://codeforces.com/contest/2065/problem/D

由题目所得, 分数的构成是由前缀和来决定, 所以贪心的想法就是把前缀和大的数组放在前面,这样我们就能最大化分数.

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
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n + 1, vector<int> (m + 1));

    vector<PII> sen;
    for (int i = 1;i <= n;i++) {
        ll sum = 0;
        for (int j = 1;j <= m;j++) {
            cin >> v[i][j];
            sum += v[i][j];
        }

        sen.push_back({sum, i});
    }

    sort(sen.begin(), sen.end(), greater<PII> ());

    ll ans = 0;
    ll cnt = 0;
    for (auto [sum, pos] : sen) {
        for(int j = 1;j <= m;j++) {
            cnt += v[pos][j];
            ans += cnt;
        }
    }

    cout << ans << '\n';    
}

E. Skibidus and Rizz

题目链接:https://codeforces.com/contest/2065/problem/E

根据题目, 我们需要关注几个点:

  • 首先如果 abs(n - m) > k 则无解

  • 其次我们判断 n 和 m 的大小分开处理

  • 然后我们在判断个数更大的数与k的关系 如果小于 k 则无解

现在我们假设 n > m:

我们可以先输出 k 个0, 再输出 k - (n - m) 个 1 这样操作后 0 和 1 的剩余个数就会一样;

从前面我们知道 abs(n - m) <= k 那么如果 n - m < k 我们就可以直接 101010 这样交替构造;

如果 n - m == k 则 此时只能 010101 这样构造

反之如果 n < m 同理

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
void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    if (abs(n - m) > k) {
        cout << -1 << '\n';
        return;
    }

    auto f = [&] (char tar, int num1, int num2) -> string {
        string s = "";
        for (int i = 0;i < k;i++) s.push_back(tar);

        char sen = (tar == '1' ? '0' : '1');

        for (int i = 0;i < k - (num1 - num2);i++) s.push_back(sen);

        int len = num1 - k;
        if (num1 - num2 < k) {
            for (int i = 0;i < len;i++) {
                s.push_back(tar);
                s.push_back(sen);
            }
        } else {
            for (int i = 0;i < len;i++) {
                s.push_back(sen);
                s.push_back(tar);
            }
        }

        return s;
    };

    if (n >= m) {
        if (n < k) {
            cout << -1 << '\n';
            return;
        }

        string ans = f('0', n, m);
        cout << ans << '\n';
    } else {
        if (m < k) {
            cout << -1 << '\n';
            return;
        }

        string ans = f('1', m, n);
        cout << ans << '\n';
    }
}

F. Skibidus and Slay

题目链接:https://codeforces.com/contest/2065/problem/F

首先以一个点为中心向四周扩散这种也符合题目要求的简单路径;

假设某条边所连两个点对应值相等,此时为满足条件的最短的路径;

如果并不相等那么我们可以依次判断每个点的所有连边, 例如此时顶点为3(值与后边不同)和他所连的两个点为1, 2值均为5

此时 1 <- 3 -> 2 是满足条件的 我们可以记录对应值出现的个数, 如果个数大于1则满足条件

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
void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) cin >> a[i];

    vector<vector<int>> edge(n + 1, vector<int> ());
    vector<int> ans(n + 1);
    for (int i = 0;i < n - 1;i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);

        if (a[u] == a[v]) ans[a[u]] = 1;
    } 

    for (int i = 1;i <= n;i++) {
        map<int, int> mp;
        for (auto c : edge[i]) mp[a[c]]++;

        for (auto [c, v] : mp) {
            if (v > 1) ans[c] = 1;
        }
    }
    
    for (int i = 1;i <= n;i++) cout << ans[i];
    cout << '\n';
}

G. Skibidus and Capping

题目链接:https://codeforces.com/contest/2065/problem/G

数论题不做啦

目录
Codeforces1003(Div4 A-F)
  1. A. Skibidus and Amog’u
  2. B. Skibidus and Ohio
  3. C. Skibidus and Fanum Tax (C1,C2)
  4. D. Skibidus and Sigma
  5. E. Skibidus and Rizz
  6. F. Skibidus and Slay
  7. G. Skibidus and Capping