338 | FXJFXJ

C 勉强写出来😒在 ABC 我希望在寒假能达到只有最后一道做不出来(A-F，至少写出 A-E)。

A - Capitalized?

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

\(S\) 的第一个字符是大写字母，其他所有字符都是小写字母。

void solve()
{
    string a;
    cin >> a;
    for (int i = 1; i < a.size(); i++)
    {
        if (isupper(a[i]))
        {
            cout << "No\n";
            return;
        }
    }
    if (isupper(a[0]))
        cout << "Yes\n";
    else
        cout << "No\n";
}

B - Frequency

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

int num[30];
void solve()
{
    string a;
    cin >> a;
    for (int i = 0; i < a.size(); i++)
        num[a[i] - 'a']++;
    int max = 0;
    for (int i = 1; i < 26; i++)
    {
        if (num[i] > num[max])
            max = i;
    }
    cout << char(max + 'a') << '\n';
}

C - Leftover Recipes

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

您可以制作两种菜肴。

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

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

Solution

枚举所有的 A- \(i(0\leq i\leq 10^6)\),对于每一个 \(i\)，都有唯一对应的 B- \(j\) 与之对应。记得还原 \(q[j]\)

void solve()
{
    int n;
    cin >> n;
    vector<int> q(n + 1), a(n + 1), b(n + 1);
    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 ans1 = 0, ans2 = INT_MAX, ans = 0;

    for (int i = 0; i <= 1e6; i++)
    {
        ans2 = INT_MAX;
        for (int j = 1; j <= n; j++)
        {
            q[j] -= i * a[j];
            if (q[j] < 0)
            {
                cout << ans << '\n';
                return;
            }
        }
        ans1 = i;

        for (int j = 1; j <= n; j++)
            if (b[j])
                ans2 = min(ans2, q[j] / b[j]);

        ans = max(ans, ans1 + ans2);

        for (int j = 1; j <= n; j++)
            q[j] += a[j] * i;//还原q
    }
    cout << ans << '\n';
}

官方 py 代码：

N = int(input())
Q = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
INF = 10**18

ans = 0
for x in range(max(Q) + 1):
    y = INF
    for i in range(N):
        if Q[i] < A[i] * x:
            y = -INF
        elif B[i] > 0:
            y = min(y, (Q[i] - A[i] * x) // B[i])
    ans = max(ans, x + y)
print(ans)

D - Island Tour

AtCoder 群岛由 \(N\) 座岛屿组成，这些岛屿由 \(N\) 座桥梁连接。这些岛屿的编号从 \(1\) 到 \(N\)

\(i\)（\(1\leq i\leq N-1\)）桥双向连接 \(i\) 和 \(i+1\) 岛，而 \(N\)桥双向连接 \(N\) 和 \(1\) 岛。除了过桥之外，没有其他方式可以在岛屿之间旅行。

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

更确切地说，Tour 是满足以下所有条件的 \(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 < y_2 < \dots < y_M = l\)，对于所有 \(k\ (1\leq k\leq M)\)，\(a_{y_k} = X_k\)

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

Solution

(待更 \(\dots\))