目录

​编辑

1.前言

2.四道题目

1.小红叕战小紫

1.题目描述

2.输入描述

3.输出描述

4.示例

5.题解与思路

2.小红的数组移动

1.题目描述

2.输入描述

3.输出描述

4.示例

5.题解与思路

3.小红的素数合并

1.题目描述

2.输入描述

3.输出描述

4.示例

5.题解与思路

4.小红的子序列求和

1.题目描述

2.输入描述

3.输出描述

4.示例

5.题解与思路

3.小结

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.小结

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