说明

此文仅为作者个人见解。原题链接：https://www.lanqiao.cn/oj-contest/senior-27/

总结

总的来说难度不是很大，主要考优化思维，大多数都用到了二分，第五题我想了很久的dp但是1e5的数据不知道怎么写了。二分使用的频率很高。

二分函数

cpp中自algorithm自带的二分函数：upper_bound & lower_bound

upper_bound 返回第一个大于或等于目标值的元素如果所有元素都小于目标值则返回last。
lower_bound 返回第一个大于目标值的元素如果所有元素都小于或等于目标值则返回last。

详细解释https://blog.csdn.net/weixin_45031801/article/details/137544229

1.抓猪拿国一

题目描述

蓝桥杯赛场上，选手小王脑洞大开，跑去问裁判：“裁判，蓝桥杯要是改成‘蓝桥抓猪大赛’，得抓多少头猪才能拿国一啊？”裁判愣了愣，但为了显摆幽默，淡定答道：“好说！想拿国一，从第一届开始，每届抓的猪数得是这一届的届数加上前面所有届数的总和。比如，第一届抓 $1$ 头，第二届抓 $1 + 2 = 3$ 头，第三届抓 $1 + 2 + 3 = 6$ 头 $\dots$ 今年是第十六届蓝桥杯，你自己算算吧！”现在，请你帮小王算算，要拿国一，总共得抓多少头猪？

思路

语法题，历遍1到16每次加上本身即可。时间复杂O(n)

代码

void solve()
{
    int ans = 0;
    for (int i = 1 ; i <= 16 ; i ++ ) ans += i;
    cout << ans << endl;
}

2.蓝桥字符

题目描述

给一个字符串S，找到 $S$ 中子序列 lan 的出现次数。这里的子序列是指从字符串 $S$ 中按顺序选取字符（不一定连续）组成的新字符串。

思路

动态规划，f[1],f[2],f[3]分别代表'l','a','n'出现的个数，从头到尾历遍，计算lan的个数 f[3]即为lan的个数时间复杂度O(n)

代码

void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    s = " " + s;

    vector<int> f(4 , 0);
    
    for (int i = 1 ; i <= n ; i ++ )
    {
      if (s[i] == 'l') f[1] ++;
      else if (s[i] == 'a') f[2] += f[1];
      else if (s[i] == 'n') f[3] += f[2];
    }

    cout << f[3] << endl;
}

3.蓝桥大史

题目描述

学校共有n个班级，每个班级都需要进行宣传。小蓝和小桥可以选择去不同的班级宣传，但为了公平起见，他们决定尽量平均分配任务。具体来说：
小蓝将去⌊n/2⌋个班级宣传。
小桥将去剩下的n−⌊n/2⌋个班级宣传。
对于第i个班级：
如果小蓝去宣传，他将获得A_i元的酬劳。
如果小桥去宣传，她将获得B_i元的酬劳。
小蓝和小桥希望最大化他们总共获得的酬劳，请你帮他们计算总酬劳最大值是多少？

思路

贪心，自定义小蓝和小桥的酬劳差值降序排序，前n/2让小蓝宣传后n/2让小桥去。时间复杂度O(nlogn)

代码

bool cmp(PII a , PII b)
{
    return a.first - a.second > b.first - b.second;
}

void solve()
{
    int n;
    cin >> n;
    vector<PII> a(n + 1);
    for (int i = 1 ; i <= n ; i ++ )
        cin >> a[i].first >> a[i].second;
    
    vector<bool> flag(n + 1);

    sort(all(a) , cmp);

    int ans = 0;
    for (int i = 1 ; i <= n / 2 ; i ++ ) ans += a[i].first;
    for (int i = n / 2 + 1 ; i <= n ; i ++ ) ans += a[i].second;

    cout << ans << endl;

}

4.拳头对决

题目描述

拳头的大小，成了这场友谊赛的焦点——谁的拳头大，谁就更有气势！两位教练各挑了N名队员，蓝队的第i个队员的拳头大小为A_i，红队的第i个队员的拳头大小为B_i。
比赛的流程是这样的：
红教练会按照顺序依次派出他的队员（先派第一位，然后第二位，以此类推）。
每当红教练派出一名队员展示拳头后，蓝教练需要从他尚未上场的队员中选择一位应战。
裁判会将蓝教练派出的队员的拳头大小与红教练所有已上场队员的拳头大小逐一比较。
每当蓝队员的拳头大小大于红队某位已上场队员的拳头，蓝教练便能赢得一次胜利（注意，这不是一对一的较量，而是以一敌多的挑战）。
这场比赛不为胜负，只为放松与切磋，可蓝教练心里却藏着小算盘：既要让队员们开心，也想借机秀一把带队本事，在蓝桥杯的训练营里留下点名声。现在，请你助蓝教练一臂之力，算出在最优策略下，他最多能拿下多少次胜利？

思路

法一：(贪心加小根堆做法)此题描述的有点问题，正确理解应该是红队依次上场,蓝队挑选一个上场，单挑在场所有红队选手，赢一次加一分。贪心加一点优先队列(小根堆)。有一个细节，将红队每次上场的选手存入堆中，蓝队从小到大排序依次用小的去比较，如果有一个是蓝队大，那么后面的剩下的蓝队成员一定比这个红队的大，都得一分。时间复杂度O(nlogn)
法二：(二分做法)对蓝队成员实力排序后进行二分，找到第一个比当前红队成员实力大的，那么后面一定都比他大，直接加上所有比他大的数量即可。需要注意的是计数方法(x到y有y-x+1个数) 。时间复杂度O(nlogn)

代码

1..贪心加小根堆

void solve()
{
    int n;
    cin >> n;

    vector<int> a(n + 1) , b(n + 1);

    for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];
    for (int i = 1 ; i <= n ; i ++ ) cin >> b[i];
    sort(all(a));

    int ans = 0;
    int cnt = 0;
    priority_queue<int , vector<int> , greater<int> > heap;

    for (int i = 1 ; i <= n ; i ++ )
    {
        heap.push(b[i]);
        while (heap.size() && heap.top() < a[i]) cnt ++ , heap.pop();
        ans += cnt;
    }

    cout << ans << endl;
}

2..二分

void solve()
{
    int n;
    cin >> n;

    vector<int> a(n + 1) , b(n + 1);

    for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];
    for (int i = 1 ; i <= n ; i ++ ) cin >> b[i];
    sort(all(a));

    int ans = 0;
    for (int i = 1 ; i <= n ; i ++ )
    {
        ans += n - (upper_bound(a.begin() + i , a.end() , b[i]) - a.begin()) + 1;
    }
    cout << ans << endl;
}

5.未来竞赛

题目描述：

本次大赛共有 N 位参赛者，第 i 位参赛者的编号为 i，来自编号为 A_i 的国家。比赛机房的电脑从左到右依次编号为 1 到 N，每位参赛者将在与自己编号相同的电脑上进行比赛。为了确保比赛的公平性，蓝桥杯官方决定对部分参赛者的电脑进行抽样监控。然而，监控方式必须满足以下条件：
1. 监控的电脑数量不能为零。
2. 同一个国家或地区的参赛者最多只能有两台电脑被监控，不能过多集中监控某个国家的选手。
3. 如果同一个国家或地区的两台电脑被监控，它们之间的距离不能超过 D。这里的距离定义为两台电脑编号之差的绝对值。
由于可能的监控方式实在太多，官方一时难以计算，于是他们向你求助，希望你能帮忙计算出所有合法的监控方式数量。
由于结果可能非常庞大，请将答案对 10^9 + 7 取模后输出。

思路

独立处理每个地区距离，二分计算距离为d内的选择方式。排列组合原理：每个地区的选一个+选两个的方式数量和相乘。对ans初始化1最后也要减去1，因为不能一个都不选。时间复杂度O(nlogn).
滑动窗口(双指针) r指针从0开始计算依次统计每个地区距离小于d的监控两个电脑的方案数量，最后ans *=(一个都不监控 + 监控一台 + 监控两台 ) 即可。最后输出的时候减一是总方案不能所有地区一个都不监控。时间复杂度O(n)

代码

1..二分+排列组合原理

const int mod = 1e9 + 7;

void solve()
{
    int n , d;
    cin >> n >> d;
    unordered_map<int , vector<int> > m;

    for (int i = 1 , temp ; i <= n ; i ++ ) 
    {
        cin >> temp; 
        m[temp].push_back(i);  
    }

    int ans = 1;
    for (auto &[mp , vec] : m)
    {
        int cnt = 0;

        for (int i = 0 ; i < vec.size() ; i ++ )
            cnt += (upper_bound(vec.begin() , vec.end() , d + vec[i]) - vec.begin()) - i - 1;
        cnt += vec.size() + 1; //加1是一个都不监控的情况
        ans *= cnt;
        ans %= mod;
    }
    cout << ans - 1 << endl;

}

2..滑动窗口

const int mod = 1e9 + 7;

void solve()
{
    int n , d;
    cin >> n >> d;

    unordered_map<int , vector<int> > m;

    for (int i = 1 ; i <= n ; i ++ )
    {
        int temp;
        cin >> temp;
        m[temp].push_back(i);
    }

    int ans = 1;

    for (auto &[mp , vec] : m)
    {
        int countSize = vec.size();
        
        int l = 0 , cnt = 0 , distance = 0;

        for (int r = 0 ; r < countSize ; r ++ )
        {
            distance = vec[r] - vec[l];
            
            while (distance > d && l < r)
            {
                l ++ ;
                distance = vec[r] - vec[l];
            }

            cnt += r - l;
        }
        ans *= (1 + cnt + countSize);
        ans %= mod;
    }

    cout << ans - 1 << endl;
}

6.备份比赛数据

题目描述

蓝桥杯大赛的组委会最近遇到了一个棘手的问题。他们有 N 台电脑需要备份比赛数据，每台电脑所需的备份时间分别为 A_1, A_2, ..., A_N 分钟。
备份必须按编号顺序依次进行，即先第 1 台，再第 2 台，依此类推。每台电脑的备份需要工作人员持续操作，且必须安排在同一天内完成。例如，如果某台电脑的备份需要 5 分钟，那这 5 分钟必须安排在同一天，不能拆分到两天。如果当天剩余时间不足以完成某台电脑的备份，那就只能推迟到第二天进行。
每台电脑备份完成后，系统需要等待 B_i 分钟才能开始下一台的备份。这段等待时间不需要工作人员操作，且可以跨天进行。例如，如果第 1 台电脑的备份在第 1 天结束时完成，且 B_1 = 10 分钟，那么第 2 台电脑的备份只需在第 2 天开始后等待 10 分钟就能进行。
现在，组委会希望尽量缩短每天的工作时间，以便工作人员能尽早下班休息。但上级有要求，所有电脑的备份必须在最多 T 天内完成。对此，请你帮助蓝桥杯组委会计算出每天最少需要安排的工作时间 M（M 最大不可超过 3600），以便所有电脑的备份能在 T 天内顺利完成。如果无论如何都无法满足条件，请直接输出 -1。