Codeforces 1084 - 题集

单个题目的链接

Codeforces 1084A - The Fair Nut and Elevator
Codeforces 1084B - Kvass and the Fair Nut - 二分
Codeforces 1084C - The Fair Nut and String
Codeforces 1084D - The Fair Nut and the Best Path - 树形DP
Codeforces 1084E - The Fair Nut and Strings - 思维

Codeforces 1084A - The Fair Nut and Elevator

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1084/problem/A


题意

  有一个电梯,它初始时会停留在第 $k$ 层楼,每当有一个人要从第 $a$ 楼去第 $b$ 楼,电梯就会始终按照 $k \rightarrow a \rightarrow b \rightarrow k$ 的路线去运行,而且电梯最多只会同时容纳一个人,现在有一个 $n$ 层楼的楼房,第 $i$ 层有 $a_i$ 个人,这一层的每个人每天都要按照 $i \rightarrow 1 \rightarrow i$ 的顺序使用电梯,问将电梯的 $k$ 设为多少时,每天的运行距离最少。


思路

  注意到 $n$ 只有 $100$,暴力枚举,复杂度 $O(n ^ 2)$。


实现

https://pasteme.cn/2418

#include <bits/stdc++.h>
typedef long long ll;
ll a[1007], n, ans = 0x3f3f3f3f;
int main() {
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) scanf("%lld", a + i);
    for (ll i = 1; i <= n; i++) {
        ll sum = 0;
        for (ll j = 1; j <= n; j++) sum += a[j] * 2 * (abs(i - j) + abs(j - 1) + abs(1 - i));
        ans = std::min(ans, sum);
    }
    printf("%lld\n", ans);
    return 0;
}

Codeforces 1084B - Kvass and the Fair Nut - 二分

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1084/problem/B


题意

  你有 $n$ 桶水,第 $i$ 桶水里初始时有 $v_i$ 升水,你需要从这 $n$ 桶水中取出 $s$ 升水,问是否能取 $s$ 升水出来,如果可以的话让 $n$ 桶水剩下水最少的那桶水尽量的多。


思路

  直接暴力二分即可,复杂度 $O(n \cdot log_2(v_{max}))$。


实现

https://pasteme.cn/2419

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 1007;
ll v[maxn], n, s, max, sum;
bool check(ll mid) {
    ll ret = 0;
    for (int i = 1; i <= n; i++) {
        if (v[i] < mid) return false;
        ret += v[i] - mid;
    }
    return ret >= s;
}
int main() {
    std::cin >> n >> s;
    for (int i = 1; i <= n; i++) std::cin >> v[i], sum += v[i], max = std::max(v[i], max);
    if (sum < s) return 0 * puts("-1");
    ll l = 0, r = max, ret = -1;
    while (l <= r) {
        ll mid = l + r >> 1;
        if (check(mid)) ret = mid, l = mid + 1;
        else r = mid - 1;
    }
    std::cout << ret << std::endl;
    return 0;
}

Codeforces 1084C - The Fair Nut and String

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1084/problem/C


题意

  给你一串字符串,问你能选出多少个形如 aba 这样的子序列(任意两个 a 之间至少包含一个 b),a 也算,abaabbaab*ba 算同一种,aaba 是非法的,复杂度 $O(n)$。


思路

  显然可以只保留 ab,然后把连续的 a 都提取出来,剩下的类似于统计 $DAG$ 不同路径数那样统计就可以。


实现

https://pasteme.cn/2420

#include <bits/stdc++.h>
const int maxn = int(1e5) + 7, mod = int(1e9) + 7;
char buf[maxn], str[maxn] = {'b'};
int len = 0, cnt[maxn], n = 0;
int main() {
    scanf("%s", buf);
    for (int i = 0; buf[i]; i++) if (buf[i] <= 'b') str[++len] = buf[i];
    for (int i = 1; i <= len; i++) {
        if (str[i] == 'a') {
            if (str[i - 1] == 'b') cnt[++n] = 1;
            else cnt[n]++;
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + (ans + 1) * cnt[i] % mod) % mod;
    printf("%lld\n", ans);
    return 0;
}

Codeforces 1084D - The Fair Nut and the Best Path - 树形DP

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1084/problem/D


题意

  给你一棵树,数上的每个点都有一个正权值,每条边都有一个负权值,让你在树中找一条简单路径,使得权值和最大。


思路

  我们定义 $f_i$ 为从以节点 $i$ 为根的子树中出发,到达节点 $i$ 时的最大权值和,转移方程为:

$$f_u = max\{f_v - cost_{u, v} + w_u\}$$

  这样处理的是竖着的路径,其中 $v$ 是 $u$ 的每一个儿子。穿过节点 $i$ 的横向路径的最大值为:

$$({f_{v_1} - cost_{u, v_1}})_{最大值} + ({f_{v_2} - cost_{u, v_2}})_{次大值} + w_u$$

  答案在所有 $f_i$ 与上述表达式中取最大值,复杂度为 $O(n)$。


实现

https://pasteme.cn/2421

#include <bits/stdc++.h>
const int maxn = int(3e5) + 7;
std::vector<std::pair<int, long long>> edge[maxn];
long long ans = 0, f[maxn];
int n, w[maxn];
void dfs(int u, int pre) {
    f[u] = w[u];
    long long max[2] = {0, 0};
    for (auto cur : edge[u]) {
        int v = cur.first;
        long long cost = cur.second;
        if (v != pre) {
            dfs(v, u);
            long long tmp = f[v] - cost;
            if (tmp > max[0]) std::swap(max[0], tmp);
            max[1] = std::max(max[1], tmp);
            f[u] = std::max(f[u], f[v] - cost + w[u]);
        }
    }
    ans = std::max({f[u], ans, max[0] + max[1] + w[u]});
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", w + i);
    for (int i = 1, u, v, cost; i < n; i++) {
        scanf("%d%d%d", &u, &v, &cost);
        edge[u].emplace_back(v, cost);
        edge[v].emplace_back(u, cost);
    }
    dfs(1, 1);
    printf("%lld\n", ans);
    return 0;
}

Codeforces 1084E - The Fair Nut and Strings - 思维

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1084/problem/E


题意

  给你一个区间 $[s, t]$,其中 $s$ 和 $t$ 都是字符串,且长度为 $n$,只包含 ab 两种字符,问从这个区间内长度为 $n$ 的字符串中挑出 $k$ 个,最多可以有多少个不同的前缀。


思路

  翻译一下,其实就是给你一个有左右边界且叶子数量必须小于等于 $k$ 个的字典树,最多能有多少个节点,模拟一下即可。


实现

https://pasteme.cn/2422

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = int(5e5) + 7;
ll n, k, ans;
char a[maxn], b[maxn];
bool flag = true;
int main() {
    scanf("%lld%lld%s%s", &n, &k, a + 1, b + 1);
    ll sum = -1, cur = 1;
    while (cur <= n && a[cur] == b[cur]) cur++, ans++;
    for (ll i = cur; i <= n && flag; i++) {
        sum = sum * 2 + 'b' - a[i] + b[i] - 'a';
        if (sum + 2 >= k) ans += (n - i + 1) * k, flag = false;
        else ans += sum + 2;
    }
    printf("%lld\n", ans);
    return 0;
}

总结

  前三题还算顺利,$D$ 题的时候松懈了,然后就忘了统计横向的路径,WA 了两发,很影响心态,$E$ 比赛的时候没想出来。

  两个队友一个第 $6$ 名,一个 $34$ 名,只有我一个 $200$ 多名。说实话,很难受,但也无法反驳什么,他们俩都比我要努力得多,唯一能做的就是加倍努力吧。

发表留言

人生在世,错别字在所难免,无需纠正。