AtCoder Beginner Contest 331

• AtCoder Beginner Contest 331

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
32
33
34
35

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int mm, dd;
    cin >> mm >> dd;
    int y, m, d;
    cin >> y >> m >> d;
    d++;
    if (d == dd + 1)
        d = 1, m++;
    if (m == mm + 1)
        m = 1, y++;
    cout << y << ' ' << m << ' ' << d;
}

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

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

    return 0;
}

B

思路

遍历所有可能取最小值即可

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n, a, b, c;
    cin >> n >> a >> b >> c;

    int ans = INF;
    for (int i = 0; i <= 20; i++)
    {
        for (int j = 0; j <= 20; j++)
        {
            for (int k = 0; k <= 20; k++)
            {
                if (6 * i + 8 * j + 12 * k >= n)
                    ans = min(ans, i * a + j * b + k * c);
            }
        }
    }

    cout << ans;
}

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e6 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vector<ll> sum(N), a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum[a[i]]++;
    }

    for (int i = 1000000; i >= 1; i--)
        sum[i] = sum[i + 1] + sum[i] * i;

    for (int i = 0; i < n; i++)
        cout << sum[a[i] + 1] << ' ';
}

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

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

    return 0;
}

D

思路

先预处理 \(n*n\) 的范围内的二维前缀和

记以 \((0,0)\) 为左上角， \((x,y)\) 为右下角的黑块的数量为 \(f(x,y)\)

对于一整个区域，我们分为四部分：

1. 左上角的 \((x/n)*(y/n)\) 个 \(n*n\) 的范围
2. 右上角的 \((x/n)\) 个 \(n*(y\%n)\) 的范围
3. 左下角的 \((y/n)\) 个 \(n*(x\%n)\) 的范围
4. 右下角的 \(1\) 个 \((x\%n)*(y\%n)\) 的范围

由二维前缀和以及容斥原理可知： \(ans= f(c,d)-f(c,b-1)-f(a-1,d)+f(a-1,b-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
39
40
41
42
43
44
45
46
47
48
49

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

vector<vector<char>> mp(N, vector<char>(N));
vector<vector<ll>> sum(N + 10, vector<ll>(N + 10));
int n, q;

ll cal(int x, int y)
{
    ll res = 0;
    res += 1LL * (x / n) * (y / n) * sum[n][n];
    res += 1LL * (y / n) * sum[x % n][n];
    res += 1LL * (x / n) * sum[n][y % n];
    res += 1LL * sum[x % n][y % n];
    return res;
}

void solve()
{
    cin >> n >> q;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> mp[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            sum[i][j] = (mp[i - 1][j - 1] == 'B') + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

    while (q--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << cal(c + 1, d + 1) - cal(c + 1, b) - cal(a, d + 1) + cal(a, b) << endl;
    }
}

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

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

    return 0;
}

E

思路

将 \(a,\ b\) 两个数组降序排序后。

易证，对于 \(a_i\ (0 \le i \le n)\) 和 \(b_j\ (0 \le j \le m)\) ， \(a_i+b_j\) 的前 \(l+1\) 大满足 \(i*j \le \sqrt{nm}\)

找出范围内的所有值中没被限制的最大值即为答案

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node
{
    int w, id;
    friend bool operator<(const node a, const node b)
    {
        return a.w > b.w;
    }
};

void solve()
{
    int n, m, l;
    cin >> n >> m >> l;

    vector<node> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].w;
        a[i].id = i;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i].w;
        b[i].id = i;
    }

    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());

    set<pair<int, int>> no;
    while (l--)
    {
        int c, d;
        cin >> c >> d;
        no.insert(make_pair(c, d));
    }

    priority_queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m && i * j <= max(1e5, sqrt(n * m)); j++)
        {
            if (no.count(make_pair(a[i].id, b[j].id)))
                continue;
            q.push(a[i].w + b[j].w);
        }
    }
    cout << q.top();
}

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

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

    return 0;
}