AtCoder Beginner Contest 253 Tutorial

A - Median?

第一题签个到，我没用编译器，直接在网站上打的代码

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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if (a <= b && b <= c)
        cout << "Yes" << endl;
    else if (a >= b && b >= c)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

B - Distance Between Tokens

输入，记录，求距离。。。

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
// Problem: B - Distance Between Tokens
// Contest: AtCoder - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）
// URL: https://atcoder.jp/contests/abc253/tasks/abc253_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e5 + 10;

// bool st;
int n, m;
int x, y, xx, yy;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            if (c == 'o')
            {
                if (x)
                {
                    xx = i;
                    yy = j;
                }
                else
                {
                    x = i;
                    y = j;
                }
            }
        }
    }
    cout << abs(x - xx) + abs(y - yy) << endl;
    return 0;
}

C - Max - Min Query

卡了我一会

记录一下:

  • set中rbegin取最大值，begin取最小值

然后就没有什么难度了，用一个map记录一下个数即可

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
// Problem: C - Max - Min Query
// Contest: AtCoder - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）
// URL: https://atcoder.jp/contests/abc253/tasks/abc253_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e5 + 10;

// bool st;
int q;
map<int, int> mp;
set<int> s;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x;
            cin >> x;
            // cerr << x << endl;
            if (!mp[x])
                s.insert(x);
            mp[x]++;
        }
        if (op == 2)
        {
            int x, c;
            cin >> x >> c;
            if (mp[x] > c)
                mp[x] -= c;
            else
            {
                if (mp[x])
                    s.erase(x);
                mp[x] = 0;
            }
        }
        if (op == 3)
        {

            cout << (*s.rbegin()) - (*s.begin()) << endl;
        }
        //cerr << s.size() << endl;
    }
    return 0;
}

D - FizzBuzz Sum Hard

数学题，简单容斥

∑i=1i≤ni=n⋅(n+1)2\sum_{i=1}^{i\leq n}i=\frac{n\cdot (n+1)}{2}

其中，a的倍数的和为: 设aa=[na]aa=[\frac{n}{a}]，则∑i=1,a∣ii≤ni=aa⋅(aa+1)2⋅a\sum_{i=1,a|i}^{i\leq n} i=\frac{aa\cdot (aa+1)}{2}\cdot a

同理，b的倍数的合为: 设bb=[nb]bb=[\frac{n}{b}]，则∑i=1,b∣ii≤ni=bb⋅(bb+1)2⋅b\sum_{i=1,b|i}^{i\leq n} i=\frac{bb\cdot (bb+1)}{2}\cdot b

此时，我们重复考虑了lcm(a,b)lcm(a,b)的倍数，在减去即可，式子和上面一样

p.s. lcm(a,b)=a⋅bgcd(a,b)lcm(a,b)=\frac{a\cdot b}{gcd(a,b)} gcd可以通过欧几里得算法求解

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
// Problem: D - FizzBuzz Sum Hard
// Contest: AtCoder - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）
// URL: https://atcoder.jp/contests/abc253/tasks/abc253_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e5 + 10;

// bool st;
int n, a, b;
// bool en;

int gcd(int x, int y)
{
    if (x == 0)
        return y;
    return gcd(y % x, x);
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> a >> b;
    int aa = n / a;
    int bb = n / b;
    int nn = n / (a * b / gcd(a, b));
    cout << n * (n + 1) / 2 - (a * ((aa + 1) * aa / 2)) - (b * ((bb + 1) * bb / 2)) +
                ((a * b / gcd(a, b)) * (nn * (nn + 1) / 2))
         << endl;
    return 0;
}

E - Distance Sequence

目测dp

考虑最朴素的状态设计:dpi,jdp_{i,j}表示ai=ja_i=j时的可能数，这个状态一般情况下需要O(nm2)O(nm^2)转移

如何优化

发现每次转移都是dpi−1dp_{i-1}的一段连续区间和，很明显，可以使用前缀和预处理，使得每个转移变为O(1)O(1)，把时间复杂度降到O(nm)O(nm)级别

注意，该方法在k=0k=0时会重复计算，所以k=0k=0时可以用快速幂直接数学计算结果，即mnm^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
// Problem: E - Distance Sequence
// Contest: AtCoder - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）
// URL: https://atcoder.jp/contests/abc253/tasks/abc253_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned int
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 1e5 + 10;

// bool st;
int n, m, k;
int dp[1005][5005];
int sum[5005];
// bool en;
int quickMod(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> m >> k;
    if (k == 0)
    {
        cout << quickMod(m, n) % MOD << endl;
        return 0;
    }
    for (int i = 1; i <= m; i++)
    {
        dp[1][i] = 1;
        sum[i] = i;
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (j > k)
                dp[i][j] += sum[j - k] % MOD;
            dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
            if (j + k <= m)
                dp[i][j] += sum[m] - sum[j + k - 1];
            dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
        }
        memset(sum, 0, sizeof(sum));
        for (int j = 1; j <= m; j++)
            sum[j] = (sum[j - 1] % MOD + dp[i][j] % MOD + MOD) % MOD;
    }
    cout << sum[m] % MOD << endl;
    return 0;
}

先写到这里，后面的题会陆续更新的。。。