P1823 - [NewOJ Week 7] 村庄与部落 - New Online Judge (ecustacm.cn)

题目描述

n个村庄坐落成一条直线，A和B两个部落生活在这里。
每个村庄要么无人居住，要么被两个部落之一所占据。
如果一个无人居住的村庄两侧都是被部落A占据的村庄，那么这个村庄也视作被部落A占据；部落B亦同。
请求出被部落A和B分别占据的村庄个数。

输入格式

第一行为正整数T，表示存在T组测试数据，1≤T≤20。
每组测试数据输入一行，包含一个字符串s，表示每个村庄的状态,|s|≤100000
字符串仅包含A、B、. 三种字符，分别表示被部落A占据、被部落B占据，以及无人居住。

输出格式

每组测试数据输出两个整数，分别表示被部落A和B控制的村庄数量。

输入样例 复制

4
A..A..B...B
..A..
A....A
..B..B..B..

输出样例 复制

4 5
1 0
6 0
0 7

本题使用快慢指针的方式可以求解。因为题上所说如果一个无人居住的村庄两侧都是A或者都是B的话那么认为该村庄也被A或B占领了。所以定一个慢指针l到左边的部落，r到下一个右边的部落。使称为包夹之势。然后判断两侧部落是否一致来判断该加多少。

代码：

//使用快慢指针的做法
#include <bits/stdc++.h>

using namespace std;


int main() {
	int l, r;
	int n;
	cin>>n;
	string s;
	while (n--) {
		cin>>s;
		int ansA=0, ansB=0;
		int l = -1;//慢的一开始为-1作为开头的标志
		for (r = 0;r<s.size();r++) {
			if (s[r]!='.') {
				if (l!=-1&&s[l]==s[r]) {
					if (s[r]=='A') {
						ansA+=r-l;
					} else {
						ansB+=r-l;
					}
				} else if(s[r]=='A') {
					ansA++;
				} else {
					ansB++;
				}
				l = r;
			}
		}
		cout<<ansA<<" "<<ansB<<endl;
	}
	
	
	return 0;
}