Codeforces Edu Round 67 A-C + E

A. Stickers and Toys

考虑尽量先买$max(s, t)$个里面单独的。那么如果$s + t > n$那么$s + t - n$的部分就该把$min(s, t)$踢出来，这些多的只能合并到另外一个上面去，所以答案就是：$ max(s, t) - (s + t - n) + 1$。

#include <cstdio>

#include <iostream>

#include <cmath>

using namespace std;

int n, s, t;

int main(){

    int T; scanf("%d", &T);

    while(T--){

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

        printf("%d\n", max(s, t) - (s + t - n) + 1);

    }

    return 0;

}

B. Letters Shop

二分答案。答案符合区间包括性（单调性），若$[1, x]$可行，那么$[1, y] (x <= y <= n)$必然也可行。

预处理前缀和，$check()$的时间复杂度可以降到$O(26)$，那么总共程序的时间复杂度为$O(mlogn)$。

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int N = 200010, M = 50010;

char s[N], t[N];

int n, m, sum[N][26], g[26], len;

//[1, x]这段可不可行

bool inline check(int x){

    for(int i = 0; i < 26; i++)

        if(sum[x][i] < g[i]) return false;

    return true;

}

int main(){

    scanf("%d%s%d", &n, s + 1, &m);

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

        for(int j = 0; j < 26; j++) sum[i][j] = sum[i - 1][j];

        sum[i][s[i] - 'a']++;

    }

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

        for(int j = 0; j < 26; j++) g[j] = 0;

        scanf("%s", t + 1);

        len = strlen(t + 1);

        for(int i = 1; i <= len; i++) g[t[i] - 'a']++;

        int l = 1, r = n;

        while(l < r){

            int mid = (l + r) >> 1;

            if(check(mid)) r = mid;

            else l = mid + 1;

        }

        printf("%d\n", r);

    }

    return 0;

}

C. Vasya And Array

由于发现在线做法需要分类讨论，懒癌晚期就把信息进行了排序$qwq$。

不难发现，$NO$的情况就是$0$的信息属于$1$的子序列。但是如果直接处理，就有多种冲突可能，$check$就需要分类讨论了。先处理$1$的数据，再处理$0$的数据，就只需要检查$0$是不是子区间就可以了。

关于方案，设$f[i]$为$i$和$i + 1$的关系（不变还是递减），这样只需要顺次维护即可。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 1010, M = 1010;

int n, m, f[N];

//f[i] 表示 i 和 i + 1 的关系

struct Node{

    int l, r, t;

}e[M];

bool inline cmp(Node x, Node y){

    return x.t > y.t;

}

bool inline check(int l, int r, int t){

    for(int i = l; i < r; i++)

        if(f[i] == -1 || f[i] == t) return true;

    return false;

}

int main(){

    memset(f, -1, sizeof f);

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

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

        int t, l, r; scanf("%d%d%d", &t, &l, &r);

        e[i] = (Node){l, r, t};

    }

    sort(e + 1, e + 1 + m, cmp);

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

        int l = e[i].l, r = e[i].r, t = e[i].t;

        if((!check(l, r, t))) { puts("NO"); return 0; }

        else for(int i = l; i < r; i++)

            if(f[i] == -1)f[i] = t;

    }

    int last = n; printf("YES\n%d ", n);

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

        if(f[i]) printf("%d ", last);

        else printf("%d ", --last);

    return 0;

}

E. Tree Painting

换根法。发现是一颗树。每次扩展的时候，假设时间倒流，发现是一个逐层逆推递进的过程。

对于任意两点$(u, v)$，除了他们的路径上的贡献外，所有外面的扩展是相同的。

设

$f[u][0]$为该点向下扩展的花费，包括$u$的花费
$f[u][1]$为改点向上扩展的花费，不包括$u$的花费
$size[u]$为以$u$为子树的大小

状态转移方程：

$f[u][0] = size[u] + \sum_{(u , v)} f[v][0]$

$f[v][1] = (n - size[v]) + f[u][1] + (f[u][0] - size[u] - f[v][0]) (u , v)$

答案：

$max\{f[i][0] + f[i][1] + (n - size[i])\} (1 <= i <= n)$

这里可以理解为两者均是时间倒流的产物，第一次扩展是先扩展下面的，所以需要计算首次合并。

#include <cstdio>

#include <iostream>

#include <cmath>

using namespace std;

const int N = 200010, M = N << 1;

typedef long long LL;

int n, head[N], numE = 0;

LL f[N][2], size[N];

struct Edge{

    int next, to;

}e[M];

void addEdge(int from, int to){

    e[++numE].next = head[from];

    e[numE].to = to;

    head[from] = numE;

}

void dfs_(int u, int fa){

    size[u] = 1;

    for(int i = head[u]; i; i = e[i].next){

        int v = e[i].to;

        if(v == fa) continue;

        dfs_(v, u);

        size[u] += size[v];

        f[u][0] += f[v][0];

    }

    f[u][0] += size[u];

}

void dfs(int u, int fa){

    for(int i = head[u]; i; i = e[i].next){

        int v = e[i].to;

        if(v == fa) continue;

        f[v][1] = (n - size[v]) + f[u][1] + (f[u][0] - size[u] - f[v][0]);

        dfs(v, u);

    }

}

int main(){

    scanf("%d", &n);

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

        int u, v; scanf("%d%d", &u, &v);

        addEdge(u, v); addEdge(v, u);

    }

    dfs_(1, 0);

    dfs(1, 0);

    LL ans = -1;

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

        ans = max(ans, f[i][0] + f[i][1] + (n - size[i]));

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

    return 0;

}

巴特西

Codeforces Edu Round 67 A-C + E

A. Stickers and Toys

B. Letters Shop

C. Vasya And Array

E. Tree Painting

最新文章

热门文章