0%

Codeforces - Educational Codeforces Round 143

Contestant. Rank 2199. Rating +10.

A. Two Towers

题意

给定由两种不同颜色的元素叠成的塔,定义操作为将一个塔上的顶部元素移动到另一个塔,在若干次操作后,输出是否可以让两个塔的元素颜色相间。

思路

显然,这个问题可以抽象为:给定一个元素序列,找出一个点,将序列分成两半,使分割后的序列颜色相间。

那么,我们需要满足两个条件:

  1. 序列内没有连续 个及以上相同元素相邻;

  2. 序列内连续 个及以上相同元素相邻的组的个数最多只有

时间复杂度:

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010, inf = 0x3f3f3f3f;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int a, b;
        cin >> a >> b;
        string x, y;
        cin >> x >> y;
        reverse(y.begin(), y.end());
        x += y;
        int n = a + b;
        char pre = -1;
        int cnt = 0;
        bool ans = true, found = false;
        for(int i=0;i<n;i++){
            char cur = x[i];
            if(cur == pre) {
                cnt ++;
                if(cnt == 2){
                    if(found){
                        ans = false;
                        break;
                    }
                    found = true;
                }
                if(cnt >= 3){
                    ans = false;
                    break;
                }
            }else cnt = 1;
            pre = cur;
        }
        cout << (ans ? "YES\n" : "NO\n");
    }
    return 0;
}

漏条件了,淦

B. Ideal Point

题意

给定 个区间,判断是否能删去一些区间,让 成为被最多数量的区间包含的点。

思路

显然,若不希望让其他节点成为被最多数量的区间包含的点,我们就希望两个区间的交集为一个点,也就是说,我们只需删到最后只剩下 即可。

换句话说,我们只需找出这样的区间,满足左边界为 或右边界为

时间复杂度:

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010, inf = 0x3f3f3f3f;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int a, b;
        cin >> a >> b;
        string x, y;
        cin >> x >> y;
        reverse(y.begin(), y.end());
        x += y;
        int n = a + b;
        char pre = -1;
        int cnt = 0;
        bool ans = true, found = false;
        for(int i=0;i<n;i++){
            char cur = x[i];
            if(cur == pre) {
                cnt ++;
                if(cnt == 2){
                    if(found){
                        ans = false;
                        break;
                    }
                    found = true;
                }
                if(cnt >= 3){
                    ans = false;
                    break;
                }
            }else cnt = 1;
            pre = cur;
        }
        cout << (ans ? "YES\n" : "NO\n");
    }
    return 0;
}

nnd,一个水题卡半天

C. Tea Tasting

题意

给定 壶茶和 个品茶师,第 壶茶有 数量的茶,第 位品茶师一次可以喝 数量的茶。

规定有 轮喝茶,第 轮由 内的品茶师喝 内的茶。

输出每位品茶师最后喝了多少。

思路

首先,我们可以发现,对于第 轮,我们考虑从第 位开始求和后第一个超过 的数的下标,此时我们就可以确定一轮下来有哪些品茶师喝了茶。

考虑到只有最后一个品茶师有可能喝到多余的茶,其余的品茶师喝的量都是次数乘上 ,那么我们不妨单独统计多余喝的量,其余的统计我们考虑使用差分。

当然,上述求和找下标的操作可以采用 前缀和+二分。

时间复杂度:

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N], b[N], sum[N], drunk[N], ans[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        for(int i=1;i<=n;i++) cin >> a[i];
        for(int i=1;i<=n;i++) {
            cin >> b[i];
            drunk[i] = 0;
            ans[i] = 0;
        }
        sum[0] = drunk[0] = ans[0] = 0;
        for(int i=1;i<=n;i++) sum[i] = sum[i - 1] + b[i];
        for(int i=1;i<=n;i++) {
            int x = lower_bound(sum + i, sum + n + 1, a[i] + sum[i - 1]) - sum - 1; //x为能吃的最后一个玩意儿
            //if(x == 0) continue;
            int left = a[i] + sum[i - 1] - sum[x];
            if(x < n) ans[x + 1] += left;
            drunk[i] ++;
            drunk[x + 1] --;
        }
        for(int i=1;i<=n;i++){
            drunk[i] += drunk[i - 1];
            ans[i] += drunk[i] * b[i];
            cout << ans[i] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

过于模拟以至于思路很清晰也很单一

D. Triangle Coloring

题意

给定一个有 个连通块的带权无向有环图,每个连通块的三点均有一条边相连,构成 个三角形。将所有点染上两种颜色,满足两种颜色的点的个数相同,输出有多少方案让连接两个颜色不同的点的边的权值总和最大。

思路

显然,我们需要考虑一个连通块内权值重复的边,而我们关注的是最大值和次大值的情况:

  1. 全都相等, 种选择;

  2. 次大值和最小值相等, 种选择;

  3. 次大值和最大值相等, 种选择;

  4. 没有一个相等, 种选择。

照上述讨论,我们可以发现一个连通块的解等于最小值和多少条边是相等的。

而考虑到两种颜色的个数要相同,我们相当于在 个连通块中找出 个连通块染成同一种颜色,所以最后的答案即为所有连通块解的乘积乘上

时间复杂度:不会分析

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int a[N];

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

int Inv(int a) {
    int x, y;
    exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}

int C(int m, int n) {
    int a = 1, b = 1;
    if (m < n) return 0;
    while (n) {
        a = (a * m) % mod;
        b = (b * n) % mod;
        m--;
        n--;
    }
    return a * Inv(b) % mod;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int t = n / 3;
    int ans = C(t, t / 2);
    for (int i = 0; i<=n/3-1;i++) {
        int minn = min(a[i * 3 + 3], min(a[i * 3 + 1], a[i * 3 + 2]));
        int cnt = 0;
        for (int j = 1; j <= 3; j++)
            if (a[i * 3 + j] == minn) cnt++;
        ans = (ans * cnt) % mod;
    }
    cout << ans << '\n';
    return 0;
}

数组不要开小了!!

E. Explosions?

题意

给定一个数组 为第 个怪物的血量。每次操作可以使用任意数量的 ,使任意一个怪物的血量扣除对应数量的值。

若怪物在遭到攻击后血量小于等于 ,那么怪物死亡。

定义”爆炸”为一个死亡的怪物将相邻的怪物的血量扣去 ,若相邻的怪物血量被扣到 ,那么继续循环。

规定只能让”爆炸”发生一次或不发生,输出让所有怪物死亡的 的最小值。

思路

答案的推导

首先,我们暂定爆炸的那个点下标为 ,之后再考虑 的选择。那么,我们不妨在最后使用爆炸,这样可以在爆炸前将所有元素调整到最好,也就是在 内严格单调递增, 内严格单调递减。

我们不妨用补集的思路,算出最后满足上述条件的数组 的最大总和 ,那么答案即为

总和的计算

首先,不难发现对于 的操作是类似的,那么我们不妨只考虑 内的

“左边界”

对于 点,假设该点满足 $h{p - 1} > h p - 1$,若需要构成连续爆炸,那么我们需要将 $h{p - 1}h_p - 1p - ih{p - i} > h_p - i$。

显然,因为严格单调递增,那么 $hp > ii \geq h_pp - i < 0h{p - i} \leq h_p - i$ 时也会到达边界。

所以,对于左边界 ,将 联立,得到

当然,若没有 满足上面的式子,那么我们将 设为

递推出总和

注意一下推导左边界的条件:$h{p - 1} > h p - 1$。这个条件有一个特点:我们目前所求得的”左边界”实际上是严格单调递增且相邻差值为 的序列的左边界,若出现了”断层”,那么 就有可能偏大了。

但是,不难发现 的推导和 后面的值是无关的,那么我们可以用递推的方式,先算出 前面”严格单调递增且相邻差值为 的序列”的总和,然后将这个总和加到 中即可。

更具体地说, 为以 点为右边界的”严格单调递增且相邻差值为 的序列”的总和,那么只要 对应的元素存在,我们就只需将 加上

有疑惑吗?请留意条件:$h{p - 1} \leq h p - 1jj + 1dp[j]$ 无额外条件。

计算

综上,我们只需对每个”严格单调递增且相邻差值为 的序列”求和即可,考虑到等差性,直接运用等差数列的求和公式即可。

因而, 存在时

“左边界”的低复杂度求法

考虑到我们不可以在每次递推的时候都向前遍历满足条件的”左边界” ,因而我们需要一种更快的方法。

我们回归到条件 。显然,我们需要找出满足该条件的 的最大值,而该思路恰好可以用单调栈实现(先入后出的逻辑适合本题),那么我们只需套上板子即可。

最后的答案

显然,上述操作是线性的,那么我们只需遍历所有的 ,然后输出最大值即可。

当然,因为 会有重叠,所以需要减去重叠的

时间复杂度:

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 3e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int hl[N], hr[N], dp[2][N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        int sum = 0;
        for(int i=0;i<n;i++) {
            cin >> hl[i];
            sum += hr[n - i - 1] = hl[i];
            dp[0][i] = dp[1][i] = 0;
        }
        for(int tp=0;tp<2;tp++){
            int *h = tp == 0 ? hl : hr;
            stack<pii> s;
            for(int i=0;i<n;i++){
                while(!s.empty() && s.top().first > h[i] - i) s.pop();
                int j = max(-1LL, i - h[i]);
                if(!s.empty()) j = max(j, s.top().second);
                int len = i - j;
                dp[tp][i] = len * h[i] - len * (len - 1) / 2;
                if(j >= 0 && len < h[i]) dp[tp][i] += dp[tp][j];
                s.emplace(h[i] - i, i);
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            ans = max(ans, dp[0][i] + dp[1][n - i - 1] - hl[i] * 2);
        }
        cout << sum - ans << '\n';
    }
}

好复杂.jpg