当前位置：首页 > article >正文

acwing 每日一题4888. 领导者

article 2025/4/1 0:06:17

题目简述：

思路梳理：

总代码：

https://www.acwing.com/problem/content/description/4891/

题目简述：

有两个品种的奶牛，分别为G和H，我们要在每个品种中各找一头牛当领导者，最后输出全部的可能方案，当领导牛是有条件的，要么在其管辖范围内有其品种的全部牛，要不在其管辖范围内有另一品种牛的领导者；

思路梳理：

有一种很明显的思路：先判断在每头牛的管辖范围内有没有其品种的全部牛，如果有就代表这个牛能当领导牛，标记一下，在判断第二条件，因为第二个条件是依附于第一个条件而存在的，最后找出两种牛的各个领导牛的可能数，相乘即为答案；

这个思路很简单，但是代码实现较为复杂且易错，处理这些条件需要开三个前缀和数组，四个计数器，一个状态数组。。。（可能有其他更好的思路，但我只想到了这一个（））

需要注意的是：分类讨论计算当前品种的奶牛的前缀和时，也要更新另一品种的前缀和，让另一品种的前缀和等于前一状态即可，要不会导致状态丢失（前缀和为0）；【我因为这个调试了半天】

总代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
// s1 用于记录前缀位置中 'G'的数量，s2 用于记录前缀位置中 'H'的数量
// s3 用于记录领导牛的奶牛数量的前缀和
int s1[N], s2[N], s3[N]; 
int n, cnt1, cnt2, res1, res2; 
// n：奶牛总数；cnt1：根西牛（'G'）的总数；cnt2：荷斯坦牛（'H'）的总数
// res1：满足条件的根西牛领导者的可选数量；res2：满足条件的荷斯坦牛领导者的可选数量
char s[N]; // 存储每头奶牛的品种（'G' 或 'H'）
int a[N]; 
bool b[N]; // 标记某头奶牛是否已满足成为领导者的条件（条件一）

int main() {
    cin >> n; // 输入奶牛的总数
    // 遍历每头奶牛，统计品种信息并计算前缀和
    for (int i = 1; i <= n; i++) {
        cin >> s[i]; // 输入第 i 头奶牛的品种
        if (s[i] == 'G') {
            // 更新根西牛的前缀数量，荷斯坦牛前缀数量不变，根西牛总数加 1
            s1[i] = s1[i - 1] + 1; 
            s2[i] = s2[i - 1]; 
            cnt1++; 
        }
        if (s[i] == 'H') {
            //更新荷斯坦牛的前缀数量，根西牛前缀数量不变，荷斯坦牛总数加 1
            s2[i] = s2[i - 1] + 1; 
            s1[i] = s1[i - 1]; 
            cnt2++; 
        }
    }

    // 处理每头奶牛写下的名单范围，判断是否满足条件一（名单包含其品种所有奶牛）
    for (int i = 1; i <= n; i++) {

        cin >> a[i]; 
        
        if (s[i] == 'G') {
            // 判断该根西牛的名单是否包含所有根西牛
            if (s1[a[i]] - s1[i - 1] == cnt1) { 
                res1++; // 根西牛领导者可选数量加 1
                b[i] = 1; // 标记该奶牛已满足条件
                s3[i] = s3[i - 1] + 1; // 更新满足条件的奶牛数量前缀和
            } else {
                s3[i] = s3[i - 1]; // 不满足条件，前缀和不变
            }
        }

        if (s[i] == 'H') {
            // 判断该荷斯坦牛的名单是否包含所有荷斯坦牛
            if (s2[a[i]] - s2[i - 1] == cnt2) { 
                res2++; // 荷斯坦牛领导者可选数量加 1
                b[i] = 1; // 标记该奶牛已满足条件
                s3[i] = s3[i - 1] + 1; // 更新满足条件的奶牛数量前缀和
            } else {
                s3[i] = s3[i - 1]; // 不满足条件，前缀和不变
            }
        }
    }

    // 处理未标记的奶牛，判断是否满足条件二（名单包含另一品种的领导者）
    for (int i = 1; i <= n; i++) {
        if (b[i]) continue; // 已满足条件一，跳过
        // 判断该奶牛的名单中是否包含已满足条件的奶牛（即是否包含另一品种的领导者）
        if (s3[a[i]] - s3[i - 1] > 0) { 
            if (s[i] == 'G') res1++; // 根西牛满足条件二
            else res2++; // 荷斯坦牛满足条件二
        }
    }

    cout << res1 * res2 << endl; // 输出满足条件的选择方案数量（根西牛与荷斯坦牛可选领导者数量的乘积）
    return 0;
}