338

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\le i\le N)$。
• 制作一份 B 菜肴，每种配料需要 $B_i$ 克 $i$。
• 每种菜只能做整数份。

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

Solution

枚举所有的 A- $i(0\le i\le {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\le i\le 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\le j\le l-1)$，岛屿 $a_j$ 和 $a_{j+1}$ 都由一座桥直接连接。
• 有一些 $0=y_1<y_2<\cdots <y_M=l$，对于所有 $k(1\le k\le M)$，$a_{y_k}=X_k$

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

Solution

(待更 $\dots$)