【Codeforces】Codeforces Round #53

Problem A

枚举所有可能的情况（枚举坐标对取余的结果），然后全部算出来取最大值即可。

时间复杂度为。

#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

定义两个计数表：

• 统计当前数字一共有多少个的
• 统计当前中值至少为i的个数的

然后逐个读输入并更新这两个表，一旦有一个达到了，就表明集齐了一套题。

时间复杂度为

#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

根据余弦定理可以得到方程：

其中，
解方程就完事了。

时间复杂度为

#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;
}

后续待补充