Codeforces Round 780 (Div. 3)

发表于 更新于 分类于 阅读次数： 本文字数： 271 阅读时长 ≈ 1 分钟
Do something today that your future self will thank you for.

A. Vasya and Coins

思路：

  • 找 \(1\) 到 \(a+b \times 2 + 1\)​ 中第一个没有出现过的数字即可

时间复杂度：\(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
void solve() {
    int a, b;
    std::cin >> a >> b;

    if (a == 0) {
        std::cout << 1 << "\n";
        return ;
    }

    std::cout << a + b * 2 + 1 << "\n";
}

B. Vlad and Candies

思路：

  • 只要最大值和次大值之间的差大于2，那么一定不行，为1就特判一下

时间复杂度：\(O(nlogn)\)

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
void solve() {
    int n;
    std::cin >> n;

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

    if (n == 1) {
        if (a[0] > 1) {
            std::cout << "NO\n";
        } else {
            std::cout << "YES\n";
        }
        return ;
    }

    std:sort(a.begin(), a.end());

    if (a[n - 1] - a[n - 2] > 1) {
        std::cout << "NO\n";
    } else {
        std::cout << "YES\n";
    }
}

C. Get an Even String

思路：

  • \(dp_{i,0}\)​ 表示

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    std::string s;
    std::cin >> s;

    int n = s.size();

    std::vector dp(n + 1, std::vector<int>(2, -1));
    dp[0][0] = 0;
    int pre = 0, ans = 0;
    std::map<char, int> mp;
    for (int i = 0; i < n; i++) {
        dp[i + 1][1] = pre + 1;
        if (mp.count(s[i])) {
            dp[i + 1][0] = dp[mp[s[i]]][1] + 1;
            pre = std::max(pre, dp[i + 1][0]);
            ans = std::max(ans, dp[i + 1][0]);
        }
        mp[s[i]] = i + 1;
    }
    std::cout << n - ans << "\n";
}