AT_diverta2019_c 题解-JZTXT

小蒟蒻第一次写题解，不好请指出。

思路1

找每个字符串中的 AB 的数量；
暴力枚举两个字符串的第一个字符和最后一个字符能否组成 AB；

然后就是劈里啪啦敲代码。

#include<iostream>
#include<string>
using namespace std;
struct str {//竟然还用结构体
	string s;
}a[10010];
int main()
{
	int n;
	int sum = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].s;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < a[i].s.size(); j++) {
			if (a[i].s[j] == 'A' && a[i].s[j + 1] == 'B') {
				sum++;
				a[i].s[j] = '0';
				a[i].s[j + 1] = '0';
			}
		}
		if (a[i].s[0] == 'B') {
			for (int j = 1; j <= n; j++) {
				if (j != i) {
					if (a[j].s[a[j].s.size() - 1] == 'A') {
						sum++;
						a[i].s[0] = '0';
						a[j].s[a[j].s.size() - 1] = '0';
						break;
					}
				}
			}
		}
		if (a[i].s[a[i].s.size() - 1] == 'A') {
			for (int j = 1; j <= n; j++) {
				if (j != i) {
					if (a[j].s[0] == 'A') {
						sum++;
						a[i].s[a[i].s.size() - 1] = '0';
						a[j].s[0] = '0';
						break;
					}
				}
			}
		}
	}
	cout << sum;
	return 0;
}

结果不出意料的错了，那么就得换一种思路了。

思路2

一样，找每个字符串中的 AB 的数量，设为 $sum$；
找开头不是 B 结尾是 A 的字符串数量，设为 $a$；
找开头是 B 结尾不是 A 的字符串数量，设为 $b$；
找开头是 B 结尾是 A 的字符串数量，设为 $ab$；
判断：
- 若 $a$ 大于 $0$ 并且 $b$ 大于 $0$、$ab$ 大于 $0$，那么把 $sum$ 先加上 $ab$ 加 $1$，因为第 $3$ 种字符串相结合再结合一个第 $1$ 和 $2$ 种字符串都会产生 $ab+1$ 个 AB。然后 $sum$ 再加上 $\min(a-1,b-1)$，因为要使第 $1$ 种字符串与第 $2$ 种字符串相结合，若一种不够，那么只能取最小值，至于为什么要减 $1$ ，是因为前面说到第 $1$ 或 $2$ 种字符串与第 $3$ 种字符串相结合。
- 若 $a$ 大于 $0$ 并且 $b$ 大于 $0$ 但是 $ab$ 等于 $0$，那么把 $sum$ 加上 $\min(a,b)$，因为既然没有第 $3$ 种字符串，那么只能第 $1$ 种字符串与第 $2$ 种字符串相结合，并且不减 $1$ 取最小值。
- 若 $a$ 大于 $0$ 并且 $ab$ 大于 $0$ 但是 $b$ 等于 $0$，那么把 $sum$ 加上 $ab$,因为要把第 $1$ 类字符串与第 $3$ 类字符串相结合，必定会浪费掉 $1$ 个 AB，所以不用加 $1$。
- 若 $b$ 大于 $0$ 并且 $ab$ 大于 $0$ 但是 $a$ 等于 $0$ 与上面相同。
- 若只有 $ab$ 大于 0，那么 $sum$ 要加上 $ab-1$，因为只有第 $3$ 类字符串相结合，必定会浪费掉 $1$ 个 AB。

理论存在，实践开始

代码

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
	int n;
	int sum = 0;
	int a = 0, b = 0, ab = 0;
	//  A结尾  B开头   A结尾以及B开头
	string s[10010];
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < s[i].size() - 1; j++) {
			if (s[i][j] == 'A' && s[i][j + 1] == 'B') {
				sum++;
				/*
				s[i][j] = '0';
				s[i][j + 1] = '0';
				不是一次性
				*/
			}
		}
		if (s[i][0] == 'B' && s[i][s[i].size() - 1] != 'A') b++;
		else if (s[i][0] != 'B' && s[i][s[i].size() - 1] == 'A') a++;
		else if (s[i][0] == 'B' && s[i][s[i].size() - 1] == 'A') ab++;
	}
	if (a > 0 && b > 0 && ab > 0) sum += ab + 1 + min(a - 1, b - 1);
	else if (a > 0 && b > 0 && ab == 0) sum += min(a, b);
	else if (a > 0 && b == 0 && ab > 0) sum += ab;
	else if (a == 0 && b > 0 && ab > 0) sum += ab;
	else if (a == 0 && b == 0 && ab > 0) sum += ab - 1;
	cout << sum;
	return 0;
}