AtCoder Beginner Contest 338

A. Capitalized?

思路：

• 模拟题意即可

时间复杂度：\(O(n)\)

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    bool ok = true;
    for (int i = 0; i < s.size(); i++) {
        if (!i) {
            if (!std::isupper(s[i])) {
                ok = false;
            }
        } else {
            if (!std::islower(s[i])) {
                ok = false;
            }
        }
    }

    std::cout << (ok ? "Yes\n" : "No\n");
    
    return 0;
}

B. Frequency

思路：

• 记录字符串中所有字符的出现次数，找到字典序最小的那个即可

时间复杂度：\(O(n)\)

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string s;
    std::cin >> s;

    std::vector<int> cnt(26);
    for (int i = 0; i < s.size(); i++) {
        cnt[s[i] - 'a']++;
    }

    int mx = *max_element(cnt.begin(), cnt.end());

    for (int i = 0; i < 26; i++) {
        if (cnt[i] == mx) {
            std::cout << char(i + 'a') << "\n";
            return 0;
        }
    }

    return 0;
}

C. Leftover Recipes

思路：

• 首先注意数据范围 \(N \le 10\) ，运用数学推导，可以发现我们需要求的东西是 \(A_ix+B_iy \le Q_i \Rightarrow B_iy \le Q_i - A_ix\)​ ，所以我们要求的就是 \(x+y\) 的最大值
• 所以我们可以枚举 \(x\)，首先当 \(Q_i - A_ix \lt 0\) ，那么 \(A\) 菜不能做，就舍弃这个值，所以现在的 \(Q_i-A_ix \ge 0\) 代表所有的 \(i\) 。
• 如果 \(B_i=0\) 那么我们可以制作任意份数的 \(B\) 菜，否则，我们最多制作 \(\lfloor \frac{(Q_i-A_ix)}{B_i} \rfloor\) 份 \(B\) 菜，而且不会用完配料 \(i\)，如果我们对所有的食材都这么计算，那么就可以求出 \(y\)​ 的最大值。

时间复杂度：\(O(n * mx)\)

constexpr i64 inf = 1LL << 60;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;

    std::vector<int> Q(N), A(N), B(N);
    for (int i = 0; i < N; i++) {
        std::cin >> Q[i];
    }
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        std::cin >> B[i];
    }

    int mx = *max_element(Q.begin(), Q.end());

    i64 ans = 0;
    for (int i = 0; i <= mx; i++) {
        i64 y = inf;
        for (int j = 0; j < N; j++) {
            if (Q[j] < 1LL * A[j] * i) {
                y = -inf;
            } else if (B[j] > 0) {
                y = std::min(y, (1LL * Q[j] - 1LL * A[j] * i) / B[j]);
            }
        }
        ans = std::max(ans, i + y);
    }
    std::cout << ans << "\n"; 

    return 0;
}

D. Island Tour

思路：

• 这 \(n\) 个点围成一个圈，每次删除的哪个点，我们可以从 \(a \rightarrow a-1 \rightarrow a-2 \rightarrow ...\rightarrow b\) 或者从 \(a \rightarrow a+1 \rightarrow a+2 \rightarrow ... \rightarrow b\)​ ，我们可以将其划分为两个集合。

时间复杂度：\(O(m)\)

constexpr i64 inf = 1LL << 60;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, M;
    std::cin >> N >> M;

    std::vector<int> X(M);
    for (int i = 0; i < M; i++) {
        std::cin >> X[i];
        X[i]--;
    }

    auto dist = [&](int x, int y) {
        if (x <= y) return y - x;
        return y - x + N;
    };

    std::vector<i64> v(N + 1);
    auto add = [&](int x, int y, int c) {
        if (x <= y) {
            v[x] += c;
            v[y] -= c;
        } else {
            v[x] += c;
            v[N] -= c;
            v[0] += c;
            v[y] -= c;
        }
    };

    for (int i = 0; i < M - 1; i++) {
        add(X[i], X[i + 1], dist(X[i + 1], X[i]));
        add(X[i + 1], X[i], dist(X[i], X[i + 1]));
    }

    i64 ans = inf;
    for (int i = 0; i < N; i++) {
        v[i + 1] += v[i];
        ans = std::min(ans, v[i]);
    }
    std::cout << ans << "\n";

    return 0;
}

E. Chords

思路：