AtCoder Beginner Contest 338

A - Capitalized?

问题陈述

给你一个由大写和小写英文字母组成的非空字符串 \(S\)。请判断是否满足以下条件：

  • \(S\) 的第一个字符是大写字母，其他所有字符都是小写字母。
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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
//变成题目那种模式
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    auto t = s;
    t[0] = toupper(t[0]);
    transform(t.begin() + 1, t.end(), t.begin() + 1, ::tolower);
    if (s == t)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}


---------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9, INF = 1e18;
int main()
{
    string s;
    cin >> s;
    if (s[0] >= 'A' and s[0] <= 'Z')
    {
        for (int i = 1; i < s.size(); i++)
        {
            if (s[i] >= 'a' and s[i] <= 'z')
                continue;
            cout << "No\n";
            return 0;
        }
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
    return 0;
}

B - Frequency

问题陈述

给你一个由小写英文字母组成的字符串 \(S\)。请找出在 \(S\) 中出现频率最高的字符。如果存在多个这样的字符，请报告按字母顺序排列最早的那个。

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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int long long
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    vector<int> mx(26, 0);
    int maxx = 0;
    for (int i = 0; i < n; i++)
    {
        mx[s[i] - 'a']++;
        maxx = max(maxx, mx[s[i] - 'a']);
    }
    for (int i = 0; i < 26; i++)
    {
        if (mx[i] == maxx)
        {
            char x = i + 'a';
            cout << x << '\n';
            return 0;
        }
    }
    return 0;
}

C - Leftover Recipes

问题陈述

你的冰箱里有 \(N\) 种配料。我们称它们为配料\(1\)、\(\dots\)和配料\(N\)。您有\(Q_i\)克配料\(i\)。

您可以制作两种菜肴。制作一份 A 菜肴，需要\(A_i\)克的配料\(i\) \((1 \leq i \leq N)\)。\((1 \leq i \leq N)\).制作一份 B 菜肴，每种材料需要\(B_i\)克\(i\)。每种菜只能做整数份。

仅使用冰箱中的配料，你最多可以制作多少份菜肴？

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
//暴力枚举A最多能有多少，然后算B即可
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int long long
const int N = 1e6 + 10;
int n;
int q[N], a[N], b[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> q[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
    }
    int mx = 1 << 30;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 0)
            continue;
        else
        {
            mx = min(mx, q[i] / a[i]);
        }
    }
    int ans = 0;
    for (int i = 0; i <= mx; i++)
    {
        int res = 1 << 30;
        for (int j = 1; j <= n; j++)
        {
            if (b[j] == 0)
                continue;
            res = min(res, (q[j] - a[j] * i) / b[j]);
        }
        res += i;
        ans = max(ans, res);
    }
    cout << ans << '\n';
    return 0;
}

D - Island Tour

问题陈述

AtCoder 群岛由 \(N\) 座岛屿组成，这些岛屿由 \(N\) 座桥梁连接。这些岛屿的编号从\(1\)到\(N\)，\(i\)（\(1\leq i\leq N-1\)）桥双向连接\(i\)和\(i+1\)岛，而\(N\)（\(1\)）桥双向连接\(N\)和\(1\)岛。除了过桥之外，没有其他方式可以在岛屿之间旅行。

在这些岛屿上，经常会有从\(X_1\)岛出发，依次游览\(X_2, X_3, \dots, X_M\)岛的*旅行团。游览过程中可能会经过正在游览的岛屿以外的其他岛屿，游览过程中经过桥梁的总次数定义为游览的长度**。

更确切地说，游是满足以下所有条件的\(l+1\)岛屿\(a_0, a_1, \dots, a_l\)序列，其长度定义为\(l\)：

  • 对于所有\(j\ (0\leq j\leq l-1)\)，岛屿\(a_j\)和\(a_{j+1}\)都由一座桥直接连接。
  • 有一些 \(0 = y_1 &lt; y_2 &lt; \dots &lt; y_M = l\)，对于所有 \(k\ (1\leq k\leq M)\)，\(a_{y_k} = X_k\)。

由于财政困难，这些岛屿将关闭一座桥，以减少维护费用。求在最佳情况下选择关闭的桥时，可能的最小游程长度。

考虑差分

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
#include <iostream>
#include <cstring>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N], route[N];
int n, m;
int calc(int a, int b)
{
    if (a > b)
        return b + n - a;
    return b - a;
}
void add(int x, int y, int val)
{
    if (x < y)
    {
        route[x] += val;
        route[y] -= val;
    }
    else
    {
        route[1] += val;
        route[x] += val;
        route[y] -= val;
    }
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    for (int i = 1; i < m; i++)
    {
        add(a[i + 1], a[i], calc(a[i], a[i + 1]));
        add(a[i], a[i + 1], calc(a[i + 1], a[i]));
    }
    for (int i = 1; i <= n; i++)
        route[i] += route[i - 1];
    int res = 0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= n; i++)
    {
        res = min(res, route[i]);
    }
    cout << res << endl;
    return 0;
}

E - Chords

注意有一种情况是包含于，因此本题不是简单的判断，而是需要进行诸如此类（（（）））的判断

问题陈述

在一个圆上有\(2N\)个等间隔的点，从某点开始按顺时针方向依次编号为\(1\)至\(2N\)。

圆上还有 \(N\) 条弦，其中 \(i\) 条弦连接点 \(A_i\) 和 \(B_i\)。保证所有的值 \(A_1,\dots,A_N,B_1,\dots,B_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
//括号序列匹配（）
//仔细想想就可以发现是括号序列匹配
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<pair<int, int>> a(2 * n);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        x--, y--;
        if (x > y)
            swap(x, y);
        a[x] = {0, i};
        a[y] = {1, i};
    }
    stack<int> s;
    for (int i = 0; i < 2 * n; i++)
    {
        if (a[i].first == 0)
        {
            s.push(a[i].second);
        }
        else
        {
            if (s.top() != a[i].second)
            {
                cout << "Yes" << '\n';
                return 0;
            }
            s.pop();
        }
    }
    cout << "No" << '\n';
    return 0;
}