题解：P9010 [USACO23JAN] Leaders B

__CJY__ · 2025-02-09 21:34:28 · 题解

发现题解区里的解法咋都那么麻烦呢？这里介绍一种非常简单的方法，希望大家喜欢！

题意简述

这道题要求我们找出可能成为两种奶牛（根西岛 G 和荷斯坦 H）的“领导者”的所有可能的奶牛对。成为“领导者”的条件是：

其记录的名单上包含它的品种的所有奶牛。
其记录的名单上记录了另一品种奶牛的“领导者”。
思路

首先我们先找出第一种牛（假设为 G 品种）的最后一个牛的位置 r，再找出第二种牛（假设为 H 品种）的第一个牛的位置 l。

找出领导者对的判断条件为 i=1 \land E_i \ge r \lor E_i \ge l，解释如下：

这是因为这些奶牛需要知道至少一个 `H` 品种奶牛的信息。

两种条件满足一条即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
char s[maxn];
int n,l,r,e[maxn],ans;
int main(){
    cin>>n>>(s+1);
    for(int i=1;i<=n;i++) cin>>e[i];
    for(int i=1;i<=n;i++){
        if(s[i]==s[1]) r=i;
    }
    for(int i=2;i<=n;i++){
        if(s[i]!=s[1]){l=i;break;}
    }
    for(int i=1;i<l;i++){
        if((i==1&&e[i]>=r)||e[i]>=l) ans++;
    }
    cout<<ans;
}

纯原创，想了好久，求赞！

题解：P9010 [USACO23JAN] Leaders B

题意简述

思路

Code