Problem A
枚舉所有可能的情況(枚舉坐標(biāo)對(duì)取余的結(jié)果)晴竞,然后全部算出來取最大值即可宛蚓。
時(shí)間復(fù)雜度為橘荠。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int a[105], sum;
int main()
{
int n, k;
while(~scanf("%d%d", &n, &k))
{
memset(a, 0, sizeof(a));
sum = 0;
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
int ans = 0;
for(int i = 0; i < k; i++)
{
int e = 0, s = 0;
for(int j = 0; j < n; j++)
{
if(j % k == i)
{
continue;
}
if(a[j] == 1)
{
e++;
}
else
{
s++;
}
}
ans = max(ans, abs(e - s));
}
printf("%d\n", ans);
}
return 0;
}
Problem B
定義兩個(gè)計(jì)數(shù)表:
- 統(tǒng)計(jì)當(dāng)前數(shù)字一共有多少個(gè)的
- 統(tǒng)計(jì)當(dāng)前中值至少為i的個(gè)數(shù)的
然后逐個(gè)讀輸入并更新這兩個(gè)表个扰,一旦有一個(gè)達(dá)到了了嚎,就表明集齊了一套題。
時(shí)間復(fù)雜度為
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
int cnt[100005], dcnt[100005];
int main()
{
int n, m;
while(~scanf("%d%d", &n, &m))
{
memset(cnt, 0, sizeof(cnt));
memset(dcnt, 0, sizeof(dcnt));
int ans = 0;
for(int i = 0; i < m; i++)
{
int a;
scanf("%d", &a);
cnt[a]++;
dcnt[cnt[a]]++;
if(dcnt[ans + 1] == n)
{
ans++;
printf("1");
}
else
{
printf("0");
}
}
printf("\n");
}
return 0;
}
Problem C
根據(jù)余弦定理可以得到方程:
其中咧七,
解方程就完事了衰齐。
時(shí)間復(fù)雜度為
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
double n, r;
while(~scanf("%lf%lf", &n, &r))
{
double theta = 2.0 * acos(-1.0) / n;
double cosTheta = cos(theta);
double A = 2.0 * (1.0 + cosTheta);
double B = 4.0 * r * (cosTheta - 1.0);
double C = 2.0 * r * r * (cosTheta - 1.0);
double delta = B * B - 4.0 * A * C;
double ans = (-1.0 * B + sqrt(delta)) / (2.0 * A);
printf("%.7lf\n", ans);
}
return 0;
}