小蓝xlanll

这个屌丝很懒，什么也没留下！

热门标签

C++牛客周赛题目分享（2）小红叕战小紫，小红的数组移动，小红的素数合并，小红的子序列求和

作者：小蓝xlanll | 2024-05-27 17:16:33

踩

1.前言

哈喽大家好喔，今天来给大家带来牛客周赛42部分题目的题解，无论你是小白，还是大牛，你一定都是能看懂的，希望对大家有所帮助，也欢迎大家多多交流，提出不一样但同样很有价值的看法。

2.四道题目

1.小红叕战小紫

1.题目描述

2.输入描述

3.输出描述

4.示例

5.题解与思路


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
 
int main(){
	char a[15];
    scanf("%s",a);
    int i=strlen(a);
    if(i!=1)printf("kou");
    else printf("yukari");
	return 0;
}

这道题就好像一道脑筋急转弯一样，需要简单思考一下，代码量不大，作为签到题也是蛮有趣的。思路：由于每一次小红都可以删除多个前缀或后缀字符，所以当字符串大于1时，小红只需要将字符串删到1即可，此时小红就赢。但如果本身字符串长度就为1，则小紫赢。

2.小红的数组移动

1.题目描述

2.输入描述

3.输出描述

4.示例

5.题解与思路


#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
long long num[100005];
long long ans = 0, n = 0, locate = 0;
char order[100005];
 
int main() {
    scanf("%lld",&n);
    for (int i = 0; i < n; i++) {
        scanf("%lld",&num[i]);
    }
    scanf("%s",order);
    for(int i=0;i<strlen(order);i++){
        if(order[i]=='L')locate=max(0ll,locate-1);
        else locate=min(n-1,locate+1);
        ans+=num[locate];
    }
    ans%=1000000007;
    printf("%lld", ans);
    return 0;
}

这道题就是需要简单模拟一下就OK了：num数组用于记录每一位分数，order数组用于记录指令，locate用于记录移动时候的所在坐标，关于如何处理到数组边界0和n-1时，用函数max以及min即可（需要注意一个小细节，使用这俩个数学函数的时候，需要保证比较的俩个数类型相同，不能一个为int，另一个为long long，所以在max中写0ll用于将默认的int强转long long）。

3.小红的素数合并

1.题目描述

2.输入描述

3.输出描述

4.示例

5.题解与思路


#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
 
long long num[100005];
long long ans = 0, n = 0 ,mi = 1e18 ,ma = 0;
char order[100005];
 
int main() {
    scanf("%lld",&n);
    for (int i = 0; i < n; i++) {
        scanf("%lld",&num[i]);
    }
    sort(num,num+n);
    int l=0 ,r=n-n%2-1;
    while(l<r){
        mi=min(mi,num[l]*num[r]);
        ma=max(ma,num[l]*num[r]);
        l++,r--;
    }
    if(n&1){
        mi=min(mi,num[n-1]);
        ma=max(ma,num[n-1]);
    }
    printf("%lld",ma-mi);
    return 0;
}

先理解题意：素数先进行合并，最后寻找极差的最小值，在正式模拟之前我们需要明确一个问题，任意俩个素数想成合并后，一定是一个合数，合数不被作为接下来的合并对象。

明确这个问题后我们开始正是分析，何时相减为最小，即我们需要保证合成操作结束后合数的最大没有那么大，最小没有那么小，所以这道题我们的思路是先将数组的质数进行sort快排（从小到大），每一合并操作都将数组中第一项和最后一项进行合并，最后寻找极差。

另外还有一个需要注意的问题是，数组中质数的个数可能为奇也可能为偶，偶数个数的时候正常处理，奇数个数的时候我们需要在合成前舍弃一个数，又由题意可得寻找极差的最小，那我们直接舍弃数组中的最大值即可，代码中是另外单开了一个if来处理奇数单独与舍弃的数进行大小比较。

4.小红的子序列求和

1.题目描述

2.输入描述

3.输出描述

4.示例

5.题解与思路


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
 
int n=0 ,k=0,ans=0;
int mod=1e9+7;
long long c[1010][1010];//预处理的杨辉三角
long long pow10[1010];//记录不同位数的倍数
char num[1010];//记录仅有数字组成的字符串
 
int main(){
    //根据题意输入
	scanf("%d%d",&n,&k);
    scanf("%s",num);
    //处理杨辉三角
    for(int i= 0;i<1000;i++){
        for(int j=0;j<=i;j++){
            if(j==0||i==j)c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
    }
    //处理倍数
    pow10[0]=1;
    for(int i=1;i<1000;i++)pow10[i]=pow10[i-1]*10%mod;
    //关键模拟
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            ans+=(num[i]-'0')*pow10[k-j-1]%mod*c[i][j]%mod*c[n-1-i][k-j-1]%mod;
            ans%=mod;
        }
    }
    printf("%d",ans);
	return 0;
}

这道题我本人认为还是很有价值的（这道题可以用dp来做，但这里本人没有使用这个方法），接下来将呈现我完整的思路历程：

首先我们先对示例中的数据进行模拟

我们模拟的思路是以每一个数为基准，算出每一个数字在每一个不同的数中的“价值”，向前向后延展。
第一个数为5，5的前面没有任何数，所以5只能做首位（这里说的都不是废话，都是对分析有帮助的），因为k=3，所以我们需要在后面的022中任选俩个数，即C（3，2），又因为5在百位，所以5的价值为5*100*C（3，2）=1500。
第二个数为0。当取5时，后面就从22中任取其一，即C（2，1）；当不取5时，就将后面的22全取，即C（2，2）。所以0的价值为0*100*C（2，2）+0*10*C（2，1）=0。
第三个数为2。推理过程同理，第一个2的价值为2*1*C（2，2）+2*10*C（2，1）=42。
第四个数为2。推理过程同理，第二个2的价值为2*1*C（3，2）=6。
综上，1500+0+42+6=1548，符合题意。

从特殊到一般，分析数据

我们发现每个数之前都有联系，如C（3，2）=C（2，2）+C（2，1），这不禁可以让你想到什么，这可就是大名鼎鼎杨辉三角啊，寻找每一位数字往前与往后所有的价值里面相乘的C( , )都和杨辉三角简直如出一辙。
再处理好每位数字出现次数的问题，接下来要来解决所在位数的问题。这里我们创建了一个pow10数组用于记录每个位数所包含的倍数。
处理完成后，我们接下来要通过代码实现了。

代码实现，有许多小细节以及需要分析的点

首先按照题目要求进行输入。
接着提前处理杨辉三角并存储进二维数组中。
接下来处理倍数，这些都是很基础的操作。
最后正式模拟：注意在计算过程中要不断的%1e9+7，防止溢出。先将着一位数字单独拿出来（num[i]-'0'），乘以对应的倍数（如题目中的5作首位时，其为百位，即k-1-j=2，）乘以左侧出现的次数c[i][j]，再乘以右侧出现的次数c[n-1-i][k-j-1]（这里都可以拿5来举例子，这里不再赘述），记得不断取模就好。
最后输出结果。

3.小结

今天的分享到这里就结束了，废了好大功夫才将这儿四道题讲的清晰明白，希望大家多多支持我哦~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/633028