A. USB Driver

脑抽了居然升序排序。。愣了几秒才发现

一遍 AC。

const int MAXN = 100 + 10;
 
int n, aa[MAXN];
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    int m; cin >> m;
    rep (i, 1, n) cin >> aa[i];
    std::sort(aa + 1, aa + 1 + n, std::greater<int>());
    rep (i, 1, n) {
        aa[i] += aa[i - 1];
        if (aa[i] >= m) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

B. The Best Gift

一遍 AC。

const int MAXN = 2e5 + 10;
 
int n, m, cnt[10 + 1];
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    rep (i, 1, n) {
        int x; cin >> x;
        ++cnt[x];
    }
    lli ans = 0;
    rep (x, 1, 10) {
        rep (y, x + 1, 10) {
            ans += cnt[x] * cnt[y];
        }
    }
    cout << ans << endl;
}

C. Load Balancing

直接猜结论：平均分配最优，差至多为 1.

信仰之跃，一遍 AC。

const int MAXN = 1e5 + 10;
 
int n, m;
int aa[MAXN];
int bb[MAXN];
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    rep (i, 1, n) cin >> aa[i];
    std::sort(aa + 1, aa + 1 + n);
    int sum = 0;
    rep (i, 1, n) sum += aa[i];
    int avg = sum / n, ext = sum % n;
    rep (i, 1, n) {
        bb[i] = avg; if (ext) { ++bb[i], --ext; }
    }
    std::sort(bb + 1, bb + 1 + n);
    lli ans = 0;
    rep (i, 1, n) ans += std::abs(aa[i] - bb[i]);
    cout << (ans + 1) / 2 << endl;
    return 0;
}

D. Gadgets for dollars and pounds

场上读错题 + 被降智，以为不能二分，无奈跳过了先做 E。

Practice 的时候被二次降智，有个地方没开 long long 结果爆了，输出方案也写爆了，换了题解的方法才过，至今不知道是为什么。

#错误警示：没开 long long 见祖宗。

const int MAXN = 2e6 + 10;
 
int n, m, k; lli s;
lli aa[MAXN], bb[MAXN];
int mca[MAXN], mcb[MAXN];
int type[MAXN];
struct IT { int id; lli cost; int day; } dollar[MAXN], pound[MAXN];
lli dls, pds;
bool cmp(IT x, IT y) { return x.cost < y.cost; }
static IT items[MAXN];
 
bool check(int mid) {
    lli cdl = aa[mca[mid]], cpd = bb[mcb[mid]];
//    DEBUG(cdl); DEBUG(cpd);
    
    int cnt = 0;
    rep (i, 1, dls) items[++cnt] = {dollar[i].id, dollar[i].cost * cdl, mca[mid]};
    rep (i, 1, pds) items[++cnt] = {pound[i].id, pound[i].cost * cpd, mcb[mid]};
    std::sort(items + 1, items + 1 + cnt, cmp);
 
    lli total = 0;
    rep (i, 1, k) {
        total += items[i].cost;
//        DEBUG(items[i].cost);
    }
//    DEBUG(total);
    return total <= s;
}
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k >> s;
    rep (i, 1, n) {
        cin >> aa[i];
        if (i == 1 || aa[mca[i - 1]] > aa[i]) mca[i] = i;
        else mca[i] = mca[i - 1];
    }
    rep (i, 1, n) {
        cin >> bb[i];
        if (i == 1 || bb[mcb[i - 1]] > bb[i]) mcb[i] = i;
        else mcb[i] = mcb[i - 1];
    }
    rep (i, 1, m) {
        int typ, cost; cin >> typ >> cost;
        type[i] = typ;
        if (typ == 1) dollar[++dls] = {i, cost};
        else pound[++pds] = {i, cost};
    }
 
    int l = 1, r = n, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    if (ans == -1) cout << -1 << endl;
    else {
        check(ans);
        cout << ans << endl;
        for (int i = 1; i <= k; ++i) {
        	cout << items[i].id << ' ' << items[i].day <<endl;
        }
    }
    return 0;
}

E. Minimum spanning tree for each edge

学过次小生成树的人都会做。

交了 3 发才过。第一发是因为没开 long long，第二发是因为数组开得太紧了（理论上应该不会溢出啊？但是它确实挂了，我也不知道为什么）

const int MAXN = 2e5 + 10;
 
struct E {int v, w;};
struct RE {int u, v, w, chosen, id;} res[MAXN];
bool cmp(RE x, RE y) { return x.w < y.w; }
 
int n, m;
std::vector<E> G[MAXN];
lli anss[MAXN];
 
struct DSU {
    int fa[MAXN];
 
    int Find(int x) {
        return !fa[x] ? x : fa[x] = Find(fa[x]);
    }
    bool Merge(int x, int y) {
        x = Find(x); y = Find(y);
        if (x == y) return false;
        fa[x] = y; return true;
    }
} dsu;
 
lli kruskal() {
    lli ans = 0;
    std::sort(res + 1, res + 1 + m, cmp);
    int cnt = 0;
    rep (i, 1, m) {
        if (dsu.Merge(res[i].u, res[i].v)) {
            ++cnt; ans += res[i].w;
            res[i].chosen = true;
        }
        if (cnt == n - 1) break;
    }
    return ans;
}
 
int fa[MAXN][25], mx[MAXN][25];
int dep[MAXN];
const int MXL = 19;
void dfs(int u, int f) {
    fa[u][0] = f;
    dep[u] = dep[f] + 1;
    for (int i = 1; i <= 19; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        mx[u][i] = std::max(mx[u][i - 1], mx[fa[u][i - 1]][i - 1]);
    }
    forall (G[u], i) {
        int v = G[u][i].v, w = G[u][i].w;
        if (v == fa[u][0]) continue;
        mx[v][0] = w;
        dfs(v, u);
    }
}
int Get(int x, int y) {
    if (dep[x] < dep[y]) {
        std::swap(x, y);
    } int ans = 0;
    for (int k = 19, delta = dep[x] - dep[y]; k >= 0; --k) {
        if ((delta >> k) & 1) {
            ans = std::max(ans, mx[x][k]);
            x = fa[x][k];
        }
    } if (x == y) return ans;
    for (int k = 19; k >= 0; --k) {
        if (fa[x][k] != fa[y][k]) {
            ans = std::max({ans, mx[x][k], mx[y][k]});
            x = fa[x][k], y = fa[y][k];
        }
    }
    return std::max({ans, mx[x][0], mx[y][0]});
}
 
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    rep (i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        res[i] = {u, v, w, false, i};
    }
    lli ans = kruskal();
    rep (i, 1, m) {
        if (res[i].chosen) {
            anss[res[i].id] = ans;
            G[res[i].u].push_back({res[i].v, res[i].w});
            G[res[i].v].push_back({res[i].u, res[i].w});
        }
    }
    dfs(1, 0);
    rep (i, 1, m) {
        if (res[i].chosen) continue;
        int u = res[i].u, v = res[i].v;
        lli mxw = Get(u, v);
        anss[res[i].id] = ans - mxw + 1ll * res[i].w;
    }
    rep (i, 1, m) cout << anss[i] << endl;
    return 0;
}