A - Calendar

在题目设定的历法中，每个月固定为 30 天，每年固定为 360 天。给定两个日期以及第一个日期对应的星期，求第二个日期的星期。

解题思路：

计算两个日期之间相差的总天数。设起始日期为 $(y_1, m_1, d_1)$，目标日期为 $(y_2, m_2, d_2)$，总天数差 $\Delta D$ 可由下式得出：

total_days = (y2 - y1) * 360 + (m2 - m1) * 30 + (d2 - d1)

由于一周只有 5 天，将总天数对 5 取模，并根据起始星期进行偏移即可。注意处理负数取模的情况。

#include <iostream>
#include <string>
#include <map>

using namespace std;

string week_names[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};

void solve() {
    long long y1, m1, d1, y2, m2, d2;
    string start_week;
    cin >> y1 >> m1 >> d1 >> start_week >> y2 >> m2 >> d2;

    int start_idx = 0;
    for (int i = 0; i < 5; ++i) {
        if (week_names[i] == start_week) start_idx = i;
    }

    long long diff = (y2 - y1) * 360 + (m2 - m1) * 30 + (d2 - d1);
    int target_idx = ((start_idx + diff) % 5 + 5) % 5;
    cout << week_names[target_idx] << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

C - Wandering Robot

机器人根据长度为 $n$ 的指令序列移动，该序列会重复执行 $k$ 轮。求机器人在整个过程中离原点的最大曼哈顿距离。

解题思路：

设一轮指令后机器人的位移为 $(\Delta x, \Delta y)$。在第 $m$ 轮结束时，机器人的位置是 $(m \cdot \Delta x, m \cdot \Delta y)$。对于每一轮中的第 $i$ 步，其坐标可以表示为 $((m-1) \cdot \Delta x + x_i, (m-1) \cdot \Delta y + y_i)$，其中 $(x_i, y_i)$ 是第一轮第 $i$ 步的坐标。

由于曼哈顿距离函数 $|x| + |y|$ 是凸函数，最大值一定在第一轮或最后一轮（第 $k$ 轮）的某个位置取得。因此，我们只需要模拟第一轮的所有位置以及最后一轮的所有位置，记录其中的最大距离即可。时间复杂度为 $O(n)$。

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

void solve() {
    int n;
    ll k;
    string s;
    cin >> n >> k >> s;

    ll cur_x = 0, cur_y = 0;
    ll max_dist = 0;

    // 记录单轮位移
    for (char c : s) {
        if (c == 'U') cur_y++;
        else if (c == 'D') cur_y--;
        else if (c == 'L') cur_x--;
        else if (c == 'R') cur_x++;
        max_dist = max(max_dist, abs(cur_x) + abs(cur_y));
    }

    ll total_dx = cur_x, total_dy = cur_y;
    // 检查第 k 轮的情况
    cur_x = total_dx * (k - 1);
    cur_y = total_dy * (k - 1);
    max_dist = max(max_dist, abs(cur_x) + abs(cur_y));

    for (char c : s) {
        if (c == 'U') cur_y++;
        else if (c == 'D') cur_y--;
        else if (c == 'L') cur_x--;
        else if (c == 'R') cur_x++;
        max_dist = max(max_dist, abs(cur_x) + abs(cur_y));
    }

    cout << max_dist << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

E - BaoBao Loves Reading

给定一个阅读序列，书架容量为 $k$。如果书不在书架上，则产生一次代价。求对于不同的 $k \in [1, n]$，最小的代价总和。

解题思路：

这是一个经典的 LRU 缓存问题变体。对于当前阅读的书籍 $a_i$，如果它之前在位置 $lst_i$ 出现过，那么当且仅当区间 $[lst_i + 1, i - 1]$ 之间不同书籍的数量小于 $k$ 时，这本书才可能留在书架上（从而不产生额外代价）。

我们可以统计每个位置 $i$ 对应的"区间不同元素个数" $d_i$。对于每一个 $k$，如果 $d_i < k$，则第 $i$ 次阅读不需要支付代价。这可以转化为：对于每一个位置 $i$，它对所有 $k > d_i$ 的答案贡献为 $0$，对 $k \le d_i$ 的答案贡献为 $1$。利用树状数组维护区间不同元素个数，通过离线处理即可求出所有 $k$ 的结果。

F - Stones in the Bucket

有 $n$ 个桶，每个桶里有一定数量的石头。你可以执行两种操作：从某个桶中移除一个石头，或者将一个石头从一个桶移动到另一个桶。目标是使所有非空桶的石头数量相等。求最少操作次数。

解题思路：

假设最终所有桶（如果保留）的高度为 $H$。为了使操作最少，我们显然应该让总的石头减少量尽可能小。设总石头数为 $S$，桶的数量为 $n$。$H$ 的取值范围在 $[0, \max(a_i)]$ 之间。

对于给定的 $H$，计算所有高于 $H$ 的桶多出的石头总量 $over = \sum \max(0, a_i - H)$，以及低于 $H$ 的桶缺少的石头总量 $under = \sum \max(0, H - a_i)$。 如果 $over \ge under$，说明可以通过移动 $under$ 个石头并移除 $over - under$ 个石头来达到目标，总代价为 $over$。 我们可以发现，代价函数关于 $H$ 具有单峰性质（或者通过二分 $H$ 找到可行的最大高度）。

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

using namespace std;

typedef long long ll;

ll check(const vector<ll>& a, ll h, int n) {
    ll up = 0, down = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] > h) up += a[i] - h;
        else down += h - a[i];
    }
    if (up >= down) return up;
    return -1;
}

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum_val = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum_val += a[i];
    }

    ll left = 0, right = 1e9 + 7, best_h = 0;
    while (left <= right) {
        ll mid = left + (right - left) / 2;
        if (check(a, mid, n) != -1) {
            best_h = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << check(a, best_h, n) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

H - Tokens on the Segments

给定 $n$ 个区间 $[l_i, r_i]$，每个区间内可以放置一个令牌，每个位置只能放一个令牌。问最多能放置多少个令牌。

解题思路：

这是一个典型的贪心问题。我们将所有区间按左端点 $l$ 从小到大排序。遍历时间轴（或每一个可能的 $l$），对于当前可选的所有区间（即 $l_i \le \text{current\_time}$），我们应该优先选择右端点 $r_i$ 最小的区间放置令牌，因为它的"时效性"最紧迫。

使用优先队列维护当前可用的区间的右端点，每次取出最小的 $r$ 即可。

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

using namespace std;

struct Node {
    int l, r;
    bool operator<(const Node& other) const {
        return l < other.l;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<Node> segments(n);
    for (int i = 0; i < n; ++i) cin >> segments[i].l >> segments[i].r;
    sort(segments.begin(), segments.end());

    priority_queue<int, vector<int>, greater<int>> pq;
    int count = 0;
    int cur_pos = 0;
    int i = 0;

    while (i < n || !pq.empty()) {
        if (pq.empty()) cur_pos = segments[i].l;
        while (i < n && segments[i].l <= cur_pos) {
            pq.push(segments[i].r);
            i++;
        }
        
        while (!pq.empty() && pq.top() < cur_pos) pq.pop();
        
        if (!pq.empty()) {
            pq.pop();
            count++;
            cur_pos++;
        }
    }
    cout << count << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}