码蹄集部分题目（2024OJ赛13期；贪心集训+递归集训）

1🐋🐋🐋red and blue（钻石；贪心）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例1

输入：
8
4
1 2 5 2
BRBR
2
1 1
BB
5
3 1 4 2 5
RBRRB
5
3 1 3 1 3
RBRRB
5
5 1 5 1 5
RBRRB
4
2 2 2 2
BRBR
2
1 -2
BR
4
-2 -1 4 0
RRRR
​
输出：
YES
NO
YES
YES
NO
YES
YES
YES

🐚备注

🐟题目思路

先提取一下题目信息：

• 1~n的排列组合

• B可以转化为小于等于自身的数

• R可以转化为大于等于自身的数

假设当前数是x，那么我们只要让B范围的数转化为1~x，R范围的数转化为x+1~n即可。

具体实现就是，排序，让B的排在前边，R的排在后边，并按ai数字大小排序。如果能变成1~n的排列组合，那么应满足a[i]=i。在B范围内需要满足a[i]>i+1（从0开始），在R范围内需要满足a[i]

MT3027 red and blue_哔哩哔哩_bilibili

🐟代码

#include 
​
using namespace std;
const int N=2e5+10;
struct NUM
{
    int x;
    char c;
}num[N];
​
bool cmp(NUM a,NUM b)
{
    if(a.c==b.c) return a.x
    else return a.c
}
​
int main( )
{
    int t,n;
    cin>>t;
    for(int k=0;k
    {
        string s;
        cin>>n;
        for(int i=0;i>num[i].x;
        cin>>s;
        for(int i=0;isize();i++) num[i].c=s[i];
        sort(num,num+n,cmp);
        bool flag=1;
        for(int i=0;i
        {
            if(num[i].c=='B'&&num[i].x1)
            {
                flag=0;
                break;
            }
            if(num[i].c=='R'&&num[i].x>i+1)
            {
                flag=0;
                break;
            }
        }
        if(flag==1) cout<<"YES"<
        else cout<<"NO"<
    }
    return 0;
}

2🐋🐋🐋正反卡片（钻石；贪心）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例1

🐚备注

🐟题目思路

要想让结果最小，就要每次都减去大的数，加上小的数。那就减去所有较大的数，加上所有较小的数。

两个数字a和b，sum=a+b，我们调整a和b使满足a>b，对于两张牌来说，如果sum[i]

MT3028 正反卡牌_哔哩哔哩_bilibili

🐟代码

#include 
​
using namespace std;
const long long N=5e5+10;
long long n,ans;
struct CARD
{
    long long a,b,sum;
}c[N];
​
bool cmp(CARD a,CARD b)
{
    return a.sum>b.sum;
}
​
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        cin>>c[i].a>>c[i].b;
        if(c[i].aswap(c[i].a,c[i].b);
        c[i].sum=c[i].a+c[i].b;
    }
    sort(c+1,c+1+n,cmp);//前一半是大的那组，后一半是小的那组
    for(long long i=1;i<=(n+1)/2;i++) ans-=c[i].a;
    for(long long i=(n+1)/2+1;i<=n;i++) ans+=c[i].b;
    cout<
    return 0;
}

3🐋🐋🐋战神小码哥（星耀；反悔贪心；小根堆）

时间限制：1秒

占用内存：128M

🐟题目描述

战神小码哥战斗力极高，每个单位时间都能斩杀一个敌人，且只能斩杀一个敌人。但是因为敌人太多，小码哥一人应敌，应接不暇。虽然有防御工事抵挡，但是防御工事只能抵挡一定时间，超出这个时间限度如果没有前来杀掉这个敌人，那么敌人就会进入城池，小码哥无法追杀。每杀一个敌人，都会掉落一定数量的元宝。小码哥会瞬移，不用考虑杀的当前敌人与下个敌人之间的距离。

现有N个敌人第00秒在城池门口集结，方便称呼，便称之为1，2，3…N。小码哥从第11秒开始可以击杀敌人。若没有小码哥，名叫ii的敌人会在Di的时刻攻入城池，小码哥可以在第ii秒及之前将其击杀，并会掉落Pi个元宝。

现问你小码哥在给定的上述敌军进攻详细情况信息下（可能会因为截止时间的问题杀不掉所有敌人），最终会最多收获多少元宝。

🐟输入输出格式

🐟样例

🐚样例1

🐚备注

🐟题目思路

这道题目所谓的贪心就是，我先把当前能打的敌人都打了，然后拿他的元宝，但是问题是，有可能我放过当前敌人打后边的敌人会拿到更多的元宝，这就需要“反悔”，所以这道题目利用小根堆来实现返回。

我们按照到达的时间d来排序并按一定规则放入小根堆，如果需要反悔，那么我们就反悔元宝数最小的那个敌人（就是堆首的敌人）。

发生反悔的时候一定是发现有两个或者更多d相等的敌人，那么这种情况下，我完全可以实现反悔最小的那个敌人来打当前的敌人。

MT3029 战神小码哥_哔哩哔哩_bilibili

🐟代码

#include 
​
using namespace std;
const long long N=1e5+10;
struct node
{
    long long d,p;
    bool operator>(const node &b) const { return p>b.p; }
}a[N];
long long n,ans;
priority_queue,greater > q;//小根堆
​
bool cmp(node a,node b)
{
    return a.d
}
​
int main( )
{
    cin>>n;
    for(long long i=1;i<=n;i++) cin>>a[i].d>>a[i].p;
    sort(a+1,a+1+n,cmp);
    for(long long i=1;i<=n;i++)
    {
        if(a[i].d>q.size()) q.push(a[i]);//按理说，q的第一个元素应该是d=1的，第二个元素应该是d=2的，……
        else if(q.top().p//这种情况就是如出现两个d=2的情况，我需要来判断堆头要不要反悔，也就是不打堆首那个敌人，打当前这个敌人
        {//当当前敌人的元宝数比堆首元素的元宝数多的时候，我们就反悔
            q.pop();
            q.push(a[i]);
        }
    }
    while(!q.empty())//对元宝数加和
    {
        ans+=q.top().p;
        q.pop();
    }
    cout<
    return 0;
}

4🐋🐋🐋天梯赛（钻石；反悔贪心；小根堆）

时间限制：1秒

占用内存：128M

🐟题目描述

众所周知，天梯赛是个人答题，团队记分。

假定在一个平行宇宙中，天梯赛的参赛人数没有限制，并且团队的分数是所有个人分数的总和。

这一年的天梯赛又快到来了，码蹄大学的ACM基地正在选择参赛队员。基地里共有N名队员，他们每一个人都有战斗力属性Ai，战斗力大的，在天梯赛中的得分就高，但是，队员们又有特殊的需求，如果选择了某一个同学ii，那么这个同学就不希望参加比赛的总人数超过Bi（即：只要选择第ii名同学，那么前去参赛的队伍人数就必须小于等于Bi）。

基地想知道 参赛同学的战斗力之和最大是多少，但是计算量太大，无法完成，所以想让你帮忙计算。

🐟输入输出格式

🐟样例

🐟题目思路

同理，这道题目我们也使用反悔贪心算法，用小根堆实现。

我们要知道加入这个队员是要求的最少队员数，所以我们按b的排序从大到小加入堆中，然后将超出的人数出堆，并且时刻记录更新总战斗力大小。

MT3030 天梯赛_哔哩哔哩_bilibili

🐟代码

#include 
​
using namespace std;
const long long N=1e5+10;
struct node
{
    long long a,b;
    bool operator>(const node &b) const { return a>b.a; }
}p[N];
long long n,ans,sum;
priority_queue,greater > q;//小根堆
​
bool cmp(node x,node y)
{
    return x.b>y.b;
}
​
int main( )
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i].a>>p[i].b;
    sort(p+1,p+1+n,cmp);//按人数b从大到小排序，这样可以先经历到允许的最大人数的队伍的情况
    for(int i=1;i<=n;i++)
    {
        //先都放入堆中
        q.push(p[i]);
        sum+=p[i].a;
        //然后将超出的人数去掉
        while(q.size()>p[i].b)
        {
            sum-=q.top().a;
            q.pop();
        }
        ans=max(ans,sum);//更新新的战斗力大小
    }
    cout<
    return 0;
}

5🐋🐋🐋硬币塔（黄金；递归）

时间限制：1秒

占用内存128M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例1

🐚备注

🐟题目思路

我们用coin[n]来记录n级硬币塔的总硬币数量，用gold[n]来记录n级硬币塔的金币数量。

根据题意，n级硬币塔构成如下：

• 第1层：1银

• 第2层：coin[n-1]

• 第3层：n金

• 第4层：coin[n-1]

• 第5层：1银

据此可以得出：

• coin[n]=2 * coin[n-1]+n+2

• gold[n]=2 * gold[n-1]+n

• coin[0]=gold[0]=1

接下来，就是找n级硬币塔从下向上数i个有几个金币：

• i属于第5层，即i<=1：一共有0个金币

• i属于第4层，即i<=coin[n-1]+1(这个1是第5层)：就去n-1级硬币塔找，就是find(n-1,i-1)（i-1是因为在当前塔已经找了1了，去n-1级塔只需再从下往上找i-1个就行了）

• i属于第3层，即i<=coin[n-1]+n+1：这时，coin[n-1]中的金币都属于我了，共gold[n-1]个，然后这n个金币中，只有i-coin[n-1]-1（减去下边两层）个属于我，就是gold[n-1]+i-coin[n-1]-1

• i属于第2层，即i<=1+coin[n-1]+n+coin[n-1]：这时，下边的coin[n-1]中的金币依旧全部属于我，即gold[n-1]个，中间n个金币也全属于我，上边coin[n-1]层中只有find(n-1,i-1-n-coin[n-1])个属于我，就是gold[n-1]+n+find(n-1,i-n-1-coin[n-1])

• i属于第1层，即其他情况：这时，直接就是全部n级硬币塔中的金币数量，也就是gold[n]

据此编辑出代码即可。

【码蹄集进阶塔全题解04】算法基础：递归/递推 MT2041 – MT2046_哔哩哔哩_bilibili

🐟代码

#include 
​
using namespace std;
#define ll long long
ll coin[50],gold[50];
ll find(ll n,ll i)
{
    if(i==0) return 0;//这句不能删，会WA
    if(n==0) return 1;
    if(i<=1) return 0;
    if(coin[n-1]+1>=i) return find(n-1,i-1);
    if(coin[n-1]+n+1>=i) return gold[n-1]+i-coin[n-1]-1;
    if(coin[n-1]*2+n+1>=i) return gold[n-1]+n+find(n-1,i-n-1-coin[n-1]);
    return gold[n];
}
int main( )
{
    ll n,i;
    cin>>n>>i;
    coin[0]=gold[0]=1;
    for(int j=1;j<=n;j++)
    {
        coin[j]=coin[j-1]*2+j+2;
        gold[j]=gold[j-1]*2+j;
    }
    cout<<find(n,i)<
    return 0;
}

6🐋🐋🐋三角形的个数（钻石；递归）

时间限制：1秒

占用内存：128M

🐟题目描述

🐟输入输出格式

🐟样例

🐚样例1

🐚备注

🐟题目思路

这道题目主要就是进行数学公式的推导，通过分别推导朝上和朝下的三角形的个数得到递推公式：

• 朝上的三角形个数：s(n)=Σ(n-i+2)*(n-i+1)/2

• 朝下的三角形个数：f(n)=f(n-2)+n*(n-1)/2

接下来就据此写代码就可以了。

【码蹄集进阶塔全题解04】算法基础：递归/递推 MT2041 – MT2046_哔哩哔哩_bilibili

🐟代码

#include 
​
using namespace std;
int f(int n)
{
    if(n==1) return 0;
    if(n==2) return 1;
    return f(n-2)+n*(n-1)/2;
}
int main( )
{
    int N,n;
    cin>>N;
    while(N--)
    {
        cin>>n;
        int sum1=0,sum2=0;
        for(int i=1;i<=n;i++) sum1+=(n-i+2)*(n-i+1)/2;
        sum2=f(n);
        cout<
    }
    return 0;
}

有问题我们随时评论区见~

⭐点赞收藏不迷路~