NOC青少儿编程大赛编程马拉松Python决赛初中组-村庄与部落

更新时间：2024-11-06 15:20  浏览量：6

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

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

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

输入样例

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）即可。

python程序参考：