Atcoder Beginner Contest 251 Tutorial

图表(仅供参考)

A - Six Characters

签到题

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
// Problem: A - Six Characters
// Contest: AtCoder - Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)
// URL: https://atcoder.jp/contests/abc251/tasks/abc251_a
// 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;
string s;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> s;
    if (s.size() == 1)
        cout << s + s + s + s + s + s << endl;
    else if (s.size() == 2)
        cout << s + s + s << endl;
    else
        cout << s + s << endl;
    return 0;
}

B - At Most 3 (Judge ver.)

暴力检查就行，其实不需要卡常，如果你循环了一半实在想break，不要忘记在枚举前sort哦（不要问我是怎么知道的qwq

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
// Problem: B - At Most 3 (Judge ver.)
// Contest: AtCoder - Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)
// URL: https://atcoder.jp/contests/abc251/tasks/abc251_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 = 1e6 + 10;

// bool st;
int n;
bool vis[N];
int a[N];
int w;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> w;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        vis[a[i]] = 1;
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (a[i] + a[j] > w)
                break;
            vis[a[i] + a[j]] = 1;
            for (int k = j + 1; k <= n; k++)
                if (a[i] + a[j] + a[k] > w)
                    break;
                else
                    vis[a[i] + a[j] + a[k]] = 1;
        }
    }
    int res = 0;
    for (int i = 1; i <= w; i++)
        if (vis[i])
            res++;
    cout << res << endl;
    return 0;
}

C - Poem Online Judge

Method

数据结构，用一个map存一下就行，具体见代码

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
// Problem: C - Poem Online Judge
// Contest: AtCoder - Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)
// URL: https://atcoder.jp/contests/abc251/tasks/abc251_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 n;
map<string, bool> mp;
string s;
int res = 0;
int pos;
int t;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s >> t;
        if (mp[s])
            continue;
        mp[s] = 1;
        if (t > res)
        {
            res = t;
            pos = i;
        }
    }
    cout << pos << endl;
    return 0;
}

D - At Most 3 (Contestant ver.)

恶心的构造题

Method

可以考虑把W分为三段，每一段是两个数位。此时，每一段可以用100个数来表示。

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
// Problem: D - At Most 3 (Contestant ver.)
// Contest: AtCoder - Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)
// URL: https://atcoder.jp/contests/abc251/tasks/abc251_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 w;
int a[305] = {
    0,      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,     91,     92,     93,     94,     95,     96,     97,
    98,     99,     100,    100,    200,    300,    400,    500,    600,    700,    800,    900,    1000,   1100,
    1200,   1300,   1400,   1500,   1600,   1700,   1800,   1900,   2000,   2100,   2200,   2300,   2400,   2500,
    2600,   2700,   2800,   2900,   3000,   3100,   3200,   3300,   3400,   3500,   3600,   3700,   3800,   3900,
    4000,   4100,   4200,   4300,   4400,   4500,   4600,   4700,   4800,   4900,   5000,   5100,   5200,   5300,
    5400,   5500,   5600,   5700,   5800,   5900,   6000,   6100,   6200,   6300,   6400,   6500,   6600,   6700,
    6800,   6900,   7000,   7100,   7200,   7300,   7400,   7500,   7600,   7700,   7800,   7900,   8000,   8100,
    8200,   8300,   8400,   8500,   8600,   8700,   8800,   8900,   9000,   9100,   9200,   9300,   9400,   9500,
    9600,   9700,   9800,   9900,   10000,  10000,  20000,  30000,  40000,  50000,  60000,  70000,  80000,  90000,
    100000, 110000, 120000, 130000, 140000, 150000, 160000, 170000, 180000, 190000, 200000, 210000, 220000, 230000,
    240000, 250000, 260000, 270000, 280000, 290000, 300000, 310000, 320000, 330000, 340000, 350000, 360000, 370000,
    380000, 390000, 400000, 410000, 420000, 430000, 440000, 450000, 460000, 470000, 480000, 490000, 500000, 510000,
    520000, 530000, 540000, 550000, 560000, 570000, 580000, 590000, 600000, 610000, 620000, 630000, 640000, 650000,
    660000, 670000, 680000, 690000, 700000, 710000, 720000, 730000, 740000, 750000, 760000, 770000, 780000, 790000,
    800000, 810000, 820000, 830000, 840000, 850000, 860000, 870000, 880000, 890000, 900000, 910000, 920000, 930000,
    940000, 950000, 960000, 970000, 980000, 990000, 1000000};
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> w;
    int en;
    for (int i = 1; a[i] <= w && i <= 300; i++)
        en = i;
    cout << en << endl;
    for (int i = 1; i <= en; i++)
        cout << a[i] << ' ';
    return 0;
}

小小的打表。。。

E - Tahakashi and Animals

Method

dp

  • 每段至多用一次
  • 单独考虑n~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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Problem: E - Tahakashi and Animals
// Contest: AtCoder - Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)
// URL: https://atcoder.jp/contests/abc251/tasks/abc251_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 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 = 3e5 + 10;
int n, a[300005], ans;
int dp[300005][2];

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    memset(dp, 0x3f, sizeof(dp));
    dp[0][1] = 0;
    for (int i = 0; i <= n; i++)
    {
        dp[i + 1][0] = dp[i][1];
        if (i != 0)
            dp[i + 1][1] = min(dp[i][0] + a[i], dp[i][1] + a[i]);
        dp[i][1] = min(dp[i][1], dp[i][0] + a[i]);
    }
    ans = dp[n][1];
    memset(dp, 0x3f, sizeof(dp));
    dp[1][1] = a[n];
    for (int i = 1; i <= n - 1; i++)
    {
        dp[i + 1][0] = dp[i][1];
        if (i != 0)
            dp[i + 1][1] = min(dp[i][0] + a[i], dp[i][1] + a[i]);
        dp[i][1] = min(dp[i][1], dp[i][0] + a[i]);
    }
    if (dp[n - 1][1] < ans)
        ans = dp[n - 1][1];
    cout << ans << endl;
    return 0;
}

后面就不会了qwq

%巨佬