1606A - AB Balance(构造性算法+字符串+级)

1606A - AB Balance(源地址自⇔CF1606A

Problem

1606A - AB Balance(构造性算法+字符串+级)

1606A - AB Balance(构造性算法+字符串+级)

tag:

⇔构造性算法、⇔字符串、⇔级(*)

题意:

对于给定的只包含 \(a\) 和 \(b\) 的字符串,请你通过最少的修改次数,使得新的字符串中 \(ab\) 和 \(ba\) 的子串数量相同。输出这个新的子串

思路:

显然的,连续的 \(a\) 和连续的 \(b\) 交界处才有一次 \(ab\) ,连续的 \(b\) 和连续的 \(a\) 交界处才有一次 \(ba\) 。所以只要给定的字符串有偶数个交界,即符合题意。所以对于奇数个交界的字符串,只需要修改开始元素即可(使得交界变成偶数个)。可以证明,这种方法恒为最优的。

(附错误思路:如给定的字符串有奇数个交界,则去寻找字符串中最短的连续 \(a\) 或连续 \(b\) ,并修改这一整段。可以证明,这种方法不是最优的。)

AC代码:

//A WIDA Project
#include <bits/stdc++.h>
using namespace std;
long long T, num;
string s;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> T;
    while(T -- > 0) {
    	num = 0;
		cin >> s;
		for(int i = 1; i < (int)s.size(); i ++) {
			if(s[i] != s[i - 1]) {
				num ++;
			}
		}
		if(num % 2 == 1) s[0] == 'a'? s[0] = 'b': s[0] = 'a';
		cout << s << endl;
	}
	return 0;
}

错误次数:4次

原因:思路完全错误(错误思路见上)。


文 / WIDA
2021.10.30成文
首发于WIDA个人博客,仅供学习讨论


更新日记:
2021.10.30 成文

上一篇:2021.10.25


下一篇:AB 测试的原理及要点