深圳网站建设怎么样,广东人才网,广州建站模板,crm软件排行榜前十名题面翻译
题面描述
FJ 有 NNN 头奶牛#xff0c;每一头奶牛的品种是根西岛 G 或荷斯坦 H 中的一种。
每一头奶牛都有一个名单#xff0c;第 iii 头奶牛的名单上记录了从第 iii 头奶牛到第 EiE_iEi 头奶牛的所有奶牛。
每一种奶牛都有且仅有一位“领导者”#xff0c;对…题面翻译
题面描述
FJ 有 NNN 头奶牛每一头奶牛的品种是根西岛 G 或荷斯坦 H 中的一种。
每一头奶牛都有一个名单第 iii 头奶牛的名单上记录了从第 iii 头奶牛到第 EiE_iEi 头奶牛的所有奶牛。
每一种奶牛都有且仅有一位“领导者”对于某一头牛 iii如果它能成为“领导者”仅当它满足以下条件的至少一个 其记录的名单上包含它的品种的所有奶牛。 其记录的名单上记录了另一品种奶牛的“领导者”。
请求出有多少对奶牛可能成为两种奶牛的领导者保证存在至少一种。
数据范围
对于 100%100\%100% 的数据1≤N≤2×105,i≤Ei≤N1\leq N\leq 2\times 10^5,i\leq E_i\leq N1≤N≤2×105,i≤Ei≤N。
题目描述
Farmer John has NNN cows (2≤N≤105)(2 \le N \le 10^5)(2≤N≤105). Each cow has a breed that is either Guernsey or Holstein. As is often the case, the cows are standing in a line, numbered 1⋯N1 \cdots N1⋯N in this order.
Over the course of the day, each cow writes down a list of cows. Specifically, cow iii s list contains the range of cows starting with herself (cow iii) up to and including cow Ei(i≤Ei≤N)E_i(i \le E_i \le N)Ei(i≤Ei≤N).
FJ has recently discovered that each breed of cow has exactly one distinct leader. FJ does not know who the leaders are, but he knows that each leader must have a list that includes all the cows of their breed, or the other breed’s leader (or both).
Help FJ count the number of pairs of cows that could be leaders. It is guaranteed that there is at least one possible pair.
输入格式
The first line contains NNN.
The second line contains a string of length NNN , with the ith character denoting the breed of the iii-th cow (G meaning Guernsey and H meaning Holstein). It is guaranteed that there is at least one Guernsey and one Holstein.
The third line contains E1⋯ENE_1 \cdots E_NE1⋯EN.
输出格式
Output the number of possible pairs of leaders.
样例 #1
样例输入 #1
4
GHHG
2 4 3 4样例输出 #1
1样例 #2
样例输入 #2
3
GGH
2 3 3样例输出 #2
2提示
Explanation for Sample 1
The only valid leader pair is (1,2)(1,2)(1,2). Cow 111’s list contains the other breed’s leader (cow 222). Cow 222’s list contains all cows of her breed (Holstein).
No other pairs are valid. For example, (2,4)(2,4)(2,4) is invalid since cow 444’s list does not contain the other breed’s leader, and it also does not contain all cows of her breed.
Explanation for Sample 2
There are two valid leader pairs, (1,3)(1,3)(1,3) and (2,3)(2,3)(2,3).
Scoring
Inputs 3−53-53−5: N≤100N \le 100N≤100Inputs 6−106-106−10: N≤3000N \le 3000N≤3000Inputs 11−1711-1711−17: N≤2×105N \le 2 \times 10^5N≤2×105
算法思想
本题核心就是分别求G和H的领导者个数然后相乘得到最后答案。例如#2测试样例G的领导者有两个H的领导者有1个那么他们的组合就有两对。
对于某一头牛来说如果它能成为“领导者”仅当它满足以上述两个条件的至少一个。由于第二个条件依赖于第一个条件因此我们可以先求出满足第一个条件的领导者。
暴力枚举50分
朴素做法就是两层循环第一层循环枚举每一头奶牛iii第二层循环枚举i到a[i]a[i]a[i]计算其本身品种的奶牛头数判断其名单上是否记录了它的品种的所有奶牛。如果满足条件就将第i头奶牛进行标记。
然后再标记第二种情况的领导者也是两层循环第一层循环枚举每一头奶牛iii第二层循环枚举i到a[i]a[i]a[i]判断这之间是否存在另一种奶牛的领导者如果存在则标记。
最后统计两种奶牛领导者的数量将其相乘就是最终答案
时间复杂度
时间复杂度为O(n2)O(n^2)O(n2)。
代码实现
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 2e5 10;
char s[N];
int a[N], g[N], h[N];
int main()
{int n;cin n;cin s 1;int s1 0, s2 0;for(int i 1; i n; i ){if(s[i] G) s1 ;else s2 ;}for(int i 1; i n; i ) cin a[i];//处理第一种领导者其记录的名单上包含它的品种的所有奶牛for(int i 1; i n; i ){int gg 0, hh 0;for(int j i; j a[i]; j ){if(s[j] G) gg ;else hh ;}if(s[i] G gg s1) g[i] 1; //标记为领导者else if(s[i] H hh s2) h[i] 1; //标记为领导者}//处理第二种领导者其记录的名单上记录了另一品种奶牛的“领导者”。for(int i 1; i n; i ){for(int j i; j a[i]; j ){if(s[i] G h[j] 1){g[i] 1;break;}else if(s[i] H g[j] 1){h[i] 1;break;}}}int c1 0, c2 0;for(int i 1; i n; i )if(g[i]) c1 ;for(int i 1; i n; i )if(h[i]) c2 ;cout c1 * c2 endl;
}前缀和优化100分
朴素做法的问题在于使用了两层循环其实第二层循环可以使用前缀和进行优化用空间换时间。
s1[]前缀和数组s1[i]表示前i个字符中字符G的个数s2[]前缀和数组s2[i]表示前i个字符中字符H的个数gs[]前缀和数组gs[i]表示前i头牛中第一类G品种领导者的数量hs[]前缀和数组hs[i]表示前i头牛中第一类H品种领导者的数量
时间复杂度
朴素做法的时间复杂度为O(n)O(n)O(n)。
代码实现
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N 2e5 10;
char s[N];
int e[N], s1[N], s2[N], g[N], h[N], gs[N], hs[N];
int main()
{int n;cin n;cin s 1;for(int i 1; i n; i ) cin e[i];//s1[i]前缀和, 表示前i个字符中字符G的个数//s2[i]前缀和, 表示前i个字符中字符H的个数for(int i 1; i n; i ){s1[i] s1[i - 1], s2[i] s2[i - 1];if(s[i] G) s1[i] ;else s2[i] ;}//处理第一种领导者其记录的名单上包含本身的品种的所有奶牛for(int i 1; i n; i ){//gg表示从i到e[i]位置所有G的个数//hh表示从i到e[i]位置所有H的个数int gg s1[e[i]] - s1[i - 1], hh s2[e[i]] - s2[i - 1];//其记录的名单上包含本身的品种的所有奶牛if(s[i] G gg s1[n]) g[i] 1; //将i位置标记为G的领导者else if(s[i] H hh s2[n]) h[i] 1;//将i位置标记为H的领导者}//gs[i]前缀和表示前i个奶牛中G的第一种领导者个数//hs[i]前缀和表示前i个奶牛中H的第一种领导者个数for(int i 1; i n; i ){gs[i] gs[i - 1], hs[i] hs[i - 1];if(g[i]) gs[i] ;if(h[i]) hs[i] ;}//ga表示G的第一种领导者个数ha表示H的第一种领导者个数int ga gs[n], ha hs[n];//处理第二种领导者其记录的名单上记录了另一品种奶牛的“领导者”。for(int i 1; i n; i ){ //其记录的名单上记录了另一品种奶牛的领导者if(s[i] G (hs[e[i]] - hs[i - 1]) ! 0) ga ;else if(s[i] H (gs[e[i]] - gs[i - 1]) ! 0) ha ;}cout ga * ha endl;
}
