Contestant. Rank 2199. Rating +10.

A. Two Towers

题意

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

思路

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

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

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

时间复杂度：\(O(n)\)

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

题意

给定 \(n\) 个区间，判断是否能删去一些区间，让 \(k\) 成为被最多数量的区间包含的点。

思路

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

换句话说，我们只需找出这样的区间，满足左边界为 \(k\) 或右边界为 \(k\)。

时间复杂度：\(O(n)\)

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

题意

给定 \(n\) 壶茶和 \(n\) 个品茶师，第 \(i\) 壶茶有 \(a_i\) 数量的茶，第 \(i\) 位品茶师一次可以喝 \(b_i\) 数量的茶。

规定有 \(n\) 轮喝茶，第 \(i\) 轮由 \([i, n]\) 内的品茶师喝 \([1, n - i + 1]\) 内的茶。

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

思路

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

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

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

时间复杂度：\(O(n \log n)\)

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

题意

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

思路

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

全都相等，\(3\) 种选择；
次大值和最小值相等，\(2\) 种选择；
次大值和最大值相等，\(1\) 种选择；
没有一个相等，\(0\) 种选择。

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

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

时间复杂度：不会分析

对应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\)，\(h_i\) 为第 \(i\) 个怪物的血量。每次操作可以使用任意数量的 \(MP\)，使任意一个怪物的血量扣除对应数量的值。

若怪物在遭到攻击后血量小于等于 \(0\)，那么怪物死亡。

定义"爆炸"为一个死亡的怪物将相邻的怪物的血量扣去 \(h_i - 1\)，若相邻的怪物血量被扣到 \(0\)，那么继续循环。

规定只能让"爆炸"发生一次或不发生，输出让所有怪物死亡的 \(MP\) 的最小值。

思路

答案的推导

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

我们不妨用补集的思路，算出最后满足上述条件的数组 \(h'\) 的最大总和 \(sum\)，那么答案即为 \((\sum h_i) - sum\)。

总和的计算

首先，不难发现对于 \([0,p]\) 和 \([p, n]\) 的操作是类似的，那么我们不妨只考虑 \([0, p]\) 内的 \(sum'\)。

"左边界"

对于 \(p - 1\) 点，假设该点满足 \(h_{p - 1} > h _ p - 1\)，若需要构成连续爆炸，那么我们需要将 \(h_{p - 1}\) 改为 \(h_p - 1\)。同理，可推得对于 \(p - i\) 点，通式为 \(h_{p - i} > h_p - i\)。

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

所以，对于左边界 \(j = p - i\)，将 \(i = p - j\) 和 \(h_{p - i} \leq h_p - i\) 联立，得到 \(h_j - j \leq h_p - p\)。

当然，若没有 \(j\) 满足上面的式子，那么我们将 \(j\) 设为 \(\max(-1, i - h_i)\)。

递推出总和

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

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

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

有疑惑吗？请留意条件：\(h_{p - 1} \leq h _ p - 1\)。\(j\) 元素的值一定小于等于 \(j + 1\) 元素的值，所以加上 \(dp[j]\) 无额外条件。

计算

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

因而， \(dp[i] = (i - j) \times h_i - \frac{(i - j)(i - j - 1)}{2}\)，\(j\) 存在时 \(dp[i] += dp[j]\)。

"左边界"的低复杂度求法

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

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

最后的答案

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

当然，因为 \(dpL\) 和 \(dpR\) 会有重叠，所以需要减去重叠的 \(h_i\)。

时间复杂度：\(O(n)\)

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