AtCoder Beginner Contest 047

A

题目大意： 三个数，问其中两个数之和能否等于剩下那个数。

排序然后直接做。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int main()
{
    int n = 3;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end());
    if (a[1] + a[2] == a[3])
    {
        cout << "Yes" << '\n';
    }
    else
    {
        cout << "No" << '\n';
    }
    return 0;
}

B

题目大意： 按照题目描述染色 N轮，问二位平面没有染色的面积。

直接求最小和最大的行于列。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// LUOGU_RID: 173211005
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int main()
{
    int n;
    int w, h;
    cin >> w >> h >> n;
    int max_x = 0;
    int min_x = w;
    int max_y = 0;
    int min_y = h;
    for (int i = 1; i <= n; i++)
    {
        int opt;
        int x, y;
        cin >> x >> y >> opt;
        if (opt == 1)
        {
            max_x = max(max_x, x);
        }
        else if (opt == 2)
        {
            min_x = min(min_x, x);
        }
        else if (opt == 3)
        {
            max_y = max(max_y, y);
        }
        else
        {
            min_y = min(min_y, y);
        }
    }
    if(min_y<=max_y||min_x<=max_x)
    {
        cout<<0<<'\n';
        return 0;
    }
    cout << (min_y - max_y) * (min_x - max_x) << '\n';

    return 0;
}

C

C - 1D Reversi

题目大意： 依次放 'B' 和 'W' 的球，按照题目描述，最少需要多少次能够让所有的球颜色相同。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int main()
{
    string s;
    cin >> s;
    char t = s[0];
    int ans = 0;
    for (auto c : s)
    {
        if (c != t)
        {
            ans++;
        }
        t = c;
    }
    cout << ans << '\n';
    return 0;
}

D

D - An Invisible Hand

题目大意： 从 n 个数里面选两个数，答案为后一个数减前一个数的差的最大值。你现在需要修改一些数，将 Ai 修改为 A′i 的代价为 |Ai−A′i|，使答案至少小 1，求最小代价。

记录前缀最小值求出最大值即可。很套路的写法啦。

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// LUOGU_RID: 173221337
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
const ll mod = 1e9 + 7;
ll inv[maxn], fac[maxn]; // 分别表示逆元和阶乘
// 快速幂
ll quickPow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

void init()
{
    // 求阶乘
    fac[0] = 1;
    for (int i = 1; i <= maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
    // 求逆元
    inv[maxn - 1] = quickPow(fac[maxn - 1], mod - 2);
    for (int i = maxn - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll C(int n, int m)
{
    if (m > n)
    {
        return 0;
    }
    if (m == 0)
        return 1;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll get(ll a, ll b, ll c, ll d)
{
    return C(c - a + d - b, c - a) % mod;
}
int main()
{
    int ans=0;
    int n, m;
    cin >> n >> m;
    vector<int> b(n + 1);
    int maxn = -1e9;
    int minn = 1e9;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        b[i] = x - minn;
        minn = min(minn, x);
        maxn = max(maxn, b[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (b[i] == maxn)
        {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}