CF-551：部分题目总结

A .Serval and Bus

pro：给出n种公交车的首班车时间和两班车之间的时间间隔，找t时间以后的第一辆车是第几种车

sol：对于每种车，找到t时间以后的第一班车的时间，计算这个时间和t的差距，然后找离t最近的

暴力

#include "bits/stdc++.h"

using namespace std;

const int MAXN = ;

const int INF = 0x3f3f3f3f;

int ans, k = INF;

int main() {

    int n, t, a, b, c;

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

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

        scanf("%d%d", &a, &b);

        if (a >= t) {

            c = a - t;

        } else {

            c = ((a - t) % b + b) % b;

        }

        if (c < k) {

            k = c;

            ans = i;

        }

    }

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

    return ;

}

最后一个取余忘了，然后就被hack......甚是无语

B .Serval and Toy Bricks

pro：给出三视图每一列的高度，俯视图有点特殊，只有0或1，求俯视图每一格的高度

sol：结果不唯一，对于俯视图每一格，找到对应的左视图和前视图，取其中高度小的就必能配成正确的俯视图

贪心

#include "bits/stdc++.h"

using namespace std;

const int MAXN = ;

int mp[MAXN][MAXN];

int f[MAXN], l[MAXN];

int main() {

    int n, m, k;

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

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

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

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

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

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

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

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

            if (mp[i][j]) mp[i][j] = min(f[j], l[i]);

        }

    }

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

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

            printf("%d ", mp[i][j]);

        puts("");

    }

    return ;

}

C .Serval and Parenthesis Sequence

pro：给出一个括号串，其中一部分被用'?'代替，补全括号串，使得括号串除自身以外每个前缀串都不是合法括号串，但是自身是合法括号串，若无法补全，输出":("；

sol：还是贪心，因为要补成合法括号串，所以左括号个数为(|s| / 2)个，从左往右扫，遇到'?'如果能补左括号就补左括号，补不了左括号再补右括号，如果还没到末尾就合法了，输出":("，如果到末尾还不是合法括号串，也输出":("，否则输出补好的串。CF贪心的题好多啊

贪心

#include "bits/stdc++.h"

using namespace std;

const int MAXN = 3e5 + ;

char s[MAXN];

int n, k, l;

int main() {

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

    k = n >> ;

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

        if (s[i] == '(') k--;

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

        if (s[i] == '?') {

            if (k > ) {

                s[i] = '(';

                k--;

            } else {

                s[i] = ')';

            }

        }

    }

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

        if (s[i] == '(') {

            l++;

        } else {

            l--;

        }

        if (l <= ) {

            puts(":(");

            return ;

        }

    }

    if (s[n - ] == ')') {

        l--;

    } else {

        l++;

    }

    if (l == ) {

        puts(s);

    } else {

        puts(":(");

    }

    return ;

}

D . Serval and Rooted Tree

pro：给出一棵树，除叶子节点外每个节点有一个属性，0表示该节点的值等于子节点中最大值，1表示该节点的值等于子节点中最小值，将1到k填入k个子节点，使得根节点值最大。

sol：树形dp + dfs，dfs(i) 表示叶子节点的个数减去i节点的最大值，所以用叶子节点个数减dfs(i)就是i节点最大值，至于树形dp那一块，看代码应该能懂了。

树形dp + 深度优先搜索 + 好像也有点贪心在里面吧

#include "bits/stdc++.h"

using namespace std;

const int MAXN = 3e5 + ;

const int INF = 0x3f3f3f3f;

vector<int> v[MAXN];

int arr[MAXN], val[MAXN];

int leaf;

int dfs(int k) {

    if (v[k].empty()) return ;

    if (arr[k] == ) {

        int mn = INF;

        for (int i = ; i < v[k].size(); i++)

            mn = min(mn, dfs(v[k][i]));

        return mn;

    } else {

        int sum = ;

        for (int i = ; i < v[k].size(); i++)

            sum += dfs(v[k][i]);

        return sum + v[k].size() - ;

    }

}

int main() {

    int n, k;

    scanf("%d", &n); leaf = n;

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

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

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

        scanf("%d", &k);

        if (v[k].empty()) leaf--;

        v[k].push_back(i);

    }

    printf("%d\n", leaf - dfs());

    return ;

}

思路来源于今年蓝桥杯省赛的一道求雨题，不过这两题比赛当场都没能完成。都是比赛结束之后才想通的。继续努力

SOL