由于我的codeforces的帐号登不上，所以我错过了这场比赛，只好赛后再抄题解自己做。

A Benches

最大的情况就是所有人都挤在那个人最多的长椅上，最小的情况是所有人尽量平均的坐。

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N = 110;

int a[N], n, m, mx; 

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) {

        scanf("%d", &a[i]);

        mx = std::max(a[i], mx);

    }

    int ansb = mx + m, ansa = 0;

    for (int i = 1; i <= n; ++i) {

        m -= mx - a[i];

    }

    if (m < 0) ansa = mx;

    else ansa = mx + m / n + (m%n != 0);

    printf("%d %d\n", ansa, ansb);

    return 0;

}

提交次数：\(1\)

B Vitamins

这个题直接DP，把有哪几种维他命状压一下就行。

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N = 1010;

int V[N];

int n, c[N], p[N];

int f[10];

int main() {

    V['A'] = 1; V['B'] = 2; V['C'] = 4;

    scanf("%d", &n);

    char s[5];

    for (int i = 1; i <= n; ++i) {

        scanf("%d%s", &p[i], s);

        int len = strlen(s);

        for (int j = 0; j < len; ++j) c[i] |= V[s[j]];

    }

    memset(f, 0x3f, sizeof f);

    f[0] = 0;

    for (int i = 1; i <= n; ++i) {

        for (int S = 7; S >= 0; --S) if (f[S] < 0x3f3f3f3f) {

            f[S|c[i]] = std::min(f[S|c[i]], f[S] + p[i]);

        }

    }

    if (f[7] == 0x3f3f3f3f) puts("-1");

    else printf("%d\n", f[7]);

    return 0;

}

提交次数：\(1\)

C Array Product

这个也是一个简单的构造题，贪心的做就行，不要忘记只能删除一个点。

删正数肯定是不优的。如果有偶数个负数，乘起来就行，如果有奇数个负数，将绝对值最小的负数和0乘起来（如果没有0那就直接删），然后把所有0乘起来删掉（如果就只剩一个0了那就不能删）。

最后把所有数乘起来就行。

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N = 2e5 + 10;

int a[N], n, m, mx = 0, del[N], tot, posi, nega, zero;

int ls[3][N]; 

int main() {

    scanf("%d", &n);

    a[0] = -0x3f3f3f3f;

    for (int i = 1; i <= n; ++i) {

        scanf("%d", &a[i]);

        if (a[i] == 0) {

            ls[1][++zero] = i;

        } else if (a[i] < 0 ) {

            ls[0][++nega] = i;

            if (a[i] > a[mx]) mx = i;

        } else {

            ls[2][++posi] = i;

        }

    }

    if (nega%2 != 0 && zero > 0) {

        printf("1 %d %d\n", mx, ls[1][1]);

        del[mx] = 1;

        tot++;

    } else if (nega%2 != 0 && zero == 0) {

        printf("2 %d\n", mx);

        del[mx] = 1;

        tot++;

    }

    if (zero > 0) {

        while (zero > 1 && tot < n-2) {

            printf("1 %d %d\n", ls[1][zero], ls[1][zero-1]);

            del[ls[1][zero]] = 1;

            zero--;

            tot++;

        }

        if (tot < n-1) {

            printf("2 %d\n", ls[1][1]);

            tot++;

            del[ls[1][1]] = 1;

        }

    }

    int i = 1, j;

    while (del[i]) i++;

    j = i+1;

    while (tot < n-1) {

        while (del[j]) j++;

        printf("1 %d %d\n", i, j);

        i = j;

        j = i+1;

        tot++;

    }

    return 0;

}

提交次数：\(3\)（没看到只能删一次和少处理了一个情况）。

D Petya and Array

求区间和一定要求前缀和，然后问题就转化成了求\(\displaystyle\sum_{l}\displaystyle\sum_{r}[s_i-s_{l-1}<k]\)，化简一下就成了\(\displaystyle\sum_{l}\displaystyle\sum_{r}[s_i<k+s_{l-1}]\)，直接倒着做然后树状数组查就行。别忘了离散化的时候要把\(S_0 = 0\)也离散进去（并没有想明白为什么）

#include <cstdio>

#include <algorithm>

const int N = 200000 + 10;

typedef long long LL;

LL a[N], s[N], b[N], c[N];

LL t;

int n, mx;

LL bt[N];

inline void add(int x) {

    for (; x <= mx; x += x&-x) {

        bt[x]++;

    }

}

inline LL query(int x) {

    LL ans = 0;

    for (; x>0; x -= x&-x) {

        ans += bt[x];

    }

    return ans;

}

int main() {

    scanf("%d%I64d", &n, &t);

    for (int i = 1; i <= n; ++i) {

        scanf("%I64d", &a[i]);

        s[i] = s[i-1] + a[i];

        b[i+1] = s[i];

    }

    std::sort(b+1, b+n+2);

    mx = std::unique(b+1, b+n+2) - b - 1;

    for (int i = 1; i <= n; ++i) {

        c[i] = std::lower_bound(b+1, b+mx+1, s[i]) - b;

    }

    LL ans = 0;

    for (int i = n; i; --i) {

        add(c[i]);

        int tmp = std::lower_bound(b+1, b+mx+1, s[i-1]+t) - b - 1;

        ans += query(tmp);

    }

    printf("%I64d\n", ans);

    return 0;

}

提交次数：\(5\)（离散化没加\(0\)，和lower_bound上界写错）

E Vasya and Magic Matrix

这个题还是能轻松的想到排序后从小到大枚举计算的。只是我一开始没有看到欧式距离的平方，苦思无解，只好去看题解，结果……

有平方的话就有交换律和结合律了，某个点的期望值为\(f_x = \displaystyle\frac{\displaystyle\sum_{1\le i\le k}(f_i + (r_x-r_i)^2 + (c_x-c_i)^2)}{k}\)，其中\(k\)是所有比他小的点的数量。化简之后就能发现这个式子只与比他小的数的个数，横纵坐标的和，横纵坐标的平方和，以及期望和有关。开几个变量记录一下就行（我图方便开了数组）

#include <cstdio>

#include <algorithm>

typedef long long LL;

const int N = 1e3 + 10;

const int M = N*N;

const LL MOD = 998244353;

struct node {

    LL x, y, h;

    bool operator< (const node &x) const {

        return h < x.h;

    }

} p[M];

int n, m, tot;

LL pos, sf[M], sx[M], sy[M], sx2[M], sy2[M], sk[M];

LL dp[N][N];

int x, y;

inline LL pow_mod(LL x, LL p) {

    LL ans = 1;

    while (p) {

        if (p&1) ans = ans * x % MOD;

        x = x * x % MOD;

        p = p >> 1;

    }

    return ans;

}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) {

        for (int j = 1; j <= m; ++j) {

            tot++;

            scanf("%I64d", &p[tot].h);

            p[tot].h++;

            p[tot].x = i;

            p[tot].y = j;

        }

    }

    scanf("%d%d", &x, &y);

    std::sort(p+1, p+tot+1);

    for (int i = 1; i <= tot; ++i) {

        if (p[i].h != p[i-1].h) {

            pos++;

            sf[pos] += sf[pos-1];

            sx[pos] += sx[pos-1];

            sy[pos] += sy[pos-1];

            sx2[pos] += sx2[pos-1];

            sy2[pos] += sy2[pos-1];

            sk[pos] += sk[pos-1];

        }

        LL f = 0;

        f = (f + sf[pos-1]) % MOD;

        f = (f + sx2[pos-1]) % MOD;

        f = (f + sy2[pos-1]) % MOD;

        f = (f + p[i].x * p[i].x % MOD * sk[pos-1] % MOD) % MOD;

        f = (f + p[i].y * p[i].y % MOD * sk[pos-1] % MOD) % MOD;

        f = (f - 2 * p[i].x % MOD * sx[pos-1] % MOD + MOD) % MOD;

        f = (f - 2 * p[i].y % MOD * sy[pos-1] % MOD + MOD) % MOD;

        f = f * pow_mod(sk[pos-1], MOD-2) % MOD;

        dp[p[i].x][p[i].y] = f;

        sf[pos] = (sf[pos] + f) % MOD;

        sx[pos] = (sx[pos] + p[i].x) % MOD;

        sy[pos] = (sy[pos] + p[i].y) % MOD;

        sx2[pos] = (sx2[pos] + p[i].x * p[i].x % MOD) % MOD;

        sy2[pos] = (sy2[pos] + p[i].y * p[i].y % MOD) % MOD;

        sk[pos] = (sk[pos] + 1) % MOD;

        if (p[i].x == x && p[i].y == y) break;

    }

    printf("%I64d\n", dp[x][y]);

    return 0;

}

提交次数：\(0+1\)

F Leaf Sets

这个题看了一会儿觉得不可做，就直接看了题解。

其实用了树形DP的思想，先dfs下去，再统计儿子们的答案然后上传。不过这个在dfs里开vector的操作惊到我了，我以前从未见过这样的写法（但是这样不会爆栈吗？）。

首先，对于一个叶子节点的集合，我们用这个集合中深度最大的点代表这个集合，因为只有这个点决定了两个集合能否合并。如果两个集合\(A,B\)的代表点\(d_A,d_B\)之间的距离小于\(k\)，那就可以合并，且合并后代表点的深度为\(max\{ d_A, d_B \}\)，如果大于\(k\)呢？不妨设\(d_A\le d_B\)，此时\(d_B\)一定没有用了，因为之后能和\(B\)合并的也一定能和\(A\)合并，那么\(B\)集合就不用再合并了，直接记录答案就行。

#include <cstdio>

#include <algorithm>

#include <vector>

const int N = 1e6 + 10;

const int M = 2e6 + 10;

int n, k;

int hd[N], to[M], nxt[M], cnt;

int dep[N], deg[N];

int ans;

inline void adde(int x, int y) {

    cnt++;

    to[cnt] = y;

    nxt[cnt] = hd[x];

    hd[x] = cnt;

}

int dfs(int x, int f) {

    if (deg[x] == 1) {

        return 0; // 叶子直接返回0

    }

    std::vector<int> d;

    for (int i = hd[x]; i; i = nxt[i]) if (to[i] != f) {

        d.push_back(dfs(to[i], x) + 1);

    }

    std::sort(d.begin(), d.end());

    while (d.size() >= 2) {

        if (d[d.size()-1] + d[d.size()-2] <= k) break;

        d.pop_back(); // 不能合并的就不合并了。

        ans++;

    }

    return d.back(); // 相当于把d中的所有集合合并了。

}

int main() {

    scanf("%d%d", &n, &k);

    for (int i = 1, x, y; i < n; ++i) {

        scanf("%d%d", &x, &y);

        adde(x, y);

        adde(y, x);

        deg[y]++; deg[x]++;

    }

    for (int i = 1; i <= n; ++i) if (deg[i] > 1) {

        dfs(i, 0);

        break;

    }

    printf("%d\n", ans+1); // 最后会剩下一个集合

    return 0;

}

提交次数：\(0+2\)（没有处理好叶子节点）

巴特西

[CF]Round510