AtCoder Beginner Contest 334

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int a, b;
    cin >> a >> b;
    if (a > b)
        cout << "Bat";
    else
        cout << "Glove";
}

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

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

    return 0;
}

B

思路

给定 \(a,m,l,r\) ，问有多少个整数 \(k\) 满足 \(l \le a+mk \le r\) .

将 \(l\) 和 \(r\) 同时减去 \(a\) ，即可以认为树是从 \(0\) 点开始种的

此时有两种情况，记 \(sum(x,y)\) 为 \((x,y]\) 范围内有多少颗树：

  1. 当 \(l\) 和 \(r\) 在 \(0\) 的同一侧时， ans = sum(1, max(l, r)) - sum(1, min(l, r) - 1) ，即长的一段减去短的一段
  2. 当 \(l\) 和 \(r\) 不在 \(0\) 的同一侧时， ans = sum(1, l) + sum(1, r) + 1 ，即两段加上 \(0\) 点

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    ll a, m, l, r;
    cin >> a >> m >> l >> r;
    l -= a, r -= a;

    if (l <= 0 && r >= 0)
        cout << (abs(l) / m) + (abs(r) / m) + 1;
    else
        cout << max(abs(l), abs(r)) / m - (min(abs(l), abs(r)) - 1) / m;
}

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
42
43
44
#include <bits/stdc++.h>
using namespace std;

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

    int ans = 0;
    if (k % 2 == 0)
    {
        for (int i = 0; i < k; i += 2)
            ans += v[i + 1] - v[i];
    }
    else
    {
        int sum = 0;
        for (int i = k - 1; i > 0; i -= 2)
            sum += v[i] - v[i - 1];
        ans = sum;
        for (int i = 0; i < k - 1; i += 2)
        {
            sum -= v[i + 2] - v[i + 1];
            sum += v[i + 1] - v[i];
            ans = min(ans, sum);
        }
    }
    cout << ans;
}

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

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

    return 0;
}

D

思路

显然我们应该选择先拉需要麋鹿最少的雪橇

按所需麋鹿数量 \(r_i\) 升序排序后，找到最大的 \(k\) 满足 \(\sum^k_{i=1} r_i\le x\)

建立关于 \(r_i\) 的前缀和数组，在其中二分查找不大于 \(x\) 的最大值即可

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, q;
    cin >> n >> q;

    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a.begin(), a.end());
    partial_sum(a.begin(), a.end(), a.begin());

    while (q--)
    {
        ll x;
        cin >> x;
        cout << upper_bound(a.begin(), a.end(), x) - a.begin() << endl;
    }
}

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

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

    return 0;
}

E

思路

先通过 \(DFS\) 标记每个连通块，并记录总共的连通块个数 \(cnt\) 。

然后遍历每一个 . ，算出将其改变为 # 对连通块个数的影响。很显然，四个方向如果有 \(x\) 个不同的联通块，那么此时连通块的数量就变为了 \(cnt+1-x\) 。

累加每个情况连通块的数量，除以 . 的个数对 \(998244353\) 取模后即为答案

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e3 + 10;

char mp[N][N];
int vis[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, m, cnt, fm;
ll sum;

ll quickpow(ll a, ll n, ll mod)
{
    ll ret = 1;
    for (; n; n >>= 1, a = 1LL * a * a % mod)
        if (n & 1)
            ret = 1LL * ret * a % mod;
    return ret;
}

void dfs(int x, int y, int id)
{
    if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '.')
        return;

    vis[x][y] = id;

    for (int k = 0; k < 4; k++)
        dfs(x + dx[k], y + dy[k], id);
}

void check(int x, int y)
{
    set<int> s;
    for (int k = 0; k < 4; k++)
    {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m || mp[nx][ny] == '.')
            continue;

        s.insert(vis[nx][ny]);
    }
    sum += cnt + 1 - s.size();
}

void solve()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> mp[i][j];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == '#' && !vis[i][j])
                dfs(i, j, ++cnt);
            else if (mp[i][j] == '.')
                fm++;
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == '.')
                check(i, j);
        }
    }

    cout << sum % mod * quickpow(fm, mod - 2, mod) % mod;
}

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

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

    return 0;
}

F

思路

待补

Code

1
ACM > 题解 > AtCoder
#算法 #AtCoder
AtCoder Beginner Contest 334
http://xiaowhang.github.io/archives/1998245045/
作者
Xiaowhang
发布于
2023年12月24日
许可协议