题目描述
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 . . . A ，可以直接统计A的数量，同理对于B . . . B也是类似的。对于A . . . B 或者B . . . A 则不需要考虑中间这一段。
所以记录上一个非⋅的下标记为last_idx，对于当前的j满足s[j]≠ ⋅ and s[last_idx] = s[j] ，则分类讨论(如果s[j]=='A'，A控制的村庄增加j - last_idx；否则B控制的村庄增加j - last_idx)，统计这一段的长度。
对于s[i]≠ ⋅ and s[last_idx] ≠ s[j]，（如：A..B，前后不一致）只需要统计当前s[j]带来的贡献（＋1）即可。
参考程序：
t=int(input())
for i in range(t):
s=input()
last_idx=-1
ansA=0
ansB=0
len_s=len(s)
for j in range(len_s):
if s[j] != '.':
if last_idx != -1 and s[last_idx] == s[j]:#与前一个字母比较
if s[j] == 'A':
ansA += j - last_idx
else:
ansB += j - last_idx
elif s[j] == 'A':
ansA+=1
else:
ansB+=1
last_idx = j
print(ansA,ansB)
本站内容未经许可，禁止任何网站及个人进行转载。
