AtCoder Beginner Contest 052

这场有点太简单了，最难的竟然是一道暴力求约数，纯纯的模板题。

A

输出 max(a * b, c * d)。

1
2
3
4
5
6
7
8
9
10
#include <iostream>
using namespace std;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max(a * b, c * d) << "\n";

    return 0;
}

B

小模拟，遇到 I 加一，遇到 D 减一，每次取个 max 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    int ans = 0, tmp = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'I') tmp++;
        else tmp--;
        ans = max(tmp, ans);
    }
    cout << ans << "\n";

    return 0;
}

C

唯一分解定理求约数，更优秀可以用欧拉筛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

bool is_prime(int n)
{
    if (n == 1)
        return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

vector<int> p;

int main()
{
    int n;
    cin >> n;
    ll ans = 1;
    // 筛素数
    for (int i = 1; i <= n; i++)
    {
        if (is_prime(i))
            p.push_back(i);
    }
    // 唯一分解定理
    for (auto v : p)
    {
        ll cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            int tmp = i;
            while (tmp % v == 0)
            {
                cnt++;
                tmp /= v;
            }
        }
        cnt++;
        ans = ans * cnt % mod;
    }
    cout << ans << "\n";

    return 0;
}

D

贪心题。每次直接算第一种好还是第二种好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// LUOGU_RID: 173278862
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

bool is_prime(int n)
{
    if (n == 1)
        return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

vector<int> p;

int main()
{
    long long n, a, b, sum = 0;
    cin >> n >> a >> b;
    long long x[1000001];
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 2; i <= n; i++)
        sum += min(b, a * (x[i] - x[i - 1]));
    cout << sum;
    return 0;
}

PS：这场打完什么也没学到。