A 好字符串

知识点： 模拟 + 字符串

题目大意： 给我们一个长度为n的字符串s，需要保证字符串中每一个小写字母和他对应的大写字母都存在或者不存在s中。

解题思路：

枚举每一个字母，利用find函数在s中查找相应的位置。如果都没有找到或者都找的到就成立，否则就范围false。
或者我们可以先预处理计数一遍，在枚举每一个字母的出现情况，两种写法都是可以的。

代码实现：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < 26; i++) {
        int a = s.find(i + 'a');
        int b = s.find(i + 'A');
        // 两者不相等说明肯定不是都找不到的情况，在此基础上如果还存在一个找不到的就舍去。
        if (a != b && (a == -1 || b == -1)) {
            cout << "NO";
            return;
        }
    }
    cout << "YES";
    return;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //	cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B 平均数

知识点： 简单思维题

题目大意： 给我们一段数组，每一个位置上存在3种值：-1，0，1，表示小于，等于，大于当前数组的平均值，要求我们判断这个序列是否合法。

解题思路：

假设存在一组序列可以满足要求，我们对这个数组进行排序，此时平均值就存在这个数组的中间段，那么左边和右边都一定存在大于或者小于的。或者说就全部等于平均值。
所以本题的思路就出来了，如果数组中不存在-1和1或者都存在-1和1，那么就是符合条件的，否则就是不合法的。

代码实现：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'

void solve() {
    int n;
    cin >> n;
    vector<int> nums(n);
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        mp[nums[i]]++;
    }
    if (mp[-1] == 0 && mp[1] == 0) {
        cout << "YES";
    } else if (mp[-1] == 0 || mp[1] == 0) {
        cout << "NO";
    } else {
        cout << "YES";
    }
    return;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //	cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C 质数

知识点： gcd & 思维

题目大意： 给我们一段区间[l,r]，我们需要将这段区间的元素分为两组，其中一组的gcd等于，另一组的gcd不等于1，并且不可以存在空的情况。需要使得两组元素的个数接近。

解题思路：

要使得两组元素个数接近，我们很容易就想要对半分，那么我们应该如何对半分才可以保证都满足上面的性质呢？
我们列举出几个区间就很容易发现，偶数分一起，奇数分一起就是最好的，偶数在一起就可以保证gcd不唯一，我们就需要考虑奇数的情况了。
我们可以知道：gcd(x,x + a) = gcd(x,2)。所有相邻两个奇数gcd(x,x + 2) = gcd(x,2) = 1.所以我们就可以得到任意两个相邻的奇数gcd为1.
所以本题思路就出来了，就是奇数一起并且偶数一起，但是需要考虑的细节也很重要。如果没有两个奇数怎么办，这样就存在问题。
如果长度为1，那就一定不符合条件。如果长度为2，我们就需要判断左端点是否为1，其他情况都是不可以的。如果长度为3并且只有一个奇数，我们就可以放置相邻的两个元素到左边（保证gcd为1）。长度大于3就一定符合要求了。

代码实现：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'

void solve() {
    int l, r;
    cin >> l >> r;
    int len = r - l + 1;
    if (len == 1) {
        cout << -1 << endl;
    } else if (len == 2) {
        if (l == 1) {
            cout << 0 << endl;
        } else {
            cout << -1 << endl;
        }
    } else {
        cout << abs(len - len / 2 - len / 2) << endl;
    }
    return;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D 众数

知识点： 枚举 + 删除懒堆。

题目大意： 我们需要进行一次操作，找到i，j对（不可以相等），使得nums[i] + 1, nums[j] - 1，找到所有可能满足众数（出现次数最多，频率一样按照值的大的优先）。

解题思路：

本题n的范围比较小，只有1000，我们枚举出所有的数对i，j进行模拟判断就可以了。由于每次操作都是相互独立的，每次操作完之后又需要去还原之前的操作，这里我们可以用set实现（时间复杂度高，正常是会超时的，但是比赛的时候给的是2s，所有可以尝试）。也可以用删除懒堆去实现。
接下来的操作就是模拟了，代码中细节也是非常的多。

代码实现：

暴力set模拟

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
int cnt[1000005];
void solve() {
    int n;
    cin >> n;
    vector<int> nums(n);
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        mp[nums[i]]++;
        cnt[nums[i]]++;
    }
    set<pair<int, int>> s;
    for (auto& [x, y] : mp) {
        s.insert({y, x});
    }
    set<int> res;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int a = nums[i], b = nums[j];
            // 把原有的全部都删除。
            s.erase({cnt[a], a});
            s.erase({cnt[b], b});
            s.erase({cnt[a + 1], a + 1});
            s.erase({cnt[b - 1], b - 1});
            // 操作加减法。
            cnt[a]--;
            cnt[b]--;
            cnt[a + 1]++;
            cnt[b - 1]++;
            // 在加入set中去。
            s.insert({cnt[a], a});
            s.insert({cnt[b], b});
            s.insert({cnt[a + 1], a + 1});
            s.insert({cnt[b - 1], b - 1});
            // 找到次数出现次数最大的一个。
            res.insert(s.rbegin()->second);
            
            // 还原操作，删除增加后的变量。
            s.erase({cnt[a], a});
            s.erase({cnt[b], b});
            s.erase({cnt[a + 1], a + 1});
            s.erase({cnt[b - 1], b - 1});
            cnt[a]++;
            cnt[b]++;
            cnt[a + 1]--;
            cnt[b - 1]--;
            // 再加入一开始原始的。
            s.insert({cnt[a], a});
            s.insert({cnt[b], b});
            s.insert({cnt[a + 1], a + 1});
            s.insert({cnt[b - 1], b - 1});
        }
    }
    for (int i : res) {
        cout << i << " ";
    }
    return;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //	cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

删除懒堆

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
int cnt[1000005];
void solve() {
    int n;
    cin >> n;
    vector<int> nums(n);
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        mp[nums[i]]++;
        cnt[nums[i]]++;
    }
    // 预处理每一个元素的出现次数。
    priority_queue<pair<int, int>> q;
    for (auto& [x, y] : mp) {
        q.push({y, x});
    }
    set<int> s;
    for (int i = 0; i < n; i++) {
        int a = nums[i];
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            int b = nums[j];
            cnt[a]--;
            cnt[b]--;
            cnt[a + 1]++;
            cnt[b - 1]++;
            // 此时新添加的元素可能会影响到答案的变化，我们应该也加入到删除懒堆。
            q.push({cnt[a + 1], a + 1});
            q.push({cnt[b - 1], b - 1});
            while (q.size() && q.top().first != cnt[q.top().second]) {
                auto [x, y] = q.top();
                q.pop();
                q.push({cnt[y], y});
            }
            s.insert(q.top().second);
            cnt[a]++;
            cnt[b]++;
            cnt[a + 1]--;
            cnt[b - 1]--;
            // 但是之前原始的a和b可能会被删除，这里我们还需要重新加回来。
            // 比赛的时候这里没有注意到呀！，导致这题没有过，呜呜呜。
            q.push({cnt[a], a});
            q.push({cnt[b], b});
        }
    }
    for (int i : s) cout << i << " ";
    return;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //	cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E 种类数

知识点： 贪心 + 模拟

题目大意： 我们每次可以执行一次操作，将数组中所有元素都减去x（x为次数数组中的种类次数）。用最少的操作次数将数组中所有元素变为相等的。感觉这题的难度应该放在D题。

解题思路：

如果数组中所有元素都相等，那么我们就不需要考虑了。否则最终变为相等的元素一定是0.
我们就从小到大模拟这样的操作就可以了，我们记录次数的种类次数sum，以及产生的插值diff，每次操作最小的元素就优先变为0，一旦变为0此时数组中种类数减少1，0的个数增加1。就是模拟这种操作即可。
但是这题的细节还是比较多的，首先就是处理重复的情况，对于重复元素来说我们是不需要考虑两个元素的，并且种类数也只会计算一次。
其次就是0的情况，一旦一个元素变为0，那么0的种类数增加（前提是数组中一开始没有0），最多也只会增加一次，这里也需要我们特殊去判断）。

代码实现：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'

void solve() {
    int n;
    cin >> n;
    vector<int> nums(n);
    set<int> s;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        s.insert(nums[i]);
    }
    int t = s.size();
    if (t == 1) {
        cout << 0;
        return;
    }
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    int flag = 0;
    if (nums[0] == 0) flag = 1;
    int i = flag;
    int sum = t, res = 0;
    int diff = 0;
    while (i < n) {
        int x = nums[i++];
        int b = x;
        x = max(0LL, x - diff);
        int a = (x + sum - 1) / sum;
        res += a;
        diff += a * sum;
        // 只有数组中一开始存在0并且种类数大于2种类数才会变少。
        if (flag == 1 && sum > 2) sum -= 1;
        flag = 1;
    }
    cout << res;
    return;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    //	cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

题解 | A-E

A 好字符串

B 平均数

C 质数

D 众数

E 种类数