我训练赛中做出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);
}