Problem A
枚舉每一個(gè)可能的t宿崭，然后驗(yàn)證取最小值即可。
時(shí)間復(fù)雜度為
#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
枚舉所有可能的字母嚷兔，對(duì)于每種字母遍歷一遍字符串統(tǒng)計(jì)即可垃你。
時(shí)間復(fù)雜度為
#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
設(shè)為數(shù)組長(zhǎng)度為
且數(shù)組和對(duì)3取模后為
，
為區(qū)間
中對(duì)3取模后為
的數(shù)的個(gè)數(shù)缭嫡。則有：
答案為
時(shí)間復(fù)雜度為
#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;
}
