考试情况
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 100 | 0 | 30 | 100 | 16 | 0 |
考题
考点/易错点
A.P1571 眼红的Medusa：考二分模板掌握度
B.P2249 【深基13.例1】查找：同上⬆️
C.P1678 烦恼的高考志愿：第二难，熟练掌握今天学的lower_bound和对于题目的理解度
D.P1918 保龄球：跟第一题一样，都是昨天讲了的题目，熟练运用板子和结构体排序
E.P1102 A-B 数对：昨天的作业题，考察今天学的lower_bound和upper_bound的掌握度
F.B3799 [NICA #1] 序列：跟第三题一样，但是还要运用之前学的前缀和。
错误题目
B.P2249 【深基13.例1】查找
错误代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int n,m,a[N],b;
int chen_teacher(int x)
{
int l=0,r=n+1,minn=INT_MAX;
a[0]=-1,a[r]=INT_MAX;
while(l+1<r)
{
int mid=(l+r)/2;
if(a[mid]<x)
{
l=mid;
}
else if(a[mid]>x)
{
r=mid;
}
else
{
minn=min(minn,mid);
r=mid;
}
}
if(minn==INT_MAX)
{
return -1;
}
return minn;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&b);
int q=chen_teacher(b);
printf("%d ",q);
}
return 0;
}
错误分析
题目理解错误
本题输入输出量较大，请使用较快的 IO 方式。
把"IO方式"理解成了要用scanf和printf。
scanf -> cin,printf -> cout
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+2;
int n,m,a[N],b;
int chen_teacher(int x)
{
int l=0,r=n+1,minn=INT_MAX;
a[0]=-1,a[r]=INT_MAX;
while(l+1<r)
{
int mid=(l+r)/2;
if(a[mid]<x)
{
l=mid;
}
else if(a[mid]>x)
{
r=mid;
}
else
{
minn=min(minn,mid);
r=mid;
}
}
if(minn==INT_MAX)
{
return -1;
}
return minn;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
cin>>b;
int q=chen_teacher(b);
cout<<q<<' ';
}
return 0;
}
C.P1678 烦恼的高考志愿
错误代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int m,n,a[N],b[N],ans,minn;
int main()
{
scanf("%d %d",&m,&n);
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
minn=INT_MAX;
for(int j=1;j<=m;j++)
{
minn=min(minn,abs(b[i]-a[j]));
}
ans+=minn;
}
printf("%d",ans);
return 0;
}
错误分析
由于当时二分板子写不出来，于是写了个暴力来骗分
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int m,n,a[N],b[N];
long long ans;
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
cin>>a[i];
}
sort(a+1,a+1+m);
for(int i=1;i<=n;i++)
{
cin>>b[i];
int pos=lower_bound(a+1,a+1+m,b[i])-a;
if(pos==m+1)
{
ans+=abs(b[i]-a[m]);
continue;
}
if(pos==1)
{
ans+=abs(b[i]-a[1]);
continue;
}
if(abs(b[i]-a[pos])<abs(b[i]-a[pos-1]))
{
ans+=abs(b[i]-a[pos]);
}
else
{
ans+=abs(b[i]-a[pos-1]);
}
}
cout<<ans;
return 0;
}
E.P1102 A-B 数对
错误代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5*2+2;
int n,c,a[N],ans;
int chen_teacher(int x,int i)
{
int l=0,r=n+1,cnt=0;
a[0]=-1,a[r]=INT_MAX;
while(l+1<r)
{
int mid=(l+r)/2;
if(a[mid]<x)
{
l=mid;
}
else if(a[mid]>x)
{
r=mid;
}
else
{
if(mid!=i)
{
cnt++;
}
if(a[mid-1]==a[mid])
{
r=mid;
}
else
{
l=mid;
}
}
}
return cnt;
}
int main()
{
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
ans+=chen_teacher((a[i]-c),i);
}
cout<<ans<<'\n';
return 0;
}
错误分析
打了一个二分板子，过了样例，但是没有过数据，把问题复杂化了，实际上用upper_bound和lower_bound就可以轻松通过
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+2;
int a[maxn],n,c;
long long ans;
int main()
{
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
int b=a[i]-c;
int geshu=upper_bound(a+1,a+1+n,b)-lower_bound(a+1,a+1+n,b);
ans+=geshu;
}
cout<<ans;
return 0;
}
C.P1678 烦恼的高考志愿
错误代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int m,n,a[N],b[N],ans,minn;
int main()
{
scanf("%d %d",&m,&n);
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
minn=INT_MAX;
for(int j=1;j<=m;j++)
{
minn=min(minn,abs(b[i]-a[j]));
}
ans+=minn;
}
printf("%d",ans);
return 0;
}
错误分析
由于当时二分板子写不出来，于是写了个暴力来骗分
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int m,n,a[N],b[N];
long long ans;
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
cin>>a[i];
}
sort(a+1,a+1+m);
for(int i=1;i<=n;i++)
{
cin>>b[i];
int pos=lower_bound(a+1,a+1+m,b[i])-a;
if(pos==m+1)
{
ans+=abs(b[i]-a[m]);
continue;
}
if(pos==1)
{
ans+=abs(b[i]-a[1]);
continue;
}
if(abs(b[i]-a[pos])<abs(b[i]-a[pos-1]))
{
ans+=abs(b[i]-a[pos]);
}
else
{
ans+=abs(b[i]-a[pos-1]);
}
}
cout<<ans;
return 0;
}
F.B3799 [NICA #1] 序列
错误代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+2;
int main()
{
cout<<"22\n31\n45";
return 0;
}
错误分析
当时写不出来，于是直接输出样例了。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+2;
long long a[maxn],sum[maxn],n,m,ans,op,k;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
}
while(m--)
{
cin>>op;
if(op==1)
{
cin>>k;
ans+=k;
}
else if(op==2)
{
long long pos=lower_bound(a+1,a+1+n,-ans)-a,l=pos,r=n;
cout<<(sum[r]-sum[l-1])+(r-l+1)*ans<<'\n';
}
}
return 0;
}
总结
对于运用upper_bound和lower_bound的方式还不熟，还是要把二分板子还要再背一下。