题解：P9010 [USACO23JAN] Leaders B

1.题意：

题意已经很清楚了，不需要过多的赘述了。

2.解法：

通过读题可知，一头牛是否是领导者的条件有两种，分别是

\begin{cases} 包括其品种的所有牛； \\ 其他品种的领导者。 \end{cases}

可以看出第一种领导者是很容易就能求出来的，对于第二种，我们可以可以从后往前遍历做前缀和，对于第

i

头牛来说，只要从

i \to e_i

这个区间中，有一只满足条件一的领导者，则它与这只领导者可以组成一个领导者对。对满足条件一的任意两头牛都可以成为一对领导者对。
这样我们就可以统计出所有的领导者对了。

3.代码：

奉上可(chou)爱(lou)的代码 :

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, e[100005], gl, gr, hl, hr, ans;
int psum[100005]; // 前缀和
string s;
bool isLeader[100005];

signed main() {
	cin >> n >> s;
	int len = s.size();
	s = " " + s;
    // 读入
	for (int i = 1; i <= len; i ++) {
		if (s[i] == 'G') {
			if (gl == 0) gl = i;
			else gr = i;
		} else {
			if (hl == 0) hl = i;
			else hr = i;
		}
	}
	for (int i = 1; i <= n; i ++) cin >> e[i];
	int k = 0;
	for (int i = 1; i <= gl; i ++)
		if (e[i] >= gr && s[i] == 'G') isLeader[i] = 1, k ++;
	for (int i = 1; i <= hl; i ++)
		if (e[i] >= hr && s[i] == 'H') isLeader[i] = 1, k ++;
	ans += k * (k - 1) / 2;
    // 计算有多少只符合条件一的奶牛，其中任意两只都能组成一个领导者对
	for (int i = n; i >= 1; i --) psum[i] = psum[i + 1] + isLeader[i];
	for (int i = n; i >= 1; i --)
		if (!isLeader[i]) ans += max(psum[i] - psum[e[i] + 1], 0ll);
    // 符合条件二的奶牛必须和使其成为一只领导者牛的满足条件一的领导者牛成为一个领导者对
	cout << ans << endl;
	return 0;
}

~~嘤嘤嘤，我这只蒟蒻只能想出这么繁琐的思路，和丑陋的代码了~~

题解：P9010 [USACO23JAN] Leaders B

文章操作

1.题意：

2.解法：

3.代码：

相关推荐

评论

题解：P9010 [USACO23JAN] Leaders B