An overnight dance in discotheque

有两点，找到最小的能包含这个点的作为父节点，避免出现一个不是树的东西
用递归的方式写，将子节点的所有状态统合起来，再由此考虑当前节点

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<array<ll, 3>> c(n);
    for (auto &i : c) {
        for (auto &j : i) {
            cin >> j;
        }
    }

    vector<vector<int>> adj(n);
    vector<int> root(n);

    for (int i = 0; i < n; i ++) {
        auto [x, y, r] = c[i];
        root[i] = -1;
        for (int j = 0; j < n; j ++) {
            auto [a, b, R] = c[j];
            if (R > r && R * R > (x - a) * (x - a) + (y - b) * (y - b)) {
                if (root[i] == -1 || c[root[i]][2] > R) {
                    root[i] = j;
                }
            }
        }
        if (~root[i]) adj[root[i]].push_back(i);
    }

    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(2, vector<ll>(2)));
    // 还未选择此节点的时候，两堆的奇偶性
    // 表示从根节点到 u 的路径上，分配到组0的祖先节点（不包括 u 自身）的个数的奇偶性
    auto dfs = [&](auto self, int u)->void {
        ll g[2][2] = {{0}};

        for (auto &v : adj[u]) {
            self(self, v);
            for (int i = 0; i < 2; i ++) {
                for (int j = 0; j < 2; j ++) {
                    g[i][j] += dp[v][i][j];
                }
            }
        }

        for (int i = 0; i < 2; i ++) {
            for (int j = 0; j < 2; j ++) {
                // 由如果选择之后，可能的奇偶性的值状态转移过来
                dp[u][i][j] = max(
                    g[i ^ 1][j] + c[u][2] * c[u][2] * (i? -1: 1),
                    g[i][j ^ 1] + c[u][2] * c[u][2] * (j? -1: 1)
                );
            }
        }
    };

    long long ans = 0;
    for (int i = 0; i < n; i ++) {
        if (root[i] == -1) {
            dfs(dfs, i);
            ans += dp[i][0][0];
        }
    }

    ld PI = acos(-1.0);
    cout << fixed << setprecision(8) << (ld)ans * PI << '\n';

    return 0;
}

Queue

非常明显，可以离散化然后线段树，或者线段树优先右边搜索

让人忽略了还有维护后缀最小值然后二分的方法

Slime

考虑了一下，如果最后剩余两个，其中一个最好尽可能的小，然后让另一个减它。

找到一个方法：枚举每个点作为最后被减的数，那么让左右尽可能小，如果有负数，把正数都同化入负数，最后都减入那个最后被减的数。如果都是正数，让其它的数都减入最小的正数，然后再计算。

实际上有O(n)预处理前后缀是否都是正数来算，但线段树可以找最小值然后算，就是写的多了点

Vanya and Triangles

乍一看挺唬人的，但从样例给的解释的中有了端倪。

它给了三个点来表示三角形，那么是不是可以用从n个点中选3个点的个数来表示可能的三角形的总数呢，再排除掉共线的三个点的个数，就是正确答案。

枚举比i大的点，斜率相同的线有k条，那么对应了k个点，从中选两个k * (k - 1) / 2，就是与点i共线的三个点的个数，枚举每个点i，求和

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2010;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<array<int, 2>> a(n);
    for (auto &i : a) {
        for (auto &j : i ) {
            cin >> j;
        }
    }

    ll ans = 1ll * n * (n - 1) * (n - 2) / 6;
    vector<int> st(n);

    auto get = [&](int i, int j) ->ld {
        if (a[j][0] == a[i][0]) return 1e18;
        return (ld)1.0 * (a[j][1] - a[i][1]) / (a[j][0] - a[i][0]);
    };

    for (int i = 0; i < n; i ++) {
        map<ld, int> cnt;
        for (int j = i + 1; j < n; j ++) {
            cnt[get(i, j)] ++;
        }
        for (auto [x, y] : cnt) {
            ans -= y * (y - 1) / 2;
        }
    }

    cout << ans << '\n';

    return 0;
}