【蓝桥杯集训·每日一题2025】 AcWing 4888. 领导者 python

AcWing 4888. 领导者

Week 4
3月12日

题目描述

有 $N$ 头奶牛站成一排，从左到右依次编号为 $1\sim N$。

每头奶牛要么是根西牛（用 G 表示），要么是荷斯坦牛（用 H 表示）。

每头奶牛都写下了一份奶牛名单，其中第 $i$ 头奶牛写下的名单中包含 $[i,E_i]$（$i\le E_i\le N$）范围内的所有奶牛。

现在，我们要在每个品种的奶牛当中选出一个领导者。

要求，每个领导者写下的奶牛名单应满足以下两个条件中的至少一个：

• 名单中包含其品种的所有奶牛。
• 名单中包含另一品种的领导者。

请问，一共有多少个满足条件的选择方案。

输入格式

第一行包含整数 $N$。

第二行包含一个长度为 $N$ 的由 G 和 H 构成的字符串，其中第 $i$ 个字符表示第 $i$ 头奶牛的品种（G 为根西牛，H 为荷斯坦牛）。

第三行包含 $N$ 个整数 $E_1,E_2,\dots ,E_N$。

输出格式

一个整数，表示满足条件的选择方案数量。

数据范围

$2\le N\le 10^5$,
$i\le E_i\le N$,
保证根西牛和荷斯坦牛的数量均不小于 $1$。
保证至少存在一个满足条件的选择方案。

输入样例1：

4
GHHG
2 4 3 4

输出样例1：

1

样例1解释

唯一满足条件的方案是选择奶牛 $1$ 和奶牛 $2$ 作为领导者，奶牛 $1$ 的名单中包含奶牛 $2$（另一品种的领导者），奶牛 $2$ 的名单中包含所有同品种奶牛。

其它方案均不满足条件，例如，选择奶牛 $2$ 和奶牛 $4$ 作为领导者就不可行，因为奶牛 $4$ 的名单中既不包含另一品种的领导者，也不包含所有同品种奶牛。

输入样例2：

3
GGH
2 3 3

输出样例2：

2

样例2解释

一共有 $2$ 种满足条件的选择方案：

• 选择奶牛 $1$ 和奶牛 $3$。
• 选择奶牛 $2$ 和奶牛 $3$。

分类讨论

AC_code

n = int(input())  
s = [0] + [0 if x == 'G' else 1 for x in input()]  
e = [0] + list(map(int, input().split()))  
  
l = [-1, -1]  # 第一次出现的位置  
r = [-1, -1]  # 最后一次出现的位置  
  
for i in range(1, n + 1):  
    x = s[i]  
    if x == 0 and l[0] == -1:  
        l[0] = i  
    elif x == 1 and l[1] == -1:  
        l[1] = i  
    if l[0] != -1 and l[1] != -1:  
        break  
  
for i in range(n, 0, -1):  
    x = s[i]  
    if x == 0 and r[0] == -1:  
        r[0] = i  
    elif x == 1 and r[1] == -1:  
        r[1] = i  
    if r[0]!= -1 and r[1]!= -1:  
        break  
  
ans = 0  
if e[l[0]] >= r[0] and e[l[1]] >= r[1]:  
    ans += 1  
  
a = s[1]  
b = a ^ 1  
if e[l[b]] >= r[b]:  
    for i in range(1, l[b]):  
        if e[i] >= l[b]:  
            ans += 1  
    if e[1] >= r[a] and e[1] >= l[b]:  
        ans -= 1  
print(ans)

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢