第 396 场周赛

又到了周赛时间，来玩玩了

A

好妙的题解，见题解第一篇，直接用数组来弄确实帅气

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isValid(string word) {
        if (word.length() < 3) {
            return false;
        }
        bool f[2]{};
        for (char c : word) {
            if (isalpha(c)) {
                c = tolower(c);
                f[c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'] = true;
            } else if (!isdigit(c)) {
                return false;
            }
        }
        return f[0] && f[1];
    }
};

B

非常合理的哈希做法，就是这样做的啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:

    int minimumOperationsToMakeKPeriodic(string word, int k) {
        unordered_map<string,int> m;
        int n=word.length();
        //每k个字符分成一段，统计各段字符串出现的次数
        for(int i=0;i<n;i+=k){
            string tmp=word.substr(i,k);
            m[tmp]++;
        }
        //让其中出现次数最多的字符串不变，其余的都变成该字符串
        auto x=max_element(m.begin(),m.end(),[](const pair<string,int>& a,const pair<string,int>& b){
            return a.second<b.second;
        });

        return n/k - x->second;
    }
};

C

同位字符串组成，今天是字符串场啊

s也并不大，t必须是s的因数，感觉还是可以暴力(bushi)

也是很水的一道题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minAnagramLength(string s) {
        int n = s.size();
        int cnt[26] = {0};
        for (char c : s) cnt[c - 'a']++;

        auto check = [&](int len) {
            for (int i = 0; i < n; i += len) {
                int tmp[26] = {0};
                for (int j = 0; j < len; j++) tmp[s[i + j] - 'a']++;
                for (int j = 0; j < 26; j++) if (tmp[j] * (n / len) != cnt[j]) return false;
            }
            return true;
        };

        for (int i = 1; i <= n; i++) 
            if (n % i == 0 && check(i)) return i;
        return -1;
    }
};

D

毫无疑问是要变成不一样最大的数字的，或者比最大的数字还要大

前面的一些特判和差值比较容易想，主要是枚举上界和两种情况的讨论比较复杂

image-20240506164431287 
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
class Solution {
public:
    int minCostToEqualizeArray(vector<int>& nums, int cost1, int cost2) {
        int n = nums.size();
        int lim = 0;
        for (int x : nums) lim = max(lim, x);

        long long sm = 0;
        int mx = 0;
        for (int x : nums) {
            int det = lim - x;
            sm += det;
            mx = max(mx, det);
        }

        const int MOD = 1e9 + 7;
        // 排除特殊情况
        if (nums.size() <= 2 || cost1 * 2 <= cost2) return sm * cost1 % MOD;

        long long ans = 1e18;
        for (int i = lim; i <= lim * 2; i++) {
            long long tmp;
            if (mx > sm - mx) 
            {
                tmp = (sm - mx) * cost2;
                long long rem = mx - (sm - mx);
                tmp += rem * cost1;
            } else 
            {
                tmp = sm / 2 * cost2;
                if (sm & 1) tmp += cost1;
            }
            ans = min(ans, tmp);
            sm += n;
            mx++;
        }
        return ans % MOD;
    }
};