Contestant. Rank 2756. Rating +40.

A. Flip Flop Sum

题意

给定一个只包含 的序列，要求必须进行一次操作，将任意 对应的 $ai,a{i+1}$ 的值取反，输出操作后序列总和的最大值。

思路

显然，若序列是 ，那么操作对总和无影响。

当序列中存在 时，总和加 。

其余情况，即序列中全是 ，总和减 。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t -- > 0){
            int n = scanner.nextInt();
            int sum = 0, pre = scanner.nextInt();
            sum += pre;
            boolean f1 = false, f2 = false;
            for(int i=1;i<n;i++){
                int a = scanner.nextInt();
                sum += a;
                if(a == pre){
                    if(!f1) {
                        if (a == -1){
                            sum += 4;
                            f1 = true;
                        }
                    }
                }else f2 = true;
                pre = a;
            }
            if(!f1 && !f2) sum -= 4;
            System.out.println(sum);
        }
    }

}

别看错题啊喂

B. The Forbidden Permutation

题意

给定长度为 的排列 、长度为 的数组 、以及一个正整数 ，其中数组 无重复元素，且对于任意 $aia_i \in [1,n]i \in [1,m)p[a_i] \geq p[a{i+1}]p[a_{i+1}] > p[a_i] + d$。

思路

显然，我们令 ，那么只要数组 是非递增的，就无需操作。

否则，我们可以执行下面的两个操作：

1. 找出数组 中相邻差值最小的两个元素，将它们交换位置；
2. 找出数组 中相邻差值最大的两个元素，将小的元素向左移，大的元素向右移，直至距离大于 。

因为我们无需考虑最后数组的情况，所以我们只需计算一下即可：

1. 对于操作 ，；
2. 对于操作 ，。

显然，当 过大时，我们无法将元素的距离扩大到 ，此时只能执行操作 。

时间复杂度：

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t -- > 0) {
            int n = scanner.nextInt(), m = scanner.nextInt(), d = scanner.nextInt();
            int[] p = new int[n + 1];
            for(int i=1;i<=n;i++) p[scanner.nextInt()] = i;
            int[] a = new int[m + 1];
            int minDist = Integer.MAX_VALUE, maxDist = 0;
            for(int i=1;i<=m;i++){
                a[i] = scanner.nextInt();
                a[i] = p[a[i]];
                if(i >= 2){
                    minDist = Math.min(minDist, a[i] - a[i - 1]);
                    maxDist = Math.max(maxDist, a[i] - a[i - 1]);
                }
            }
            if(minDist <= 0 || maxDist > d) System.out.println(0);
            else{
                if(d - maxDist + 1 > n - maxDist - 1) System.out.println(minDist);
                else System.out.println(Math.min(minDist, d - maxDist + 1));
            }
        }
    }

}

分类讨论呐

C. Flexible String

题意

给定两个字符串 ，满足字符串 最多只有 种不同的字母，定义一次操作为：

1. 选择一个 ，将 放入集合 ；
2. 任意挑选一个字母，将其放入 。

其中，集合 内需要满足最多只有 个不同的字母。

寻找操作方案，让 的数量最大，并输出这个最大值。

表示对于 ，它们在 区间内的所有字符都一样。

思路

首先，我们只需考虑选 种不同的字母然后将其标记，最后遍历一遍计算答案即可。

因为数据量较小，且我们无需考虑选择字母的先后，那么 可行。

更具体地说，我们只需找出所有满足 的 的字母种类 ，然后枚举所有长度为 的组合并计算答案的最大值即可。

暴力即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100010;

int n, k;
char a[N], b[N];
bool same[N];
char cnt[26];
int ans;
vector<int> w;
bool use[26];

void dfs(int p, int t){
    if(t == k){
        int tot = 0, cur = 0;
        for(int i=0;i<n;i++){
            if(same[i] || use[a[i] - 'a']) tot ++;
            else{
                cur += (tot + 1) * tot / 2;
                tot = 0;
            }
        }
        if(tot != 0) cur += (tot + 1) * tot / 2;
        ans = max(ans, cur);
    }else{
        for(int i=p+1;i<w.size();i++){
            use[w[i]] = true;
            dfs(i, t + 1);
            use[w[i]] = false;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        memset(cnt, 0, sizeof cnt);
        cin >> n >> k >> a >> b;
        for (int i = 0; i < n; i++) {
            if (a[i] == b[i]) same[i] = true;
            else cnt[a[i] - 'a']++, same[i] = false;
        }
        w.clear();
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i]) {
                w.emplace_back(i);
                sum ++;
            }
        }
        if (k == 0) {
            int tot = 0, cur = 0;
            for (int i = 0; i < n; i++) {
                if (same[i]) tot++;
                else {
                    cur += (tot + 1) * tot / 2;
                    tot = 0;
                }
            }
            if (tot != 0) cur += (tot + 1) * tot / 2;
            cout << cur << '\n';
        } else {
            if (sum - k <= 0) {
                cout << (n + 1) * n / 2 << '\n';
            } else {
                ans = 0;
                for (int i = 0; i <= sum - k; i++) {
                    use[w[i]] = true;
                    dfs(i, 1);
                    use[w[i]] = false;
                }
                cout << ans << '\n';
            }
        }
    }
}

不要忘了初始化啊啊啊啊，在功亏一篑中屈服.jpg