# B

# 题目大意

给定 $n$ 个数 $a_1,...,a_n$ ，求最大的非负整数 $x$ ， $x$ 需要满足

$\sum\limits_{i=1}^{n} [a_i \ge x] \ge x$

# 数据范围

$1 \le n \le 100$
$0 \le a_i \le 10^9$

# 题解

$x$ 最大不会超过 $n$ ，因为是计数问题，最多个数也只能是 $n$ ，所以倒着枚举 $x$ 即可

c++

void solve () {
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)    cin >> a[i];

    for (int i = n; i >= 0; i--) {
        int cnt = 0;
        for (int j = 1; j <= n; j++)    if (a[j] >= i)  cnt++;
        if (cnt >= i) {
            cout << i << '\n';
            return;
        }
    }
}

# C

# 题目大意

有一个周长为 $L$ 的圆，圆周上有 $N$ 个点，第 $i + 1$ 个点，位于从第 $i$ 个点顺时针走 $d_i$ 距离的位置，请你统计满足以下条件三元组的个数

$a, b, c$ 互不相同
以 $a,b,c$ 为顶点的三角形是正三角形

# 数据范围

$3 \le L, N \le 3 \times 10^5$
$0 \le d_i \le L$
输入均为整数

# 题解

显然，只有当 $L$ 是 $3$ 的倍数时，才有可能有等边三角形出现
我们不妨记录一个 $cnt$ 数组，第一个位置随便选，选 $0$ 位置即可，记录圆上各位置出现点的个数，为了避免重复计算，我们只需要遍历 $i = 1 \to i = l / 3$ 即可计算所有可能的等边三角形，个数为三个位置点数相乘

C++

void solve () {
    cin >> n >> l;
    vector<int> d(n + 1), cnt(l + 1);

    int last = 0;
    cnt[0]++;
    for (int i = 1; i <= n; i++)
        cin >> d[i], last = (last + d[i]) % l, cnt[last]++;
    cnt[last]--;

    if (l % 3 != 0) {
        cout << 0 << '\n';
        return;
    }

    int res = 0, k = l / 3;

    for (int i = 0; i <= k; i++) {
        int a1 = cnt[i], a2 = cnt[i + k], a3 = cnt[i + 2 * k];
        res += a1 * a2 * a3;
    }

    cout << res << '\n';
}

# D

# 题目大意

给定一个长度为 $n$ 的小写字母字符串 $S=s_1s_2...s_n$ ，现在对其执行一次下方操作

选择一个长度至少为 $1$ 的连续子串，将其向左循环移位 $1$ 次

求出操作后， $S$ 字典序最小的字符串

# 数据范围

$1 \le T,n \le 10^5$

# 题解

# 错解

一开始的思路是，对于每一个 $s_i$ ，其必须 $\ge s_{i+1}$ 才有移位的必要，然后其~~移位最优解是移动到~~ $a \to s_{i}$ 的最后一个位置上
但是比如说 baca ，显然，最优移法是 abca ，但是按我的移法，最后答案会是 acab
由此可以发现，移动位置不是 $a \to s_i$ 的每个的最后一个，而是在 $s_i$ 之后，第一个 $\ge s_i$ 的字符的前面一个位置，这是 $WA$ 的原因
而为什么会 $TLE$ 呢？
这是由于， $substr$ 的时间复杂度是线性 $O(L)$ 的，预估复杂度是 $O(26·N·L)$ ，显然直接爆掉了

C++

void solve () {
    cin >> n >> s;
    vector<vector<int>> pos(26);

    for (int i = 0; i < n; i++)
        pos[s[i] - 'a'].push_back(i);

    string res = s;
    
    for (int i = 0; i < n - 1; i++)
        // 从第 i 个位置开始做循环移位
        if (s[i] >= s[i + 1]) {
            // 只有当 s[i] < s[i + 1] 时，循环移位才能使得字符串变小
            for (int j = s[i] - 'a'; j >= 0; j--) {
                // 最坏的移位情况，是只交换 s[i] s[i + 1]
                // 现在，我的位置上 i，也就是说，对于每一个字符，我要找其出现位置 >= i 的最大位置
                int idx;

                if (pos[j].empty() || (idx = pos[j].back()) < i)
                    continue;// 找到了 idx > i 的最大位置

                string t = s.substr(0, i) + s.substr(i + 1, idx - i) + s[i] + s.substr(idx + 1, n - idx - 1);

                if (res > t)
                    res = t;
            }
        }

    cout << res << '\n';
}

# 正解

如何解决 $TLE$ 呢，题目要求是求字典序最小的，显然遇到能够移位的，先移位，肯定是最优的
所以，我们可以用 $O(n)$ 枚举需要循环移位的字符， $O(n)$ 找到移动的位置， $O(n)$ 输出答案即可
平均时间复杂度是 $O(3n)$ ，可以接受

这题也给我们一个启示，当题目要求字符串类似移位操作后，字典序最小的结果，只需要考虑第一次移位即可，因为后面的移位结果肯定不会大于前面的

C++

void solve () {
    cin >> n >> s;

    for (int i = 0; i < n - 1; i++)
        if (s[i] > s[i + 1]) {
            int idx = i + 1;
            while (idx < n && s[idx] <= s[i])
                idx++;
            idx--;
            
            string t = s.substr(0, i) + s.substr(i + 1, idx - i) + s[i] + s.substr(idx + 1);
            cout << t << '\n';
            return;
        }

    cout << s << '\n';
}

# E

# 题目大意

给定一个 $N$ 个顶点的树，有 $N-1$ 条边，每条边的权重为 $W_i$ ，顶点 $i$ 上有一个整数 $x_i$ ，若 $x_i > 0$ ，代表此处有 $x_i$ 个正电子，否则有 $-x_i$ 个负电子，题目保证，全树电子和为 $0$
每次可以沿边移动 $1$ 个正电子或负电子，消耗 $W_j$ 能量，当正负电子位于同一顶点时，他们会相互抵消
求，使得所有电子全部消失所需要的最小总能量

# 数据范围

$2 \le N \le 10^5$
$|x_i| \le 10^4$
$0 \le w_j \le 10^4$

# 题解

这题的关键，是要发现，不管最终在哪个点抵消，答案都是一样的
也就是说，我们可以把 $1$ 点当根节点，利用树形 $DP$ ，就直接是，从叶节点往上不断移动电子的全部总能量
树形 $DP$ 还是练的少了，不过这个题目的性质有点难发现

C++

void dfs(int u, int f) {
    s[u] = a[u];

    for (auto [to, val] : g[u])
        if (to != f) {
            dfs(to, u);
            s[u] += s[to], res += val * abs(s[to]);
        }
}

void solve () {
    cin >> n, a = vector<int>(n + 1), s = vector<int>(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w}), g[v].push_back({u, w});
    }

    dfs(1, 0);

    cout << res << '\n';
}

ABC 暴力

# B

# 题目大意

# 数据范围

# 题解

# C

# 题目大意

# 数据范围

# 题解

# D

# 题目大意

# 数据范围

# 题解

# 错解

# 正解

# E

# 题目大意

# 数据范围

# 题解

ABC-408

位运算最短路