第135场双周赛

A

image-20240721134504554

很简单的一个模拟题

1
2
3
4
5
6
7
class Solution {
public:
    string losingPlayer(int x, int y) {
        int max_ = min(x, y / 4);
        return max_ & 1 ? "Alice" : "Bob";
    }
};

B

image-20240721135024204

根据字母独立进行讨论

如果小于3显然一个都删除不了

如果大于或等于3要讨论奇偶：

  • 奇数的话就可以剩下1个
  • 偶数一定会剩下两个。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minimumLength(string s) {
        int cnt[26] = {0}, res = 0;
        for (char c : s)
            ++cnt[c - 'a'];
        for (int x : cnt)
            res += (x >= 3 ? 2 - (x & 1) : x);
        return res;
    }
};

C

image-20240721140200786

很自然的想法就是直接计算每个差值出现了多少次，然后思考一下改成这个差值需要改多少次，有些数对需要改1次，有些数对则是一个数不够需要改两个数字。注意改两个数字那里可以做个前缀和，因为假如说改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
const int N = 1e5+100;
class Solution {
int cnt[N];
int sum[N];
public:
    int minChanges(vector<int>& a, int k) {
        int n = a.size();
        for (int i = 0;i <= n / 2 - 1;i ++) {
            int o = a[n - i - 1];
            int c = a[i];
            int r = abs(o - c);
            cnt[r] ++;
            int ans= max(max(o,c),k-min(o,c));
            sum[ans] ++;
        }
        for (int i = 1;i <= k;i ++)
        {
           sum[i] += sum[i - 1];  
        }
        int res =1e9;
        for (int i = 0;i <= k;i ++)
        {
            int tmp = cnt[i];
            int x = n / 2 - tmp; 
           res = min (res,x + sum[i - 1]);
        }
        return res;
    }
};