自动搬运

查看原文

来自洛谷，原作者为

	CJY 小升初蒟蒻||/article/ugxlm066/team/87748||没有一根棒棒糖解决不了的事情，如果有，就再来一根||最后在线时间：2025年8月24日20时21分

搬运于2025-08-24 22:44:32，当前版本为作者最后更新于2025-02-09 21:34:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

题意简述

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

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

思路

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

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

• $i=1 \land E_i \ge r$：如果当前奶牛是第一头奶牛，并且它的名单结束位置 $E_i \ge r$（即包含所有 G 品种奶牛），则它可以是一个领导者。这是因为如果第一头奶牛是 G，它需要知道所有 G 品种奶牛的信息。
• $E_i \ge l$：对于其他奶牛（不是第一头奶牛），如果它们的名单结束位置 $E_i \ge l$（即包含第一个 H 品种奶牛的位置），则它们也可以是一个领导者。 这是因为这些奶牛需要知道至少一个 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;
}

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