XP02_2暑假集训营练习答案
2025-07-23 19:15:37
发布于：浙江
156阅读
0回复
0点赞
7/23
1.T42443.查找x
#include<bits/stdc++.h>
using namespace std;
int n,f=1,apple[114514];
int main(){
cin>>n;
int l=1,r=n;
for(int i=1;i<=n;i++) cin>>apple[i];
int x;
cin>>x;
while(l<=r){
int mid=(l+r)/2;
if(apple[mid]>x){
r=mid-1;
}else if(apple[mid]<x){
l=mid+1;
}else if(apple[mid]==x) {
cout<<mid;
f=0;
break;
}
}
if(f==1) cout<<"-1";
return 0;
}
2.T41335.查找第一个大于等于目标的数
方法1：
#include<bits/stdc++.h>
using namespace std;
int n,q,apple[214514];
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>apple[i];
while(q--){
int x,ans=n+1;
cin>>x;
int l=1,r=n;
while(l<=r){
int mid=(l+r)/2;
if(apple[mid]>=x){
ans=mid;
r=mid-1;
}else if(apple[mid]<x){
l=mid+1;
}
}
cout<<ans<<endl;
}
return 0;
}
方法2：
#include<bits/stdc++.h>
using namespace std;
int a,b,apple[214514];
int main(){
cin>>a>>b;
for(int i=1;i<=a;i++) cin>>apple[i];
while(b--){
int x;
cin>>x;
cout<<lower_bound(apple+1,apple+a+1,x)-apple<<endl;
}
return 0;
}
T41379.查找第一个大于目标的数
方法1：
#include<bits/stdc++.h>
using namespace std;
int a[200010],s[200010];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=a[i];
}
for(int i=1;i<=m;i++){
int w,ans=0,l=1,r=n;
cin>>w;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]>w){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
if(ans==0) cout<<n+1<<endl;
else cout<<ans<<endl;
}
return 0;
}
方法2：
#include<bits/stdc++.h>
using namespace std;
int a,b,apple[214514];
int main(){
cin>>a>>b;
for(int i=1;i<=a;i++) cin>>apple[i];
while(b--){
int x;
cin>>x;
cout<<upper_bound(apple+1,apple+a+1,x)-apple<<endl;
}
return 0;
}
T43047.出现次数:
方法1：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000010],s[1000010];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[a[i]]+=1;
}
cin>>m;
for(int i=1;i<=m;i++){
int p;
cin>>p;
cout<<s[p]<<endl;
}
return 0;
}
方法2：
#include<bits/stdc++.h>
using namespace std;
int a,b,apple[214514];
int main(){
cin>>a;
for(int i=1;i<=a;i++) cin>>apple[i];
cin>>b;
sort(apple+1,apple+a+1);
while(b--){
int x,low=0,upp=0;
cin>>x;
low=lower_bound(apple+1,apple+a+1,x)-apple;
upp=upper_bound(apple+1,apple+a+1,x)-apple;
cout<<upp-low<<endl;
}
return 0;
}
T44263.保龄球
#include<bits/stdc++.h>
using namespace std;
int a[114514];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int q;
cin>>q;
while(q--){
int m;
cin>>m;
int t=lower_bound(a+1,a+n+1,m)-a;
if(a[t]==m) cout<<t<<endl;
else cout<<0<<endl;
}
return 0;
}
方法2：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int cnt,id;
}apple[100010];
bool cmp(Node x,Node y){
return x.cnt<y.cnt;
}
int main(){
int n,q;
cin>>n;
for(int i=1;i<=n;i++){
cin>>apple[i].cnt;
apple[i].id=i;
}
sort(apple+1,apple+n+1,cmp);
cin>>q;
while(q--){
int l=1,r=n,x,flag=0;
cin>>x;
while(l<=r){
int mid=(l+r)/2;
if(apple[mid].cnt==x){
cout<<apple[mid].id<<endl;
flag=1;
break;
}else if(apple[mid].cnt<x){
l=mid+1;
}else if(apple[mid].cnt>x){
r=mid-1;
}
}
if(flag==0) cout<<0<<endl;
}
return 0;
}
T44266.和为 0 的 4 个值
#include<bits/stdc++.h>
using namespace std;
int n,cnt=0,ans=0,a[1010],b[1010],c[1010],d[1010],apple[1000010];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
apple[++cnt]=a[i]+b[j];
}
}
sort(apple+1,apple+cnt+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int low=0,upp=0;
int pear=-c[i]-d[j];
low=lower_bound(apple+1,apple+cnt+1,pear)-apple;
upp=upper_bound(apple+1,apple+cnt+1,pear)-apple;
ans+=upp-low;
}
}
cout<<ans;
return 0;
}
T58817.**************************************************
送分题
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"@_@";
return 0;
}
有帮助，赞一个