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

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

题目描述

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)

本站内容未经许可，禁止任何网站及个人进行转载。