莆田网站建设培训,个人做电影网站服务器放国外安全吗,免费虚拟空间wordpress,微信设计网站一、题目描述Farmer John 有 N 头牛 (2≤N≤10^5)。 每头牛有对应的品种#xff1a;Guernsey or Holstein. 按照惯例#xff0c;这些牛站成一排#xff0c;编号从1到N。在某一天#xff0c;每头牛写了一个数字, 第i头牛写的数字Ei明确地表示了一个范围#xff0c;表示范围…一、题目描述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。输出输出有多少对可行的头领。样例输入复制4GHHG2 4 3 4输出复制1输入复制3GGH2 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.二、分析头领的条件第一包含同类所有的牛第二包含异类首领。后面的牛不可能包含前面的。G、H有前后顺序后面种类的奶牛的第一个必是头领后面的这种奶牛不可能是头领。结论靠后种类的奶牛只有一个头领排名靠前的奶牛如果是第一头牛并且包含所有同种类的牛或者包含靠后种类的头领则头领三、代码#include bits/stdc.h
using namespace std;
const int N1e510;
int n;
char s[N];
int a[N];
int main() {scanf(%d%s,n,s1);for(int i1;in;i) scanf(%d,a[i]);int pos,last;for(int i2;in;i){if(s[i]!s[1]){ //找位置靠后种类奶牛的第一个位置posi;break;}}for(int i1;in;i){if(s[i]s[1]){ //第一头种类奶牛的最后一个位置lasti;}}int ans0;for(int i1;ipos;i){if((i1a[i]last)||a[i]pos)ans;}printf(%d,ans);return 0;
}
