完整代码:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Good%20Bye%202021-2022%20is%20NEAR

A. Integer Diversity

在这里插入图片描述
题目大意:给你n个数,你可以选择任意某个数使其乘-1,问最多可以得到多少个不同的数
思路:用map记录每个数出现的次数,遍历map,如果某个数出现了2次以上且它乘-1没出现过,答案+2,否则答案+1
坑点:注意跳过it.second==0的情况

void work()
{
    cin >> n;
    map<int,int> M;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int temp;
        cin >> temp;
        M[temp]++;
    }
    for (auto it : M)
    {
        // cout << it.first << " " << it.second << endl;
        // if (it.second == 0)
        //     continue;
        if (it.second >= 2 && M[it.first * -1] == 0)
            ans += 2;
        else
            ans++;
    }
    cout << ans << endl;
}

B. Mirror in the String

在这里插入图片描述

题目大意:给你一个字符串s1s2s3s4...sn,你可以选择一个k构成一个新的字符串t:s1s2s3sk,求字典序就小的t
思路:我们发下新构造的字符串是一个回文串而且要求其字典序最小,试想一下如果s的第一个字符是a,那么k应该取多少?
实际上,我们要找的s1-sk应该必定是降序,否则字典序则不是最优
坑点:尝试算一下baa和bba的答案,发现需要特判首字母相等的情况
代码:

void work()
{
    string nowS;
    cin >> n >> nowS;
    int cnt = n - 1;
    for (int i = 0; i + 1 < n; i++)
        if (nowS[i] < nowS[i + 1] || (i == 0 && nowS[i] == nowS[i + 1]))
        {
            cnt = i;
            break;
        }
    string ans = nowS;
    ans = ans.substr(0, cnt + 1);
    reverse(ans.begin(), ans.end());
    ans = nowS.substr(0, cnt + 1) + ans;
    cout << ans << endl;
}

C. Representative Edges

在这里插入图片描述
题目大意:如果数组满足任意的1≤l≤r≤n,且 al+al+1+…+ar=12(al+ar)⋅(r−l+1),则称该数组为好数组,现在给你一个数组arr,你可以修改其中的任意一个数,问最小修改多少个数使其变成好数组

思路:我们发现题目所求的好数组,就是等差数列,如果一个数组等差数列,那么他必定是一个好数组,可以枚举所有可能的公差,记录每个公差可以对应的数的个数来得到最小答案

坑点:记得统计公差为0的情况

代码:

void work()
{
    cin >> n;
    map<int, int> M;
    vector<int> V(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> V[i], M[V[i]]++;
    int cnt = 1e9;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            double nowD = (V[j] - V[i]) * 1.0 / (j - i);
            int nowAns = n;
            for (int k = 1; k <= n; k++)
            {
                if (abs(V[k] - (V[i] + nowD * (k - i))) < 1e-2)
                    nowAns--;
                // cout << V[k] << " " << V[i]+nowD*(k-i) << " " << nowD << " " << nowAns << endl;
            }
            cnt = min(cnt, nowAns);
        }
    for (int i = 1; i <= n; i++)
        cnt = min(cnt,n-M[V[i]]);
    cout << cnt << endl;
}

D. Keep the Average High

在这里插入图片描述
题目大意:给你一个数组a,和一个数x,让你选择ans个元素,使得对于任意一个连续的、长度大于等于2的子段都满足
其中有一个元素没有被选择
子段和 >= x*子段长度
求的最大的x
思路:
先来翻译翻译题目,说人话就是对于每个连续的、长度大于等于2的子段,要么其中有一个元素没有选,要么它的平均数大于x
可以知道,如果小区间满足,则组成的大区间一定满足,所以我们可以只判断长度<=3的子段
使用dp[0][i] 表示从0-i选的数,此时第i个数没有选择
使用dp[1][i] 表示从0-i选的数,此时第i个数被选择
使用dp[2][i] 表示从0-i选的数,此时第i、i-1被选择
使用dp[3][i] 表示从0-i选的数,此时第i、i-1、i-2被选择
可以知道dp[0][i]可以从dp[0-3][i-1]得到,而且dp[1][i] = dp[0][i-1] + 1 (因为题目要求的子段长度大于如果a[i] + a[i-1] >= 2 * x
则 dp[2][i] = max(dp[0][i - 2] + 2, dp[1][i - 1] + 1),同理可以构造出长度为3的子段满足的转移方程,这里就不列举了,太难写了
代码:

void work()
{
    for (int i = 0; i <= 3; i++)
        dp[i].clear();
    cin >> n;
    vector<int> V(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> V[i];
    cin >> x;
    for (int i = 1; i <= n; i++)
    {
        dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
        dp[0][i] = max(dp[0][i], dp[2][i - 1]);
        dp[0][i] = max(dp[0][i], dp[3][i - 1]);
        dp[1][i] = dp[0][i - 1] + 1;
        if (i >= 2 && V[i] + V[i - 1] >= 2 * x)
            dp[2][i] = max(dp[0][i - 2] + 2, dp[1][i - 1] + 1);
        if (i >= 3 && (V[i] + V[i - 1] >= 2 * x) && (V[i - 1] + V[i - 2] >= 2 * x) && (V[i - 2] + V[i - 1] + V[i] >= 3 * x))
        {
            dp[3][i] = max(dp[2][i - 1] + 1, dp[1][i - 2] + 2);
            dp[3][i] = max(dp[3][i], dp[0][i - 3] + 3);
            dp[3][i] = max(dp[3][i], dp[3][i - 1] + 1);
        }
    }
    int ans = 0;
    ans = max(dp[0][n], dp[1][n]);
    ans = max(ans, dp[2][n]);
    ans = max(ans, dp[3][n]);
    cout << ans << endl;
}