牛客小白月赛86

A. 水盐平衡

思路：

• 直接比较两个溶液的浓度大小即可

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

void solve() {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;

    double x = a * 1.0 / (b + a);
    double y = c * 1.0 / (d + c);

    if (x > y) {
        std::cout << "S\n";
    } else {
        std::cout << "Y\n";
    }
}

B. 水平考试

思路：

• 如果填写的字符串长度大于答案的长度，那么一定错误
• 如果填写的字符串中出现了答案不存在的字符，那么一定错误
• 也就是说，除了满分10分外，就是0分

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

void solve() {
    std::string S, F;
    std::cin >> S >> F;

    int n = S.size();

    std::unordered_set<char> st;
    for (char c : F) {
        st.insert(c);
    }

    if (n > F.size()) {
        std::cout << "0\n";
        return ;
    }

    for (int i = 0; i < n; i++) {
        if (!st.count(S[i])) {
            std::cout << "0\n";
            return ;
        }
    }
    std::cout << "10\n";
}

C. 数组段数

思路：

• 差分的思想，在每一个连续子段的开头都插入一个1 ，即可得到一个前缀和数组(关于子段数量的)，然后一减即可

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

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

    std::vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> A[i];
    }
    std::vector<int> c(n + 2);
    c[1] = 1;
    for (int i = 1; i <= n; i++) {
        int j = i;
        while (A[j] == A[i]) {
            j++;
        }
        c[j]++;
        i = j - 1;
    }

    for (int i = 1; i <= n; i++) {
        c[i] += c[i - 1];
    }

    while (m--) {
        int l, r;
        std::cin >> l >> r;

        std::cout << c[r] - c[l] + 1 << "\n";
    }
    
    return 0;
}

D. 剪纸游戏

思路：

• 暴搜统计一下数量即可，将一个方块中的个数和最大顶点和最小顶点组成的长方形与这个方块中的小方块个数比较一下即可

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

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

    std::vector g(n, std::vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> g[i][j];
        }
    }

    int ans = 0;
    std::array<int, 4> dx {-1, 0, 1, 0}, dy {0, -1, 0, 1};
    std::vector vis(n, std::vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!vis[i][j] && g[i][j] == '.') {
                int cnt = 0, hig = i, wid = j, mx = i, my = j;
                auto dfs = [&](auto self, int x, int y) -> void {
                    vis[x][y] = true;
                    cnt++;
                    for (int i = 0; i < 4; i++) {
                        int a = x + dx[i], b = y + dy[i];
                        if (b >= m || a >= n || a < 0 || b < 0) continue ;
                        if (vis[a][b] || g[a][b] == '*') continue ;
                        vis[a][b] = true;
                        hig = std::max(hig, a);
                        mx = std::min(mx, a);
                        my = std::min(my, b);
                        wid = std::max(wid, b);
                        self(self, a, b);
                    }
                };
                dfs(dfs, i, j);
                if (cnt == (wid - my + 1) * (hig - mx + 1)) {
                    ans++;
                }
            }
        }
    }
    std::cout << ans << "\n";

    return 0;
}

E. 可口蛋糕

思路：

• 首先找到第一个满足 \(W\) 的位置，然后，这个位置一直到 \(n\) 一定都是满足和大于 \(W\) 的
• 在使用一个 \(mx_i\) 维护一下区间中 \(d\) 的前缀和的最大值，然后每次用 \(mx_p-sumd_i\) 即可
• 因为 \(mx_i\) 保证了这是这个前缀和序列中的最大值，所以二分出的零界点 \(p\) ，也不用管之后的最大值了，已经被 \(mx_i\)​ 维护了

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

constexpr i64 inf = 1LL << 60;

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

    std::vector<i64> w(n + 1), d(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> w[i];
        w[i] += w[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        std::cin >> d[i];
        d[i] += d[i - 1];
    }

    std::vector<i64> mx(n + 2, -inf);
    for (int i = n; i >= 1; i--) {
        mx[i] = std::max(mx[i + 1], d[i]);
    }
    i64 ans = -inf;
    for (int i = 1; i <= n; i++) {
        int p = std::lower_bound(w.begin() + 1, w.end(), W + w[i - 1]) - w.begin();
        ans = std::max(ans, mx[p] - d[i - 1]);
    }
    std::cout << ans << "\n";

    return 0;
}