Contestant. Rank 2756. Rating +40.
A. Flip Flop Sum
题意
给定一个只包含 \(1,-1\) 的序列，要求必须进行一次操作，将任意 \(i\) 对应的 \(a_i,a_{i+1}\) 的值取反，输出操作后序列总和的最大值。
思路
显然，若序列是 \(1,-1,1,-1,...\) ，那么操作对总和无影响。
当序列中存在 \(-1,-1\) 时，总和加 \(4\)。
其余情况，即序列中全是 \(1\)，总和减 \(4\)。
时间复杂度：\(O(n)\)
对应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
题意
给定长度为 \(n\) 的排列 \(p\)、长度为 \(m\) 的数组 \(a\)、以及一个正整数 \(d\)，其中数组 \(a\) 无重复元素，且对于任意 \(a_i\) 满足 \(a_i \in [1,n]\) 。定义一次操作为交换相邻元素，输出最少的操作数，满足存在 \(i \in [1,m)\)，有 \(p[a_i] \geq p[a_{i+1}]\) 或 \(p[a_{i+1}] > p[a_i] + d\)。
思路
显然，我们令 \(b[i]=p[a_i]\)，那么只要数组 \(b\) 是非递增的，就无需操作。
否则，我们可以执行下面的两个操作：
- 找出数组 \(b\) 中相邻差值最小的两个元素，将它们交换位置；
- 找出数组 \(b\) 中相邻差值最大的两个元素，将小的元素向左移，大的元素向右移，直至距离大于 \(d\)。
因为我们无需考虑最后数组的情况，所以我们只需计算一下即可：
- 对于操作 \(1\)，\(cnt=dist_{\min}\)；
- 对于操作 \(2\)，\(cnt=d-dist_{\max}+1\)。
显然，当 \(d\) 过大时，我们无法将元素的距离扩大到 \(d\)，此时只能执行操作 \(1\)。
时间复杂度：\(O(m)\)
对应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
题意
给定两个字符串 \(a,b\)，满足字符串 \(a\) 最多只有 \(10\) 种不同的字母，定义一次操作为：
- 选择一个 \(i\)，将 \(a_i\) 放入集合 \(Q\)；
- 任意挑选一个字母，将其放入 \(a_i\)。
其中，集合 \(Q\) 内需要满足最多只有 \(k\) 个不同的字母。
寻找操作方案，让 \(a[l,r]=b[l,r],1 \leq l \leq r \leq n\) 的数量最大，并输出这个最大值。
\(x_1[l,r]=x_2[l,r]\) 表示对于 \(x1,x2\)，它们在 \([l,r]\) 区间内的所有字符都一样。
思路
首先，我们只需考虑选 \(k\) 种不同的字母然后将其标记，最后遍历一遍计算答案即可。
因为数据量较小，且我们无需考虑选择字母的先后，那么 \(Dfs\) 可行。
更具体地说，我们只需找出所有满足 \(a[i] \neq b[i]\) 的 \(a[i]\) 的字母种类 \(cnt\)，然后枚举所有长度为 \(k\) 的组合并计算答案的最大值即可。
暴力即可。
时间复杂度：\(O(C_{cnt}^k \times n)\)
对应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