【Codeforces】Codeforces Round #53

Problem A

枚举每一个可能的t，然后验证取最小值即可。

时间复杂度为

#include <cstdio>
#include <algorithm>

using namespace std;

int a[1005];

int Caclu(int t, int n)
{
    int ret = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] == t)continue;
        if(a[i] > t)
        {
            ret += (a[i] - t - 1);
        }
        else
        {
            ret += (t - a[i] - 1);
        }
    }
    return ret;
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        int t = 1;
        int ans = Caclu(1, n);
        for(int i = 2; i <= 100; i++)
        {
            int pans = Caclu(i, n);
            if(ans > pans)
            {
                t = i;
                ans = pans;
            }
        }
        printf("%d %d\n", t, ans);
    }
    return 0;
}

Problem B

枚举所有可能的字母，对于每种字母遍历一遍字符串统计即可。

时间复杂度为

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int Check(string &s, int n, int k, char c)
{
    int ret = 0;
    int pLen = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == c)
        {
            pLen++;
            if(pLen == k)
            {
                pLen = 0;
                ret++;
            }
        }
        else
        {
            pLen = 0;
        }
    }
    return ret;
}

int main()
{
    string s;
    int n, k;
    while(cin >> n >> k)
    {
        cin >> s;
        int ans = 0;
        for(int i = 0; i < 26; i++)
        {
            char c = 'a' + i;
            ans = max(ans, Check(s, n ,k ,c));
        }
        cout << ans << endl;
    }
    return 0;
}

Problem C

设为数组长度为且数组和对3取模后为，为区间中对3取模后为的数的个数。则有：

答案为

时间复杂度为

#include <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 200000;

const LL mod = 1e9+7;

LL dp[MAXN + 5][4];

LL getAns(int n, int l, int r)
{
    int cnt[4] = {0};
    if(r - l < 10)
    {
        for(int i = l; i <= r; i++)
        {
            cnt[i % 3]++;
        }
    }
    else
    {
        while(l % 3 != 0)
        {
            cnt[l % 3]++;
            l++;
        }
        while(r % 3 != 2)
        {
            cnt[r % 3]++;
            r--;
        }
        cnt[0] += (r - l + 1) / 3;
        cnt[1] += (r - l + 1) / 3;
        cnt[2] += (r - l + 1) / 3;
    }
    dp[0][0] = 1;
    dp[0][1] = 0;
    dp[0][2] = 0;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            dp[i][j] = 0;
            for(int k = 0; k < 3; k++)
            {
                dp[i][j] += dp[i-1][(j - k + 3) % 3] * cnt[k];
                dp[i][j] %= mod;
            }
        }
    }
    return dp[n][0];
}

int main()
{
    int n, l, r;
    while(cin >> n >> l >> r)
    {
        cout << getAns(n, l, r) << endl;
    }
    return 0;
}

后续待补充