小白月赛90

A 小 A 的文化节

void solve() {
    int n, m;cin >> n >> m;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    int ans = 0;
    while (m--) {
        int x;cin >> x;ans += a[x];
    }
    cout << ans << '\n';
}

B 小 A 的游戏

小 A 和小 B 在玩一个游戏，每局游戏的结果可能有胜平负三种。游戏的胜者得到 3 分，败者不得分，若打平则双方都得1分。

现在他们进行了若干局游戏，比分记录着小 A 为 X 分，小 B 为 Y 分。判断一下此时的比分是否合法吧。

void solve() {
    int x, y;cin >> x >> y;
    if ((x % 3) == (y % 3)) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

C 小 A 的数字

小 A 给定一个数字 n，请你帮她找出从低位对齐后任意一位均与 n 对应数位不同的最小正整数。

对于本题题面描述中的从低位对齐后任意一位均与 n 对应数位不同，你需要保证你所输出的答案的位数小于 n 的位数时，即使在添加前导零至与 n 的位数相同后，也不应有任意一位的数字两两相同。

void solve() {
    string s, ans = "";cin >> s;
    int idx = 0;
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '0') {
            idx = i;break;
        }
    }
    for (int i = idx;i < s.size();i++) {
        for (int j = 0;j < 10;j++) {
            if (s[i] - '0' != j) {
                ans += j + '0';break;
            }
        }
    }
    int res = stoi(ans);
    if (!res)res = 1;
    if (!idx) {
        if (s[s.size() - 1] == '1')res = 2;
    }
    cout << res << '\n';
}

D/F 小 A 的线段

在一个标有 1-n 的数轴上给定 m 条线段，第 i 个线段的左右端点分别为 sti , edi，求有多少种线段的选择方案可以使得数轴上的每个整数点至少被覆盖两次。

定义两种选择方案不同当且仅当至少有一个线段在两种方案中的状态（选/不选）不同。

• easy: $m\le 10$
• hard: $m\le 200$

Easy

显然 DFS

int a[100010];
void solve() {
    int n, m;cin >> n >> m;
    vector<pair<int, int>> s(m + 1);
    for (int i = 1;i <= m;i++) {
        cin >> s[i].first >> s[i].second;
    }
    int ans = 0;
    auto dfs = [&](auto self, int x) -> void {
        if (x > m) {
            int cnt = 0;
            for (int i = 1;i <= n;i++) {
                if (a[i] >= 2) {
                    cnt++;
                }
            }
            if (cnt == n) {
                ans++;
            }
            return;
        }

        for (int i = s[x].first;i <= s[x].second;i++)a[i]++;
        self(self, x + 1);
        for (int i = s[x].first;i <= s[x].second;i++)a[i]--;
        self(self, x + 1);
        };
    dfs(dfs, 1);
    cout << ans << '\n';
}

Hard

DP
(待更 $\dots$)

E 小 A 的任务

小 A 现在需要完成有序的任务。A 类任务和 B 类任务各 $n$ 个，初始时只有第一个 A 类任务可以进行。进行第 $i$ 个 A 类任务需在完成第 $i-1$ 个 A 类任务之后，进行第 $i$ 个 B 类任务需要在完成第 $i$ 个 A 类任务之后。且在同一时刻只能进行 A 类和 B 类中的一类任务，同一类的任务只能同时进行一个，任何一个任务都至多完成一次。

总共有 $q$ 次询问，每次询问你需要回答完成 $k$ 个 B 类任务至少需要多长时间。

使用堆，太妙了。

#define int long long
void solve() {
    int n, q;cin >> n >> q;vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];
    while (q--) {
        int k;cin >> k;
        int ans = 1e18, res = 0;
        priority_queue<int>q;
        for (int i = 1;i <= n;i++) {
            res += a[i] + b[i];q.push(b[i]);
            if (q.size() > k)res -= q.top(), q.pop();
            if (q.size() == k)ans = min(ans, res);
        }
        cout << ans << '\n';
    }
}