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

Week 4 3月12日

题目描述

有 N N N 头奶牛站成一排，从左到右依次编号为 1 ∼ N 1 \sim N 1∼N。 每头奶牛要么是根西牛（用 G 表示），要么是荷斯坦牛（用 H 表示）。 每头奶牛都写下了一份奶牛名单，其中第 i i i 头奶牛写下的名单中包含 [ i , E i ] [i,E_i] [i,Ei​]（ i ≤ E i ≤ N i \le E_i \le N i≤Ei​≤N）范围内的所有奶牛。 现在，我们要在每个品种的奶牛当中选出一个领导者。 要求，每个领导者写下的奶牛名单应满足以下两个条件中的至少一个：

• 名单中包含其品种的所有奶牛。
• 名单中包含另一品种的领导者。 请问，一共有多少个满足条件的选择方案。

输入格式

第一行包含整数 N N N。 第二行包含一个长度为 N N N 的由 G 和 H 构成的字符串，其中第 i i i 个字符表示第 i i i 头奶牛的品种（G 为根西牛，H 为荷斯坦牛）。 第三行包含 N N N 个整数 E 1 , E 2 , … , E N E_1,E_2,…,E_N E1​,E2​,…,EN​。

输出格式

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

数据范围

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

输入样例1：

4 GHHG 2 4 3 4

输出样例1：

1

样例1解释

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

输入样例2：

3 GGH 2 3 3

输出样例2：

2

样例2解释

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

• 选择奶牛 1 1 1 和奶牛 3 3 3。
• 选择奶牛 2 2 2 和奶牛 3 3 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 如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！ 如果喜欢的话，请给博主点个关注 谢谢