Codeforces Round 920 (Div. 3)

• Codeforces Round 920 (Div. 3)

A

思路

横坐标的差值和纵坐标的差值之积

Code

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    vector<pair<int, int>> v;
    for (int i = 0; i < 4; i++)
    {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
    sort(v.begin(), v.end());
    cout << (v[3].second - v[0].second) * (v[3].first - v[0].first) << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

B

思路

两个字符串中 \(1\) 出现较少的个数加上两个字符串相差多少个 \(1\) 即为答案

Code

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n;
    string s, t;
    cin >> n >> s >> t;
    int a = 0, b = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == t[i] && s[i] == '1')
            continue;

        if (s[i] == '1')
            a++;
        if (t[i] == '1')
            b++;
    }

    cout << min(a, b) + abs(a - b) << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

C

思路

贪心，每步选择耗电最少的即可

Code

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    ll n, f, a, b;
    cin >> n >> f >> a >> b;
    vector<ll> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    ll now = 0;
    for (int i = 0; i < n; i++)
    {
        if ((v[i] - now) * a > b)
            f -= b;
        else
            f -= (v[i] - now) * a;
        now = v[i];
    }
    if (f <= 0)
        cout << "NO" << '\n';
    else
        cout << "YES" << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

D

思路

将两个序列排序后可知，对于每一个数 \(a_i\) 选择的应该是最大或者最小的 \(b_i\) ，用双指针从两边向中间移动，每次选择差值最大的

Code

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;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), c(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> c[i];
    sort(a.begin(), a.end());
    sort(c.begin(), c.end());

    int i = 0, j = n - 1;
    int l = 0, r = m - 1;
    ll ans = 0;
    while (i <= j)
    {
        if (max(abs(a[i] - c[l]), abs(a[i] - c[r])) <= max(abs(a[j] - c[l]), abs(a[j] - c[r])))
        {
            if (abs(a[j] - c[l]) >= abs(a[j] - c[r]))
            {
                ans += abs(a[j] - c[l]);
                l++;
            }
            else
            {
                ans += abs(a[j] - c[r]);
                r--;
            }
            j--;
        }
        else
        {
            if (abs(a[i] - c[l]) >= abs(a[i] - c[r]))
            {
                ans += abs(a[i] - c[l]);
                l++;
            }
            else
            {
                ans += abs(a[i] - c[r]);
                r--;
            }
            i++;
        }
    }

    cout << ans << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

E

思路

由题意可知，由于双方每次只能前进一步且不能后退或者停止，那么双方的交汇一定会在两者的中线，而谁吃谁由双方的初始距离决定。

1. 当双方一开始就是在同一排或者背对背，此时平局
2. 当双方的初始距离为奇数时，只有 \(Alice\) 可以吃掉 \(Bob\) 的棋子。
3. 当双方的初始距离为偶数时，只有 \(Bob\) 可以吃掉 \(Alice\) 的棋子。
4. 当出现会被吃的可能时，判断被吃掉的棋子能否逃脱，通过棋子的可移动范围可以判断，能逃脱即为平局。

Code

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int h, w, x, y, xx, yy;
    cin >> h >> w >> x >> y >> xx >> yy;
    if (x >= xx)
    {
        cout << "Draw" << endl;
        return;
    }

    if ((xx - x) % 2 == 1)
    {
        int t = (xx - x) / 2 + 1;
        if (max(1, yy - (t - 1)) >= max(1, y - t) && min(w, yy + (t - 1)) <= min(w, y + t))
        {
            cout << "Alice" << endl;
            return;
        }
    }
    else
    {
        int t = (xx - x) / 2;
        if (max(1, y - t) >= max(1, yy - t) && min(w, y + t) <= min(w, yy + t))
        {
            cout << "Bob" << endl;
            return;
        }
    }
    cout << "Draw" << endl;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}