AtCoder Beginner Contest 163 解题报告

本文代码均省略库和namespace声明，其中read()函数是读入数值的函数。

A - Circle Pond
Print the circumference of a circle of radius R.
1 ≤ R ≤ 100

简单的模拟题，输入R输出对应的圆周长即可
小技巧 通常使用 acos(-1) 表示精度很高的π

double r;
int main()
{
    cin >> r;
    cout << 2 * acos(-1) * r;
    return 0;
}

B - Homework
Takahashi has N days of summer vacation. His teacher gave him M summer assignments. It will take A_i days for him to do the i-th assignment. He cannot do multiple assignments on the same day, or hang out on a day he does an assignment. What is the maximum number of days Takahashi can hang out during the vacation if he finishes all the assignments during this vacation? If Takahashi cannot finish all the assignments during the vacation, print -1 instead.
1 ≤ N ≤ 10⁶
1 ≤ M ≤ 10⁴
1 ≤ A_i ≤ 10⁴

简单模拟题，对所有A_i求和后与n进行比较，对应情况输出即可。

int n, m, a, sum;
int main()
{
    read(n);
    read(m);
    for(int i = 1; i <= m; ++i)
    {
        read(a);
        sum += a;
    }
    if(sum > n) printf("-1");
    else printf("%d", n - sum);
    return 0;
}

C - management
A company has N members, who are assigned ID numbers 1,...,N. Every member, except the member numbered 1, has exactly one immediate boss with a smaller ID number. When a person X is the immediate boss of a person Y, the person Y is said to be an immediate subordinate of the person X. You are given the information that the immediate boss of the member numbered i is the member numbered A_i. For each member, find how many immediate subordinates it has.
2 ≤ N ≤ 2 × 10⁵
1 ≤ A_i < i

模拟记录输出就好了

int n, ans[200001];
int main()
{
    read(n);
    for (int i = 2, t; i <= n; ++i)
    {
        read(t);
        ++ans[t];
    }
    for (register int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}

D - Sum of Large Numbers
We have N+1 integers: 10¹⁰⁰, 10¹⁰⁰+1,..., 10¹⁰⁰+N. We will choose K or more of these integers. Find the number of possible values of the sum of the chosen numbers, modulo (10⁹+7).
1 ≤ N ≤ 2 × 10⁵
1 ≤ K ≤ N + 1

容易知道，对于一个k值，这样一个数字序列A_i能生成的最小数V_min是Σ(A₀..A_K-1)，最大数V_max是Σ(A_N-K+1..A_N)，易证能取遍V_min到V_max中的所有数，即可以形成V_max-V_min+1个数。
容易知道，K的取值上限是N+1，循环求解即可。
需要知道，这个数字序列拥有这样的特性：每一个K之间取得的情况不会出现重复结果，所以把所有K对应情况的结果相加即为正确答案。（我无法进行严格证明，需要读者给出）
小技巧 频繁求区间和可以用前缀和优化。在本题中如果用循环求区间和会导致TLE。
提示 需要使用 long long 类型储存ans和sum

int n,k;
long long ans,sum[200001];
int main()
{
    read(n); read(k);
    for (int i=1;i<=n;++i) sum[i]=sum[i-1]+i;
    while(k<=n+1)
    {
        ans+=sum[n]-sum[n-k]-sum[k-1]+1;
        ans%=1000000007;
        ++k;
    }
    printf("%lld",ans);
    return 0;
}

E - Active Infants
There are N children standing in a line from left to right. The activeness of the i-th child from the left is A_i. You can rearrange these children just one time in any order you like. When a child who originally occupies the x-th position from the left in the line moves to the y-th position from the left, that child earns A_x × |x−y| happiness points. Find the maximum total happiness points the children can earn.
1 ≤ N ≤ 2000
1 ≤ A_i ≤ 10⁹