codeforce 1700-1900

3.6

Lonely Mountain Dungeons

 算贡献算了半天还错了， 这种采用容斥可以减少细节处理， 代码注释有

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;

void solve() {
    int n, b, x; cin >> n >> b >> x;
    // cout << n << b << x << endl;
    vector<int> a(n + 1);
    map<int, int> mp;
    for (int i = 1; i <= n; i++) cin >> a[i], mp[a[i]]++;
    int maxn = *max_element(a.begin() + 1, a.begin() + 1 + n), ans = 0;

    auto calc = [&](int x, int d) {
        // x 代表人数， d 代表组数
        // 假设全排成一排（ x 个人到 x 组都是一个）
        int ans = x * (x - 1) / 2;
        // t 代表 x 人分为 d 组，每组都有的共同人数
        int t = x / d;
        // del代表有 del 组多出来一个人
        int del = x % d;
        // 1. 那么对于这些人数，我们组内没有贡献的，我们容斥需要减去这些贡献(C(t, 2))
        ans -= d * t * (t - 1) / 2;
        // 2. 有 del 组多出来一个人， 对于多出来的那个人，我们会减少的贡献是他组内的 t 个人
        ans -= del * t;
        return ans * b;
    };

    for (int i = 1; i <= maxn; i++) {
        int sum = -(i - 1) * x;
        // cout << "TEST " << i << endl;
        for (auto [id, v] : mp) {
            if (id <= i) {
                // cout << id << endl;
                sum += id * (id - 1) / 2 * b * v;
                continue;
            }
            sum += v * calc(id, i);
            // cout << v * calc(id, i) << ' ' << id << endl;
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
}   

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int T = 1; cin >> T;
    while (T--) solve();
    // solve();    

    return 0;
}

Microcycle

我们取一颗最大生成树， 那么一条非树边会产生一个环， 我们找到这样一条权值最小的边去 dfs 

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;

const int N = 2e5 + 100;

struct node {
    int x, y, v;
} e[N];

bool cmp(node a, node b) {
    return a.v > b.v;
}

vector<int> g[N];

int fa[N], vis[N];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

vector<int> cir;
void dfs(int x, int t) {
    vis[x] = 1;
    cir.push_back(x);
    if (x == t) {
        cout << cir.size() << endl;
        for (auto i : cir) cout << i << ' ';
        cout << endl;
        return;
    }
    for (auto y : g[x]) {
        if (!vis[y]) dfs(y, t);
    }
    cir.pop_back();
}

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, v; cin >> x >> y >> v;
        e[i] = {x, y, v};
    }
    cir.clear();
    for (int i = 1; i <= n; i++) fa[i] = i, vis[i] = 0, g[i].clear();
    sort(e + 1, e + 1 + m, cmp);
    int minn = INT_MAX / 2, id;
    for (int i = 1; i <= m; i++) {
        auto [x, y, v] = e[i];
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            fa[fx] = fy;
        } else {
            minn = min(minn, v);
            id = i;
        }
    }
    for (int i = 1; i <= m; i++) {
        if (i != id) {
            auto [x, y, v] = e[i];
            g[x].push_back(y);
            g[y].push_back(x);   
        }
    }

    cout << minn << ' ';
    dfs(e[id].x, e[id].y);
}   


signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int T = 1; cin >> T;
    while (T--) solve();

    return 0;
}