Contestant. Rank 2199. Rating +10.

A. Two Towers

题意

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

思路

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

那么，我们需要满足两个条件：

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

时间复杂度：

对应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

题意

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

思路

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

全都相等，种选择；
次大值和最小值相等，种选择；
次大值和最大值相等，种选择；
没有一个相等，种选择。

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

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

时间复杂度：不会分析

对应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 - 1 $。同理，可推得对于$ p - i $点，通式为$ h{p - i} > h_p - i$。

显然，因为严格单调递增，那么 $hp > i $是一定成立的，也就是说，$ i \geq h_p $时到达边界。当然，按照上述的推导，$ p - i < 0 $或$ h{p - i} \leq h_p - i$ 时也会到达边界。

所以，对于左边界，将和联立，得到。

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

递推出总和

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

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

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

有疑惑吗？请留意条件：$h{p - 1} \leq h p - 1 $。$ j $元素的值一定小于等于$ j + 1 $元素的值，所以加上$ dp[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

本文作者 Floating Ocean
本文链接 https://floating-ocean.github.io/blog_old/posts/3290967404/
版权声明本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

Blog - Floating Ocean

Codeforces - Educational Codeforces Round 143

A. Two Towers

题意

思路

对应AC代码

B. Ideal Point

题意

思路

对应AC代码

C. Tea Tasting

题意

思路

对应AC代码

D. Triangle Coloring

题意

思路

对应AC代码

E. Explosions?

题意

思路

答案的推导

总和的计算

“左边界”

递推出总和

计算

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

最后的答案

对应AC代码