A. 最小二进制数

给定一个仅包含字符 '0' 和 '1' 的正确二进制字符串 s。定义两种操作：

1. 交换任意一对相邻字符，例如 "101" → "110"；
2. 将子串 "11" 替换为 "1"，例如 "110" → "10"。

目标是通过若干次上述操作（可为零次），得到数值最小的正确二进制字符串。所谓"正确"是指无前导零（除非数字本身就是 0）。

分析：注意到操作 2 可以合并连续的 '1'，而操作 1 允许 '0' 和 '1' 相对移动。最终最优形式应为一个 '1' 后接所有 '0'（若存在至少一个 '1'）。若原串全为 '0'，则结果就是 "0"。

因此，只需统计 '0' 的个数，若存在 '1'，输出 "1" 加上相应数量的 '0'；否则输出 "0"。

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    int zeros = 0, ones = 0;
    for (char c : s) {
        if (c == '0') zeros++;
        else ones++;
    }
    if (ones == 0) {
        cout << "0\n";
    } else {
        cout << "1";
        for (int i = 0; i < zeros; i++) {
            cout << "0";
        }
        cout << "\n";
    }
    return 0;
}

B. 劳拉的路径坐标

劳拉在一个 n 行 m 列的网格中按特定蛇形路径移动。起始点为 (1, 1)，先垂直向下走到 (n, 1)，然后向右到 (n, m)，再向上一格，向左到第 2 列，再向上一格，重复此横向来回模式，直到所有格子访问完毕。已知她进行了 k 次移动（从 0 开始计数），求其最终位置。

分析：路径分为两部分。第一部分是从 (1,1) 到 (n,1)，共 n-1 次移动。当 k < n 时，位置为 (k+1, 1)。之后进入蛇形阶段，每层（行）需要 2*(m-1) 步完成左右移动（除首列外）。通过计算当前处于第几层及在该层内的偏移量，可确定坐标。

#include <cstdio>
using namespace std;

int main() {
    long long n, m, k;
    scanf("%lld %lld %lld", &n, &m, &k);
    if (k < n) {
        printf("%lld 1\n", k + 1);
        return 0;
    }
    k -= n; // 剩余步数
    long long layer = k / (m - 1); // 所处层级（从底部开始）
    long long offset = k % (m - 1); // 当前层内偏移
    long long row = n - layer;
    long long col;
    if (layer % 2 == 0) {
        col = 2 + offset;
    } else {
        col = m - offset;
    }
    printf("%lld %lld\n", row, col);
    return 0;
}

C. 区间嵌套查找

给定 n 个区间 [l_i, r_i]，需找出两个不同索引 i 和 j，使得区间 i 完全包含于区间 j 中（即 l_i ≥ l_j 且 r_i ≤ r_j）。若不存在，返回 -1 -1。

分析：将区间按左端点升序排序，若左端点相同则按右端点降序排列。这样处理后，对于任意位置 i，所有可能包含它的候选区间均位于其前面。遍历过程中维护此前遇到的最大右端点，若当前区间的右端点不超过该最大值，则找到一组解。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct Segment {
    int l, r, idx;
    bool operator<(const Segment& other) const {
        return l != other.l ? l < other.l : r > other.r;
    }
};

int main() {
    int n;
    scanf("%d", &n);
    vector<Segment> segs(n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &segs[i].l, &segs[i].r);
        segs[i].idx = i + 1;
    }
    sort(segs.begin(), segs.end());
    int maxRight = 0;
    for (int i = 0; i < n; i++) {
        if (segs[i].r <= maxRight) {
            printf("%d %d\n", segs[i].idx, segs[i].l == segs[i-1].l ? segs[i-1].idx : segs[i-1].idx);
            return 0;
        }
        maxRight = max(maxRight, segs[i].r);
    }
    printf("-1 -1\n");
    return 0;
}

E. 游戏技能优化

有 n 个生物，每个具有生命值 hp_i 和伤害 dmg_i。有两种法术：

1. 最多使用 a 次：使某生物 hp 翻倍（可多次作用于同一单位）；
2. 最多使用 b 次：将某生物的伤害设为其当前生命值。

求使用这些法术后，所有生物总伤害的最大值。

分析：第二种法术（赋值类）的效果取决于当前生命值。优先考虑对 (hp - dmg) 差值大的单位使用法术 2。首先计算不使用任何法术的基础总伤害。接着，在最多 b 个单位上应用法术 2，选择增益最大的。对于法术 1，由于最多仅 a 次（a ≤ 20），可考虑将其全部用于某个单位以最大化其 hp，从而增强法术 2 的效果。枚举是否将所有 a 次翻倍应用于某个本已计划施放法术 2 的单位，或是一个尚未被选中的单位，取最优解。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

struct Creature {
    ll hp, dmg;
};

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    vector<Creature> creatures(n);
    ll baseDamage = 0;
    for (int i = 0; i < n; i++) {
        cin >> creatures[i].hp >> creatures[i].dmg;
        baseDamage += creatures[i].dmg;
    }

    if (b == 0) {
        cout << baseDamage << endl;
        return 0;
    }

    // 计算每只生物使用法术2的潜在增益
    vector<pair<ll, int>> gains;
    for (int i = 0; i < n; i++) {
        gains.push_back({max(creatures[i].hp - creatures[i].dmg, 0LL), i});
    }
    sort(gains.rbegin(), gains.rend());

    ll maxGain = 0;
    ll multiplier = 1LL << a; // hp 翻倍 a 次后的倍数

    // 情况1：不使用额外翻倍，仅用 b 次法术2
    for (int i = 0; i < min(b, n); i++) {
        maxGain += gains[i].first;
    }

    // 情况2：尝试将所有 a 次翻倍用在某个单位上
    for (int i = 0; i < n; i++) {
        ll newHp = creatures[i].hp * multiplier;
        ll potentialGain = max(newHp - creatures[i].dmg, 0LL);
        ll currentGain = 0;
        int used = 0;
        // 贪心选择其他增益最高的 b-1 个单位
        for (int j = 0; j < n && used < b; j++) {
            int idx = gains[j].second;
            if (idx == i) continue; // 预留位置给当前单位
            currentGain += gains[j].first;
            used++;
        }
        if (used < b) {
            currentGain += potentialGain;
        } else {
            // 若已有 b 个，需替换掉增益最小的一个
            ll minGain = potentialGain;
            for (int j = 0; j < n && minGain > 0 && used == b; j++) {
                int idx = gains[j].second;
                if (idx == i) continue;
                ll g = gains[j].first;
                if (g < minGain) {
                    minGain = g;
                    break;
                }
            }
            if (potentialGain > minGain) {
                currentGain = currentGain - minGain + potentialGain;
            }
        }
        maxGain = max(maxGain, currentGain);
    }

    cout << baseDamage + maxGain << endl;
    return 0;
}