【题解】牛客NOIP暑期七天营-普及组1

该题解同步于我的博客我的牛客博客

A

对于,直接开个桶统计即可。入门题目。

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153707&scrollToDetail=1

B

对于,直接按题目模拟就好。每次两个指针扫一下就是的了。整个加起来是的复杂度。可以结合代码理解。

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153710

C

对于直接copy代码然后完善一下头文件什么的就行了。
考虑这个是在干什么,其实就是求对于每个位置往前的前大的数的和。
那么对于,直接删掉第三重循环(考虑如果不选这个数,可以直接直接从转移,所以第三重循环完全多余)
对于,用一个数据结构动态维护前大即可。(这里用或者小根堆,都行)
复杂度

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153712

D

对于,很明显是个的算法..那么直接暴力枚举两个端点,然后暴力统计和取即可。
对于,注意到这个矩阵的生成方式有点特别,把它写出来,就会发现一个矩阵的和是一段乘上一段,那么便可以省去统计两重循环,复杂度
对于,考虑优化分的做法,30分的统计就是一个前缀和相乘的形式,那么要让它最大无非3种情况,正数最大正数最大,负数最小负数最小,正数最小负数最大,第三种又可以分为正数最小在中,正数最小在中两种情况,于是维护前缀和前缀,分类讨论一下,就可以解决了。
对于,既然是一段乘上一段,那么分别统计最大子段和和最小子段和即可。
最后根据的做法分四类情况讨论一下就好。这部分其实就是把分做法综合起来而已。
复杂度
至于怎么算最小子段和?全部取反求最大子段和再重新重新乘即可。

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41153727

全部评论
这个D数据也太水了吧,大多数人都是求两个最大字段和一乘就过了,丝毫没考虑最小乘最小,最小乘最大,子矩阵不能为空的情况。就对于 3 3 1 2 3 -1 -2 -3 这组数据,全场代码只有代码长度最长的三个可以过,其他代码输出的都不对。过了45个人其他人都可以用一组数据hack掉是不是这数据也太水了?包括现在看别人ac代码补题的也都只看到了两个最大字段一乘就过了,是不是应该考虑加强一下数据rejudge一下啊?
点赞 回复 分享
发布于 2019-08-19 12:30
请问B用最长公共子串做爆零是什么情况
点赞 回复 分享
发布于 2019-08-20 16:41
麻烦大神帮忙看看本程序为什么是零分? #include <bits/stdc++.h> usingnamespacestd; intmain() {     intn,b[127]={0},m;     cin>>n>>m;     chara[n+5];     cin>>a;     for(inti=0;i<n;i++)     b[a[i]-' ']++;     for(inti=1;i<=m;i++)     {         charc[5005];         cin>>c;         intb1[127]={0},sum=0;         for(intj=0;j<strlen(c);j++)         b1[c[j]-' ']++;         for(intj=0;j<100;j++)         sum+=min(b1[j],b[j]);         cout<<sum;     }     return0; }
点赞 回复 分享
发布于 2019-08-19 18:16
orzhy!
点赞 回复 分享
发布于 2019-08-19 14:21
我感觉我太***了,这么水的题都会炸……
点赞 回复 分享
发布于 2019-08-19 13:04

相关推荐

06-12 16:50
已编辑
小米_软件开发(准入职员工)
晓沐咕咕咕:评论区没被女朋友好好对待过的计小将可真多。觉得可惜可以理解,毕竟一线大厂sp。但是骂楼主糊涂的大可不必,说什么会被社会毒打更是丢人。女朋友体制内生活有保障,读研女朋友还供着,都准备订婚了人家两情相悦,二线本地以后两口子日子美滋滋,哪轮到你一个一线城市房子都买不起的996清高计小将在这说人家傻😅
点赞 评论 收藏
分享
评论
1
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务