Leader (USACO Bronze 2023 January)

Leaders (USACO Bronze 2023 January)

若干头G牛和H牛站成一排，每头牛ii有一个名单，包含自己到之后一个编号EiE_i之间所有牛。 一头牛成为领导者要满足两个条件之一，名单包含自己类别的所有牛，或者名单中包含另一类别的牛的领导者。 问有多少对牛可能是领导者。

此题初看可能有点绕，我们需要仔细一步步分析来找到条件可以推导出的中间结论：

  1. 首先，因为牛的名单是向后发展的，所以不会出现两个领导者的名单互相包含对方的情况。
  2. 由此可以推出，至少有一个领导者的名单包含了所有同类牛，当然它肯定也是这类牛中排在最前面的。
  3. 所以根据以上，我们有一个计数的办法了，就是先找出包含所有同类牛的领导者，然后再看另一类的牛哪些符合领导者的条件，就可以进行计数。

具体算法如下：

  1. 判断每类牛的头一个，它的名单是否包含所有本类牛。
  2. 如果是，则所有包含他的另外一类牛都是可以的，进行计数。
  3. 如果两类牛都符合条件1，那么这一对也符合条件，结果加一。但如果其中一头包含另外一头，则不用加了，因为这一对前面2中已经计算了。

复杂度是O(N)\mathcal{O}(N)。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
 
int n;
char s[100005];
int e[100005];
int g0 = -1, h0 = -1;   // beginning index
int g1, h1;             // ending index
bool gfirst, hfirst;    // g0 is leader, h0 is leader
 
int main() {
    scanf("%d", &n);
    scanf("%s", s);
    for (int i = 1; i <= n; i++)
        scanf("%d", &e[i]);
    for (int i = 1; i <= n; i++) {
        if (s[i-1] == 'G') {
            if (g0 == -1) g0 = i;
            g1 = i;
        } else {
            if (h0 == -1) h0 = i;
            h1 = i;
        }
    }
    gfirst = e[g0] >= g1;
    hfirst = e[h0] >= h1;
    int ans = 0;
    if (gfirst && hfirst) {
        ans++;          // 两个都包含全部牛的leader组成的pair
        if (g0 < h0 && e[g0] >= h0 || h0 < g0 && e[h0] >= g0)
            ans--;      // 减去重复计算
    }
    for (int i = 1; i <= n; i++) {   // 一个包含全部，一个包含另外一个leader
        if (s[i-1] == 'H' && gfirst && i <= g0 && e[i] >= g0) ans++;
        if (s[i-1] == 'G' && hfirst && i <= h0 && e[i] >= h0) ans++;
    }
    printf("%d", ans);
 
    return 0;
}