2.2 vp Codeforces Round #848 (Div. 2)

A - Flip Flop Sum

题意

给出长度为n的序列a，a中只包括1和-1，你必须操作一次，让相邻两个元素由1变-1或由-1变1，问操作后数组总和最大多少

思路

暴力即可

void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1);
	int sum = 0;
	for (int i = 1; i <= n; i ++) cin >>a[i], sum += a[i];
	int ans = sum;
	sum = -INF;
	for (int i = 1; i < n; i ++) {
		int x = ans;
		if (a[i] == 1) x -= 2;
		else x += 2;
		if (a[i + 1] == 1) x -= 2;
		else x += 2;
		sum = max(x, sum);
	}
	
	cout <<sum <<endl;
}

B - The Forbidden Permutation

题意

给出长度为n的排列，还有m个排列中的数字组成的序列a，和d
若m个数字都满足条件
则是不好的
问最少操作多少次可以使a好

思路

本题切记要看清楚题，是全满足条件才不好，只要有一个不满足条件即好。我看成了必须都要满足条件才好，到打完了都不知道为什么不对。
读清楚题目后就很简单了，只有两种方法，一是将\(a_{i + 1}\)放到\(a_i\)前面，二是将\(a_{i + 1}\)放到\(a_i\)距离为d的后面，对每个相邻对儿找一遍最小操作数即可

void solve() {
	int n, m, d;
	cin >> n >> m >> d;
	vector<int> a(n + 1), p(n + 1), b(m + 1);
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		p[a[i]] = i;
	}
	
	for (int i = 1; i <= m; i ++) {
		cin >> b[i];
	}
	
	int ans = INF;
	for (int i = 1; i < m; i ++) {
		if (p[b[i + 1]] < p[b[i]] || p[b[i]] + d < p[b[i + 1]]) {     //若不满足条件，直接好，输出0
			ans = 0;
			break;
		}
		
		int x, y;
		x = p[b[i + 1]] - p[b[i]];                                   //放到前面
		if (d + 2 <= n) {                                            //放到后面
			y = d + 2 - (p[b[i + 1]] - p[b[i]] + 1);
		}else y = INF;
		ans = min(ans, min(x, y));
	}
	
	cout << ans << endl;
}

C - Flexible String

题意

给出字符串a, b。a只能更换k种字符，问a更换完字符后，和b最多有多少个区间是相同的

思路

暴力枚举即可，使用二进制枚举法，将a中出现过的字符数记录下来，然后枚举它是否出现，当选中了k种就去和b对照，求出区间数，然后求最大值即可

void solve() {
	int n, k;
	cin >> n >> k;
	string a, b;
	cin >> a >> b;
	vector<int> ap(30, 0), bn(30, 0);
	int cnt = 0;
	for (int i = 0; i < n; i ++) {
		if (!ap[a[i] - 'a']) ap[a[i] - 'a'] = 1;
	}
	
	for (int i = 0; i < 26; i ++) {
		if (ap[i]) bn[cnt ++] = i;
	}
	
	int cs = min(cnt, k);
	
	int q = pow(2, cnt) - 1;
	LL ans = 0;
	for (int i = 0; i <= q; i ++) {
		vector<int> use(30, 0);
		int num = 0, tmp = i, tt = 0;
		while (tmp) {
			if (tmp & 1) {
				use[bn[tt]] = 1;
				num ++;
			}
			tmp >>= 1;
			tt ++;
		}
		
		if (cs == num) {
			string t = a;
			for (int j = 0; j < n; j ++) {
				if (use[t[j] - 'a']) {
					t[j] = b[j];
				}
			}
			
			LL sum = 0, cnt = 0;
			
			for (int j = 0; j < n; j ++) {
				if (t[j] == b[j]) cnt ++;
				else {
					sum += cnt * (cnt + 1) / 2;
					cnt = 0;
				}
				if (j == n - 1) sum += cnt * (cnt + 1) / 2;
			}
			
			ans = max(ans, sum);
		}
	}
	
	cout << ans << endl;
}

总结

读错题害死人。二进制枚举法确实不错，学到了