T0

挂掉了，但是离开倒计时2天。

T1

LUOGU
数据范围非常小，所以直接暴力去做。

#include <bits/stdc++.h>
using namespace std;
int l, r, x;
int work(int t) {
    int res = 0;
    while (t) {
        res += t % 10;
        t /= 10;
    }
    return res == x;
}
int main() {
    scanf("%d%d%d", &l, &r, &x);
    for (int n = l; n <= r; n++) {
        if (work(n)) {
            printf("%d\n", n);
            break;
        }
    }
    for (int m = r; m >= l; m--) {
        if (work(m)) {
            printf("%d\n", m);
            break;
        }
    }
    return 0;
}

T2

(用的Latex公式太多了，直接图片)
这题第一个想法就是DP，模拟此处是否需要进行操作就可以了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
typedef long long LL;
LL res = 0, f[N][2];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        LL x;
        scanf("%lld", &x);
        f[i][0] = f[i - 1][0] + x;
        f[i][1] = f[i - 1][0] - x;
        if (i > 1) {
            f[i][0] = max(f[i][0], f[i - 1][1] - x);
            f[i][1] = max(f[i][1], f[i - 1][1] + x);
        }
    }
    printf("%lld", f[n][0]);
    return 0;
}

T3

将每一个区间按长度从大到小排序之后，前(n-1)个区间是可以不用选的，因此，从n-1~末尾区间的长度，就是答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, m, res, x[N];
vector<int> V;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) scanf("%d", &x[i]);
    if (n >= m) {
        puts("0");
        return 0;
    }
    sort(x + 1, x + m + 1);
    for (int i = 1; i < m; i++) V.push_back(x[i + 1] - x[i]);
    sort(V.begin(), V.end());
    reverse(V.begin(), V.end());
    for (int i = n - 1; i < V.size(); i++) res += V[i];
    printf("%d", res);
    return 0;
}

T4

一年一度的猴王争霸赛的报名开始啦！
目前有n只猴子排起了长长的队伍，每只猴子都有自己的身高。当然，每只猴子都想着排到前面去,于是它们就要插队啦。
每次插队，插队的猴子都会去找目前排在它前面的那只猴子。如果前面那只猴子身高比自己矮，要插队的猴子就会直接用武力解决，从而排到它的前面，即所谓“猴高猴有理”。而对于那些身高比自己高的猴子，就不能直接插队了T_T。
根据猴国的传统，只要抱在一只猴子的身上并用香蕉贿赂它，就能排到它前面了……然而由于香蕉数量有限，每只猴子最多只能贿赂一只身高比自己高的猴子。
在开始插队之前，每只猴子都想知道，如果只有它一只猴在插队，它最多能排到哪个位置。

单调栈，但是二次维护。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, a[N], stk[N], top, res[N];
vector<int> pos[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        while (top && a[i] > a[stk[top]]) top--;
        pos[stk[top]].push_back(i);
        stk[++top] = i;
    }
    top = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < pos[i].size(); j++) {
            while (top && a[pos[i][j]] > a[stk[top]]) top--;
            res[pos[i][j]] = stk[top];
        }
        stk[++top] = i;
    }
    for (int i = 1; i <= n; i++) printf("%d\n", res[i] + 1);
    return 0;
}

T5

本身是一个二维偏序的问题。
但是数据范围小，可以用二维前缀和/后缀和维护。

#include <bits/stdc++.h>
using namespace std;
const int N = 500005, M = 705;
int n, a[N], b[N], c[M][M], pre[M][M], suf[M][M];
int cnta[N], cntb[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);
        c[++a[i]][++b[i]]++;
        if (a[i] == 1)
            cntb[b[i]]++;
        if (b[i] == 1)
            cnta[a[i]]++;
    }
    for (int i = 1; i <= 700; i++) {
        for (int j = 1; j <= 700; j++)
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + c[i][j] - pre[i - 1][j - 1];
    }
    for (int i = 700; i; i--) {
        for (int j = 700; j; j--) suf[i][j] = suf[i + 1][j] + suf[i][j + 1] + c[i][j] - suf[i + 1][j + 1];
    }
    for (int i = 1; i <= n; i++) {
        int l = suf[a[i] + 1][b[i] + 1], r = pre[a[i] - 1][b[i] - 1];
        if (a[i] == 651)
            r += cntb[b[i]];
        if (b[i] == 651)
            r += cnta[a[i]];
        printf("%d %d\n", l + 1, n - r);
    }
    return 0;
}

T6

代码量很短，但是要往并查集的方向上去考虑。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
typedef long long LL;
int n, m;
LL res;
int fa[N], par[N], cnt[N];
int find(int x) {
    if (par[x] == x)
        return x;
    else
        return par[x] = find(par[x]);
}
int main() {
    scanf("%d%d", &n, &m);
    par[1] = 1;
    for (int i = 2; i <= n; i++) {
        scanf("%d", &fa[i]);
        fa[i]++;
        par[i] = i;
    }
    while (m--) {
        int x;
        scanf("%d", &x);
        x++;
        cnt[x]++;
    }
    for (int i = 1; i <= n; i++) {
        if (!cnt[i])
            par[i] = fa[i];
    }
    for (int i = n; i; i--) {
        int x = find(i);
        if (x) {
            res += (LL)(i - 1);
            if (!(--cnt[x]))
                par[x] = fa[x];
        }
    }
    printf("%lld", res);
    return 0;
}