我训练赛中做出4题, 赛后补4题, 最终使用word完成解题报告, 报告上呈现出9题.

补题数量: 8/ 10.

收获感悟:这次训练赛是对我们从寒假开始上的课的一个总结,感觉自己学的一点都不扎实,前缀和差分的知识很简单,但是一遇到具体题目结合起来就令我显得十分吃力,自己基础不牢,做题总是在乎做题量,做出的题目没有分类总结,做不出来的题目也没有去反思总结,想的很多,行动起来却十分吃力,还是需要多刷题,要是能有一个基础算法的刷题网站就好了,还要继续努力,希望自己不要被acm扫地出门,在这个大家庭学习非常快乐,卑微.jpg。

我会更着学长好好学习算法的,希望自己能对一些非常长的题目静下心来分析,用心学习,不能三心二意。

通过这次训练赛,加强了我对前缀和和差分以及二分算法等一些基础算法的认识,认识到了自己与其他人的差距,在接下来的训练我会继续努力听讲学习算法知识。

A:幸运数字们https://vjudge.csgrandeur.cn/problem/51Nod-2091

思路:暴力循环,对每一个区间内的数进行取余10后除以10,直到区间内的数的位数中有7输出这个数,并停止循环。

考察内容:循环

#include<bits/stdc++.h>
using namespace std;
int main()
{
int l,r;
scanf("%d%d",&l,&r);
int flag=0;
for(int i=l;i<=r;i++)
{int x=i;while(x!=0){if(x%10==7){printf("%d\n",i);flag=1;break;
}
x=x/10;}
}
if(flag==0)
{
printf("None\n");
}
return 0;
}

B:二分查找(5)

https://vjudge.csgrandeur.cn/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-T1555

二分模板题

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int main()
{
int n,m;
scanf("%d%d",&n,&m);//为什么要注释??
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
while(m--)
{
int x;
scanf("%d",&x);
if(x<a[0])
{
printf("-1\n");
continue;}if(x>=a[n-1]){printf("%d\n",a[n-1]);continue;
}
int l=0,r=n-1;
while(l<r)
{
int mid=(r+l+1)/2;
if(a[mid]<=x)
{
l=mid;}
else
r=mid-1;}cout<<a[l]<<endl;
}
return 0;
}

C(补): 海巴莱堆叠

https://vjudge.csgrandeur.cn/problem/SPOJ-HAYBALE

考察内容:差分,前缀和

思路:通过差分给输入的区间直接加上一包干草堆,再求差分数数组的前缀和,排序,因为n是奇数,直接取中位数即可。

反思:看到这么长的英文题就怕,直接放弃了,太长了,看的我发慌,希望改掉这个毛病。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000005;
int w[N],a[N];
int main()
{int n,k,x,y;
scanf("%d%d",&n,&k);
while(k--)
{
scanf("%d%d",&x,&y);
w[x]++;
w[y+1]--;
}
for(int i=1;i<=n;++i)
a[i]=a[i-1]+w[i];
sort(a+1,a+n+1);
printf("%d",a[n/2+1]);
return 0;
}

D:最大子阵列

https://vjudge.csgrandeur.cn/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-21

考察内容:双指针,数据较少,暴力也行。

思路:暴力,定义一个指针j往下移,对每个值加上于上一个值对比,如果大于则替换。直到遍历完所有数就输出最大的值。

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int main()
{
int n;
scanf("%d",&n);
int sum1=0,sum=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sum=a[0];
for(int i=0;i<n;i++)
{
sum1=0;
for(int j=i;j<n;j++)
{
sum1+=a[j];
if(sum1>sum)
sum=sum1;}
}
printf("%d\n",sum);
return 0;
}

E:激光炸弹

https://vjudge.csgrandeur.cn/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-T2431

考察内容:二维数组的前缀和

思路:定义一个二维数组a,对于输入的x,y每次于R比较用来确定正方形的边界,二维前缀和运算,枚举边长为R的正方形右下角坐标(i,j),求其在正方形内所有价值之和,再更新答案。

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N][N];
int main()
{
int N,R;
scanf("%d%d",&N,&R);
int n=R,m=R;
while(N--)
{
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
x++,y++;
n=max(n,x);
m=max(m,y);
a[x][y]+=v;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
int sum=0;
for(int i=R;i<=n;i++)
{
for(int j=R;j<=m;j++)
{
sum=max(sum,a[i][j]-a[i-R][j]-a[i][j-R]+a[i-R][j-R]);
}
}
printf("%d\n",sum);
return 0;
}

F(补):Hate "A"

https://vjudge.csgrandeur.cn/problem/CodeForces-1146B

思路:网上看的,遍历str字符串,将其分为两个字符串,一个是不加a的字符串suf,另外一个是加了字符串的pre,边加边判断其总长度是不是等于原串长度,直到循环结束的时候如果没有得出结果就输出":("。

#include<bits/stdc++.h>
using namespace std;
int main(){
string str,pre,suf;
cin >> str;
for(auto c : str){
pre += c;
if(c != 'a') suf += c;
if(pre.size() + suf.size() == str.size() && pre + suf == str){
cout << pre << endl;
return 0;
}
} 
cout << ":(" << endl;
return 0;
}

I(补):非常男女

https://vjudge.csgrandeur.cn/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-T1853

考察内容:前缀和,双指针。

思路:定义女生为-1,男生为1,定义数组S为per数组的前缀和,只要找到两个位置的前缀和相等，他们之间就是男女相等的连续子序列。我们记录每个前缀和第一次出现的位置，下次出现的时候，减去第一次的位置就是长度。

#include <iostream>
using namespace std;
const int N=1e5+10;
int per[N],s[N];
int main(){int n,i,j,max=0;cin>>n;for(i=1;i<=n;i++){scanf("%d",&per[i]);if(per[i]==0) per[i]=-1;s[i]=s[i-1]+per[i];}for(i=1;i<=n;i++){for(j=0;j<i;j++){if(s[i]==s[j]){if(i-j>max)max=i-j;break;}}}cout<<max;return 0;
}

H(补):铺设道路

https://vjudge.csgrandeur.cn/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-T2050

考察内容:贪心算法

 思路:遍历道路数组：如果前一个块比后一块小，那么计数器加上其差值，因为这样做，第一个坑设置为坑的深度-0，当一个坑比前一个坑深时，需要相对于已经储存的次数的额外操作次数就是其差值.

#include<iostream>
#include<cstdio>
using namespace std;
int n,ans=0,l=0;
int main()
{scanf("%d",&n);for(int a=1;a<=n;a++){int p;scanf("%d",&p);//当前深度if(p>l)//如果当前深度大于前一段深度{ans=ans+p-l;//总步数加当前深度减前一段深度}l=p;//前一段深度；}printf("%d\n",ans);
}