T1

题目分析

n名选手各有若干筹码，进行n-1场比赛。每场随机选两人，筹码多的赢（相同则随机），赢家获得输家所有筹码。求哪些选手有非零概率夺冠。

核心观察

一个选手能否夺冠，取决于他能否（通过合理的比赛顺序安排）"吃掉"所有其他选手。由于比赛对手是随机选择的，只要存在一种可行的比赛顺序让该选手最终赢，他就有非零概率夺冠。

关键结论：筹码较小的选手们如果能联合起来（按从小到大的顺序依次合并），他们的总筹码一旦 >= 下一个更大的选手，就可以继续"滚雪球"合并更大的选手。

反过来想：如果前 k 个选手（筹码最小的k个）的筹码总和 < 第 k+1 个选手的筹码数，那么前 k 个选手无论如何联合，最终也打不过第 k+1 个，因此这 k 个选手不可能夺冠。

算法步骤

1. 排序：将选手按筹码数从小到大排序，同时保留原始编号。

2. 前缀和：计算排序后的筹码前缀和数组。

3. 找临界点：从后往前（从大到小）查找最后一个位置 i，使得 prefix[i] < a[i+1].first。

   - 如果找到了这样的 i，说明前 i+1 个选手（筹码最小的那些）加起来也打不过第 i+2 个，因此只有从第 i+1 个选手开始（包含）后面的选手才可能夺冠。

   - 如果一直没找到（prefix始终 >= 下一个），则所有选手都有可能夺冠。

4. 输出：收集符合条件的选手原始编号，按升序排列后输出。

复杂度

• 时间：$O(n log n)$，主要是两次排序（选手排序 + 答案编号排序）

• 空间：$O(n)$，存储排序数组和前缀和

实现细节

• 使用 long long 存储筹码数和前缀和，因为单个筹码可达 $10^9$，总和可达 $2^{14}$，会溢出 int。

• 用 pair 存（筹码数，原始编号），排序时自动按筹码数升序排。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n;
        scanf ("%d", &n);
        vector <pair <ll, int> > a (n);
        for (int i = 0; i < n; i++) {
            scanf ("%lld", &a[i].first);
            a[i].second = i + 1;
        }
        sort (a.begin (), a.end ());
        vector <ll> pre (n);
        pre[0] = a[0].first;
        for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + a[i].first;
        int sta = 0;
        for (int i = n - 2; i >= 0; i--) {
            if(pre[i] < a[i + 1].first) {
                sta = i + 1;
                break;
            }
        }
        vector <int> ans;
        for (int i = sta; i < n; i++) ans.push_back (a[i].second);
        sort (ans.begin (), ans.end ());
        printf ("%d\n", (int) ans.size ());
        for (int i = 0; i < (int) ans.size (); i++) printf ("%d ", ans[i]);
        printf ("\n");
    }
    return 0;
}

T2

显而易见：在森林里加一条边 (u, v) 不形成环，当且仅当 u 和 v 原本不在同一个连通分量里。加边后连通分量数减 1。

题目分析

两个森林都有 n 个节点。每次加边必须同时加到两个森林里，且加完后两个森林都仍是森林（无环）。求最多能加几条边并给出方案。

设第一个森林初始有 c1 个连通分量，第二个有 c2 个连通分量：

• c1 = n - m1

• c2 = n - m2

每加一条合法边，两个森林的连通分量数各减 1。森林最少要有 1 个连通分量（一棵树），所以最多能加的边数为：

答案 = min(c1 - 1, c2 - 1)

关键结论：贪心一定能达到最优

策略：枚举所有边 (u, v)，只要两个森林里 u、v 都不在同一连通分量，就加这条边。

算法步骤

用两个并查集分别维护两个森林的连通关系。

1. 读入初始边，分别在对应并查集里合并。

2. 枚举所有 (u, v)（u < v），若两个并查集中 u、v 都不同根，就加这条边（两个并查集都合并），并记录方案。

3. 输出加边数和方案。

复杂度

• 时间：$O(n^2 · α(n))$，n=1000 时约 $10^6$，足够快。

• 空间：$O(n)$。

实现细节

• 并查集下标 1~n，开 n+1 大小。

• 加边方案的具体边可能不唯一，任意合法方案都正确（我一开始就是没想到这个导致我在这里磨了好久）

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int fa1[N], fa2[N];
int find (int fa[], int x) {
    if (fa[x] == x) return x;
    return fa[x] = find (fa, fa[x]);
}
void hb (int fa[], int x, int y) {
    x = find (fa, x), y = find (fa, y);
    if (x != y) fa[x] = y;
}
int main () {
    int n, m1, m2;
    scanf ("%d%d%d", &n, &m1, &m2);
    for (int i = 1; i <= n; i++) fa1[i] = i, fa2[i] = i;
    for (int i = 0; i < m1; i++) {
        int u, v;
        scanf ("%d%d", &u, &v);
        hb (fa1, u, v);
    }
    for (int i = 0; i < m2; i++) {
        int u, v;
        scanf ("%d%d", &u, &v);
        hb (fa2, u, v);
    }
    vector <pair <int, int> > ans;
    for (int u = 1; u <= n; u++) {
        for (int v = u + 1; v <= n; v++) {
            if (find (fa1, u) != find (fa1, v) && find (fa2, u) != find (fa2, v)) {
                hb (fa1, u, v);
                hb (fa2, u, v);
                ans.push_back ({u, v});
            }
        }
    }
    printf ("%d\n", (int) ans.size ());
    for (int i = 0; i < (int) ans.size (); i++)
        printf ("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}

T3

题目分析

n 个任务，第 i 个完成得 $a_i$ 硬币。每天最多做一个任务；做完某任务后 k 天内不能再做它（即隔 k 天后可重做）。要在 d 天内得到至少 c 个硬币，求最大的 k。

贪心策略（固定 k 时如何最大化硬币）

把任务奖励从大到小排序。冷却 k 天意味着：一个任务做完后，要再过 k 天才能重做，所以每个 (k+1) 天的周期里，同一个任务最多做一次。

于是一个周期里最多做 m = min(n, k+1) 个不同任务，取最大的 m 个，总奖励记为 S = pref[m]（前缀和）。

d 天分成：

• 完整周期数 cyc = d / (k+1)

• 剩余天数 rem = d % (k+1)

总奖励 = cyc * S + pref[min(m, rem)]（剩余天数里做前 min(m, rem) 个最大的）。

单调性 → 二分答案

设 f(k) 为冷却 k 时 d 天最多能得的硬币。k 越大限制越严，f(k) 单调不增。因此满足 f(k) ≥ c 的 k 是一个前缀 [0, K]，用二分找最大 K。

三种边界情况

1. Infinity：k 任意大时每个任务最多做一次，最多得 pref[min(n, d)]。若它 ≥ c，则 k 可任意大。

2. Impossible：k=0 时每天都能做最大任务，最多得 d * max(a)。若它 < c，则任何 k 都不可能。

3. 普通情况：已知 f(0) ≥ c 且 f(∞) < c，二分 k ∈ [0, d]。

   - 上界取 d：因为 check(d) 时 cyc=0、rem=d，结果就是 pref[min(n,d)] = f(∞) < c，必为 false，可作为合法上界。

复杂度

• 时间：$O(n log n + log d)$，每个测试用例排序 + 二分

• 空间：$O(n)$

实现细节

• 千万不要用__int128，会后悔的（我在这里看了好久的CE结果发现不能用__int128）

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        ll n, c, d;
        scanf ("%lld%lld%lld", &n, &c, &d);
        vector <ll> a (n);
        for (int i = 0; i < n; i++) scanf ("%lld", &a[i]);
        sort (a.begin (), a.end (), greater <ll> ());
        vector <ll> pre (n + 1, 0);
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
        ll best = pre[min (n, d)];
        if (best >= c) {
            puts ("Infinity");
            continue;
        }
        if (d * a[0] < c) {
            puts ("Impossible");
            continue;
        }
        ll l = 0, r = d, ans = 0;
        while (l <= r) {
            ll k = (l + r) / 2;
            ll m = min (n, k + 1);
            ll S = pre[m];
            ll cyc = d / (k + 1);
            ll rem = d % (k + 1);
            ll tot = cyc * S + pre[min (m, rem)];
            if (tot >= c) ans = k, l = k + 1;
            else r = k - 1;
        }
        printf ("%lld\n", ans);
    }
    return 0;
}

T4

题目思路

题意

依次击杀n个怪物，我攻击力a，对手b。战斗循环：我攻击→（可消耗技巧跳过对手）→对手攻击。最多k次跳过，求最大得分（我击杀怪物数量）。

关键观察

一轮完整无跳过回合总伤害 s = a + b。对于怪物$h_i$，先对s取模：$rem = h_i$如果rem等于0，说明最后是对手打死怪物，rem赋值为s。rem代表：打完若干完整回合之后怪物剩余血量。

1. 如果 rem ≤ a：我一次攻击直接打死，不需要技巧，直接得分。
2. 如果 rem > a：我第一下打不死，需要多次出手；每多出手一次，就必须消耗1次技巧跳过对手回合。

• 需要总出手次数：total_hit = ceil(rem / a) = (rem + a - 1)/a
• 需要技巧次数 cost = total_hit - 1，减去我固有的第一次出手。

贪心

收集所有怪物的cost，从小到大排序。优先消耗最少的技巧拿下怪物。依次遍历，k足够就拿分，k减去cost；k不足停止。

复杂度

• $O(n log n)$，n最大2e5，满足数据范围。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int n;
    ll a, b, k;
    scanf ("%d%lld%lld%lld", &n, &a, &b, &k);
    ll s = a + b;
    vector <ll> h (n);
    for (int i = 0; i < n; i++) scanf ("%lld", &h[i]);
    vector <ll> cost;
    ll ans = 0;
    for (ll hi : h) {
        ll rem = hi % s;
        if (rem == 0) rem = s;
        if (rem <= a) ans ++;
        else {
            ll tot = (rem + a - 1) / a;
            cost.push_back (tot - 1);
        }
    }
    sort (cost.begin (), cost.end ());
    for (ll c : cost) {
        if (k >= c) {
            ans ++;
            k -= c;
        }
        else break;
    }
    printf ("%lld\n", ans);
    return 0;
}

T5

题目思路

题意

n天股票，每天最多买1股、卖1股或者不操作。不能裸卖空。初始和结束都不能持有股票，求最大收益。

算法：小根堆贪心

核心思想：尽可能低买高卖，使用优先队列维护历史价格。遍历每一天价格$p_i$：

1. 将$p_i$放入小根堆。

2. 如果堆顶（历史最小价格）小于 $p_i$：

• 执行交易：以堆顶价格买入，$p_i$价格卖出，收益 $+= p_i$堆顶。

• 弹出堆顶；再次把$p_i$压入堆。

  再次压入$p_i$的意义：允许“撤销本次卖出”，相当于今天不卖出，改为今天买入，留给后面更高的价格卖出，实现多次复用同一天价格。

正确性说明

这个堆模型等价于维护可选择的买入候选。二次入堆是算法的精髓，模拟把今天作为买入点留给未来。算法自动满足：持仓不会为负，最终结束持仓为0。

复杂度

每个元素最多入堆出堆各两次，$O(n log n)，n≤3e5$可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int n;
    scanf ("%d", &n);
    priority_queue <ll, vector <ll>, greater <ll> > q;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll x;
        scanf ("%lld", &x);
        q.push (x);
        if (q.top () < x) {
            ans += x - q.top ();
            q.pop ();
            q.push (x);
        }
    }
    printf ("%lld\n", ans);
    return 0;
}

T6

题目思路

博弈模型

每个位置是博弈状态，只能向a值更大的格子转移，DAG无环。win[i]=true：当前玩家必胜(A)；win[i]=false必败(B)。

• 必胜态（Plyer 先手可以赢，win [i]=true，A）：当前轮到你走，存在至少一种走法，把对手扔到必败态。

• 必败态（win [i]=false，B）：当前轮到你走，你所有可以走的下一步，全部都是对手的必胜态；无论你怎么走，对手都能赢。转移规则：如果存在至少一个后继j，使得win[j]=false，则win[i]=true；否则win[i]=false。

排序处理

因为只能走到a更大的点，我们把所有位置按照a[i]从大到小排序。数值最大的点没有后继，win直接等于false（B）。按a从大往小遍历，计算每个位置i的胜负：步长d = a[i]，枚举i所有d倍数偏移的格子j（i±d,i±2d…）。只要找到任意一个j，满足 a[j]>a[i] 并且 win[j]==false，那么i就是必胜，不用继续找。

复杂度

对于每个i，枚举倍数，总次数是 $n/1 + n/2 + n/3+… = O(n log n)$，$n≤10^5$完全可过。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int n;
    scanf ("%d", &n);
    vector <int> a (n);
    vector <int> pos (n + 1);
    for (int i = 0; i < n; i++) {
        scanf ("%d", &a[i]);
        pos[a[i]] = i;
    }
    vector <bool> win (n, false);
    for (int val = n; val >= 1; val--) {
        int i = pos[val];
        int d = a[i];
        bool ok = false;
        for (int j = i + d; j < n && !ok; j += d) {
            if (a[j] > a[i] && !win[j]) ok = true;
        }
        for (int j = i - d; j >= 0 && !ok; j -= d) {
            if (a[j] > a[i] && !win[j]) ok = true;
        }
        win[i] = ok;
    }
    string s;
    for (int i = 0; i < n; i++) s += win[i] ? 'A' : 'B';
    cout << s << endl;
    return 0;
}