当前位置:首页 » 《休闲阅读》 » 正文

C++牛客周赛43题目分享(3)小红平分糖果,小红的完全平方数,小苯的字符串变化,小红的子数组排列判断

20 人参与  2024年05月25日 19:24  分类 : 《休闲阅读》  评论

点击全文阅读


目录

​编辑

1.前言

2.四道题目

2.1小红平分糖果

2.1.1题目描述

2.1.2输入描述

2.1.3输出描述

2.1.4示例

2.1.5代码

2.2小红的完全平方数

2.1.1题目描述

2.1.2输入描述

2.1.3输出描述

2.1.4示例

2.1.5代码

2.3小苯的字符串变化

2.1.1题目描述

2.1.2输入描述

2.1.3输出描述

2.1.4示例

2.1.5代码

2.4小红的子数组排列判断

2.1.1题目描述

2.1.2输入描述

2.1.3输出描述

2.1.4示例

2.1.5代码

3.小结


1.前言

哈喽大家好啊,就在刚刚的周日,结束了牛客周赛 Round 43,今天继续为大家分享一些题解,希望对大家有所帮助,也请大家多多支持我哦~

2.四道题目

2.1小红平分糖果

2.1.1题目描述

2.1.2输入描述

2.1.3输出描述

2.1.4示例

2.1.5代码

#include<iostream>#include<algorithm>#include<cstring>using namespace std;int main(){int n=0;    scanf("%d",&n);    if(n%2==0)printf("%d %d",n/2,n/2);    else printf("-1");return 0;} 

第一道题就是一道简单的签到题,认真审题就没有问题~ 

2.2小红的完全平方数

2.1.1题目描述

2.1.2输入描述

2.1.3输出描述

2.1.4示例

2.1.5代码

#include<iostream>#include<algorithm>#include<cstring>#include<cmath>using namespace std;void func(){    long long x;    cin>>x;    long long l=sqrt(x);    long long r=l+1;    if((x-l*l)%2==0)cout<<(x-l*l)/2;    else cout<<(r*r-x)/2;    }int main(){    func();    return 0;}

第二道题考了一道有关完全平方数的问题:

在解决这道题之前,我们需要先明白完全平方数的一个性质,每一个完全平方数都是由连续的自然数平方得出,由于自然数的顺序是奇数偶数交错,且奇数乘以奇数仍未奇数,偶数乘以偶数仍未偶数,因此,每一个完全平方数也是奇数偶数相交错


在知晓这一个性质之后就可以开始敲代码了,先寻找输入的这个数在哪俩个相邻的完全平方数之间,然后寻找该数离哪一个完全平方数的距离是偶数,最后输出即可。

以上代码中是直接打印出了模拟出来的结果,可以先自己在演草本上写写。

2.3小苯的字符串变化

2.1.1题目描述

2.1.2输入描述

2.1.3输出描述

2.1.4示例

2.1.5代码

#include<iostream>#include<algorithm>#include<cstring>#include<cmath>using namespace std;const int N=100005;char s[N];int a[N],b[N];int m=0,locate=0,ans=1e9;int main(){    scanf("%s",s);m=strlen(s);    if(s[0]>='a'&&s[0]<='z')a[0]=1;    for(int i=1;i<m;i++){        if(s[i]>='a'&&s[i]<='z'){            a[i]=a[i-1]+1;        }        else a[i]=a[i-1];    }        for(int j=m-1;j>=0;j--){        if(s[j]>='A'&&s[j]<='Z'){            b[j]=b[j+1]+1;        }        else b[j]=b[j+1];    }        for(int n=0;n<m-1;n++){        ans=min(ans,a[n]+b[n+1]);    }    cout<<ans<<endl;return 0;} 

这一道题有一点前缀和的感觉,接下来是题目思路:

根据题意,任何一个位置都可以作为那一个“分界点”,即前面小写字母(包括本分界点)都变成大写字母,后面的大写字母(不包括本分界点)都变成小写字母。因此根据这个逻辑,我们可以将每一个字母都作为“分界点”并利用循环分别计算前后大小写字母个数。


先按照题意输入,然后先进行第一个字母的判断(因为循环处可能会出现越界,所以将边界点拿出来单独处理),接着俩个循环(一个正向,一个反向)分别计算字母数量,最后再利用一个循环取所有分界点中,俩个字母数目相加的最小值,最后输出即可。

2.4小红的子数组排列判断

2.1.1题目描述

2.1.2输入描述

2.1.3输出描述

2.1.4示例

2.1.5代码

#include<iostream>#include<algorithm>#include<cstring>using namespace std;int n=0,k=0;//数组大小与连续子数组大小int a[100005];//存储定义排列int b[100005];//存储当下数字状态int num=0;//存储当下k数组中有多少不同的数字int ans=0;//记录答案int main(){scanf("%d%d",&n,&k);    for(int i=0;i<n;i++)scanf("%d",&a[i]);        for(int i=0;i<k;i++){        b[a[i]]++;        if(b[a[i]]==1)num++;    }    if(num==k)ans++;//判断前k个是否满足题意        for(int i=k;i<n;i++){        b[a[i-k]]--;        if(b[a[i-k]]==0)num--;        b[a[i]]++;        if(b[a[i]]==1)num++;        if(num==k)ans++;    }    cout<<ans<<endl;return 0;} 

 这道题当时拿到手里的时候,感觉题目很清晰但自己唯一能想到的方法就是暴力(就是一直不断利用for循环),但我也知道这样也会爆TLE,所以接下来给大家分享一个比较良好的算法整体思路如下:


先来为大家讲解一下题意:

我这里输入的数组与k值分别为:

 数组:3 2 3 1 2 3 2 1 2 3 1 3

 k值:3

我们从第一个开始往后模拟(每次往后递推一位):

3 2 3不满足。2 3 1满足。3 1 2满足。1 2 3满足。2 3 2不满足。

3 2 1满足。2 1 2不满足。1 2 3满足。2 3 1满足。3 1 3不满足。

综上所述,输出结果应为6。


从以上的模拟我们应该能发现规律,每次往后地推一位只是少了第一个数多了最后一个数,在判断该子序列是否满足题意时也大可不必采用for循环大法,可以通过判断每位数出现的次数,如果出现的次数num刚好等于k,那么ans++;相反如果子序列中有重复的数,num<k,那么ans不做处理,最后输出即可。


(还有一点也需要提到的是,如果输入的数中有大于k的数字,应当continue,但对该题无影响,这样操作更加严谨)

3.小结

今天的这四道题虽然题目较为简单,但对平时解题时思路的拓展仍有借鉴意义,看完了不要忘了点个赞喔。感谢大家的支持~


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/113602.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 暴雨惊魂夜:+后续(陆舟吴佳)全书免费_(陆舟吴佳)暴雨惊魂夜:+后续后续(陆舟吴佳)
  • 我死遁后,族长悔疯了:结局+番外(我死遁后,族长悔疯了:结局+番外)_我死遁后,族长悔疯了:结局+番外(战痕音音)列表_笔趣阁(战痕音音)
  • 温长生陆扶摇(温长生陆扶摇:结局+番外)完结_温长生陆扶摇列表_笔趣阁(温长生陆扶摇:结局+番外)
  • 梁岁霍司年叶琳完本(又名:似月光吻野风)完本_完本梁岁霍司年叶琳完本(又名:似月光吻野风)
  • 全书免费周宴礼宋知蔓(又名:改嫁闲散王爷后负心将军跪求我原谅)_周宴礼宋知蔓(又名:改嫁闲散王爷后负心将军跪求我原谅)全书免费
  • 天鹅曾坠落(江舒白秦蓁)_天鹅曾坠落(江舒白秦蓁)
  • [爱的莫比乌斯环]精彩节选免费试读_江子安娇娇老公节选免费试读
  • 温长生陆扶摇:结局+完结宝藏_温长生陆扶摇:结局+完结宝藏
  • 好看的温长生陆扶摇:结局+完结宝藏_温长生陆扶摇:结局+完结宝藏
  • 全书免费娘子为师弟夺我秘宝后我灭她满门月婵柳安澜李凤年在线(又名:娘子为师弟夺我秘宝后我灭她满门)_娘子为师弟夺我秘宝后我灭她满门月婵柳安澜李凤年在线(又名:娘子为师弟夺我秘宝后我灭她满门)全书免费
  • 离婚后嫁死对头,冷傲总裁红了眼:+后续列表_离婚后嫁死对头,冷傲总裁红了眼:+后续(姜岁宁顾寒川)
  • 开学家长会上,丁克妻子成了竹马儿子的妈妈精彩节选试读_[淼淼杨文泽杨锐]精彩节选试读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1