A - Tomorrow

本题要求计算给定日期的下一天。输入包含一年的月数 M、一个月的天数 D，以及当前的年、月、日。只需对日进行加一操作，并根据 D 和 M 处理进位逻辑即可。

#include <iostream>

void solve() {
    int months_in_year, days_in_month;
    int year, month, day;
    std::cin >> months_in_year >> days_in_month >> year >> month >> day;
    
    day++;
    if (day > days_in_month) {
        day = 1;
        month++;
        if (month > months_in_year) {
            month = 1;
            year++;
        }
    }
    std::cout << year << " " << month << " " << day << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

B - Buy One Carton of Milk

题目提供三种包装的牛奶：6盒装、8盒装和12盒装，价格分别为 a、b、c。目标是购买至少 n 盒牛奶的最小花费。通过枚举6盒装和8盒装的购买数量，可以直接计算出12盒装所需的最小数量，从而将时间复杂度优化至合理范围。

#include <iostream>
#include <algorithm>

void solve() {
    long long n, a, b, c;
    std::cin >> n >> a >> b >> c;
    
    long long min_cost = 1e18;
    for (long long i = 0; i * 6 <= n + 12; ++i) {
        for (long long j = 0; j * 8 <= n + 12; ++j) {
            long long remaining = n - (i * 6 + j * 8);
            long long k = (remaining > 0) ? (remaining + 11) / 12 : 0;
            min_cost = std::min(min_cost, i * a + j * b + k * c);
        }
    }
    std::cout << min_cost << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

C - Sum of Numbers Greater Than Me

对于数组中的每个元素，需要求出严格大于它的其他元素之和。可以通过对数组进行排序并计算前缀和，随后利用二分查找（std::upper_bound）快速定位大于当前元素的起始位置，从而在 $O(1)$ 时间内通过前缀和得出结果。

#include <iostream>
#include <vector>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> nums(n), sorted_nums(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
        sorted_nums[i] = nums[i];
    }
    
    std::sort(sorted_nums.begin(), sorted_nums.end());
    std::vector<long long> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + sorted_nums[i];
    }
    
    for (int i = 0; i < n; ++i) {
        auto it = std::upper_bound(sorted_nums.begin(), sorted_nums.end(), nums[i]);
        int idx = std::distance(sorted_nums.begin(), it);
        long long sum_greater = prefix_sum[n] - prefix_sum[idx];
        std::cout << sum_greater << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

D - Tile Pattern

给定一个 $N \times N$ 的字符矩阵，将其在二维平面上无限平铺。需要回答多个查询，计算指定子矩阵中字符 'B' 的数量。 核心思路是利用二维前缀和结合周期性数学计算。定义函数 count_B(r, c) 计算从 $(1, 1)$ 到 $(r, c)$ 的 'B' 数量，将其拆分为完整周期块和边缘剩余部分。查询时利用容斥原理 count_B(c, d) - count_B(a-1, d) - count_B(c, b-1) + count_B(a-1, b-1) 即可快速得出答案。

#include <iostream>
#include <vector>
#include <string>

int n, q;
std::vector<std::vector<int>> P;

long long count_B(long long r, long long c) {
    if (r <= 0 || c <= 0) return 0;
    long long full_r = r / n;
    long long rem_r = r % n;
    long long full_c = c / n;
    long long rem_c = c % n;
    
    long long res = 0;
    res += full_r * full_c * P[n][n];
    res += full_r * P[n][rem_c];
    res += full_c * P[rem_r][n];
    res += P[rem_r][rem_c];
    return res;
}

void solve() {
    std::cin >> n >> q;
    P.assign(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        std::string row;
        std::cin >> row;
        for (int j = 1; j <= n; ++j) {
            P[i][j] = (row[j - 1] == 'B') ? 1 : 0;
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            P[i][j] += P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];
        }
    }
    
    while (q--) {
        long long a, b, c, d;
        std::cin >> a >> b >> c >> d;
        a++; b++; c++; d++; // Convert 0-indexed input to 1-indexed
        long long ans = count_B(c, d) - count_B(a - 1, d) - count_B(c, b - 1) + count_B(a - 1, b - 1);
        std::cout << ans << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

E - Set Meal

从数组 $A$ 和 $B$ 中各选一个元素，使得它们的和最大，且选出的下标对 $(i, j)$ 不在给定的禁止列表中。 将两个数组分别排序后，最大的和必然出现在数组末尾。使用最大堆（优先队列）存储候选状态，每次弹出和最大的状态。如果该状态对应的原始下标对合法，则直接输出结果；否则，将其相邻的次大状态（即 $A$ 的下标减一或 $B$ 的下标减一）加入堆中，并使用哈希集合记录已访问状态以避免重复计算。

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

struct State {
    int idx_a, idx_b;
    long long sum;
    bool operator<(const State& other) const {
        return sum < other.sum;
    }
};

void solve() {
    int n, m, l;
    std::cin >> n >> m >> l;
    
    std::vector<std::pair<long long, int>> A(n), B(m);
    for (int i = 0; i < n; ++i) {
        std::cin >> A[i].first;
        A[i].second = i;
    }
    for (int i = 0; i < m; ++i) {
        std::cin >> B[i].first;
        B[i].second = i;
    }
    
    std::vector<std::set<int>> invalid_pairs(n);
    for (int i = 0; i < l; ++i) {
        int u, v;
        std::cin >> u >> v;
        u--; v--; 
        invalid_pairs[u].insert(v);
    }
    
    std::sort(A.begin(), A.end());
    std::sort(B.begin(), B.end());
    
    std::priority_queue<State> pq;
    std::set<std::pair<int, int>> visited;
    
    pq.push({n - 1, m - 1, A[n - 1].first + B[m - 1].first});
    visited.insert({n - 1, m - 1});
    
    while (!pq.empty()) {
        State curr = pq.top();
        pq.pop();
        
        int orig_a = A[curr.idx_a].second;
        int orig_b = B[curr.idx_b].second;
        
        if (invalid_pairs[orig_a].find(orig_b) == invalid_pairs[orig_a].end()) {
            std::cout << curr.sum << "\n";
            return;
        }
        
        if (curr.idx_a > 0 && !visited.count({curr.idx_a - 1, curr.idx_b})) {
            visited.insert({curr.idx_a - 1, curr.idx_b});
            pq.push({curr.idx_a - 1, curr.idx_b, A[curr.idx_a - 1].first + B[curr.idx_b].first});
        }
        if (curr.idx_b > 0 && !visited.count({curr.idx_a, curr.idx_b - 1})) {
            visited.insert({curr.idx_a, curr.idx_b - 1});
            pq.push({curr.idx_a, curr.idx_b - 1, A[curr.idx_a].first + B[curr.idx_b - 1].first});
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

F - Palindrome Query

本题要求支持单点字符修改以及区间回文串查询。由于涉及区间查询和动态修改，线段树是理想的数据结构。 为了高效判断回文，可以在线段树的每个节点中维护该区间的字符串哈希值，包括正序哈希值和逆序哈希值。在合并左右子节点时，正序哈希值的计算方式为：left.hash_forward * base^{right.length} + right.hash_forward；逆序哈希值的计算方式为：right.hash_reverse * base^{left.length} + left.hash_reverse。 在执行区间查询时，提取目标区间的正序和逆序哈希值进行比对。若两者相等，则该区间为回文串。为了有效降低哈希碰撞的概率，建议采用双哈希策略（即使用两组不同的底数和模数）来增强算法的鲁棒性。