[USACO2023-JAN-Bronze] T1 LEADERS 题解

一、题目描述

Farmer John 有 N 头牛 (2≤N≤10^5)。 每头牛有对应的品种：Guernsey or Holstein. 按照惯例，这些牛站成一排，编号从1到N。在某一天，每头牛写了一个数字, 第i头牛写的数字Ei明确地表示了一个范围，表示范围从i到Ei(i≤Ei≤N)的每一头牛都归它管(包含Ei)。FJ最近发现每个种类的牛都有它明确的头领。FJ不知道谁才是头领，但是他知道每个头领写的范围必须包含它的种类的所有牛，或者包含其他种类的牛的头领(或者都有)。帮助FJ计算有多少对可能的头领，数据确保至少有一对可能的头领。

输入

第一行包含一个整数 N.

第二行包含一个长度为N的字符串，第i个字符表示第i头牛的种类(G 表示 Guernsey ， H 表示 Holstein). 数据确保至少有一头Guernsey 和一头Holstein.

第三行包含N个整数，表示E1……En。

输出

输出有多少对可行的头领。

样例

输入

复制

4

GHHG

2 4 3 4

输出

复制

1

输入

复制

3

GGH

2 3 3

输出

复制

2

说明

样例1说明：只有一对可行的头领(1,2). 第1头牛包含其他种类的头领(cow 2). 第二头牛包含所有它种类的牛(Holstein).没有其他可行的头领对。例如，(2,4)不行是因为第4头牛的范围没有包含其他种类的头领，也没有包含它的种类的其他所有牛。

样例2说明：有两个可行的头领对： (1,3) 和 (2,3).

• Inputs 3-5: N≤100

• Inputs 6-10: N≤3000

• Inputs 11-17: No additional constraints.

二、分析

1. 头领的条件：第一，包含同类所有的牛，第二，包含异类首领。

2. 后面的牛不可能包含前面的。

3. G、H有前后顺序，后面种类的奶牛的第一个必是头领，后面的这种奶牛不可能是头领。

4. 结论：靠后种类的奶牛只有一个头领，排名靠前的奶牛如果是第一头牛并且包含所有同种类的牛或者包含靠后种类的头领，则头领++

三、代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
char s[N];
int a[N];
int main() {scanf("%d%s",&n,s+1);for(int i=1;i<=n;i++) scanf("%d",&a[i]);int pos,last;for(int i=2;i<=n;i++){if(s[i]!=s[1]){        //找位置靠后种类奶牛的第一个位置pos=i;break;}}for(int i=1;i<=n;i++){if(s[i]==s[1]){        //第一头种类奶牛的最后一个位置last=i;}}int ans=0;for(int i=1;i<pos;i++){if((i==1&&a[i]>=last)||a[i]>=pos)ans++;}printf("%d",ans);return 0;
}