XP03A-3练习题答案
2025-08-02 15:22:13
发布于：浙江
95阅读
0回复
0点赞
T1：查找第一个大于等于目标的数
#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;
}
T2:保护环境人人有责
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0,apple[1010101];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>apple[i];
sort(apple+1,apple+n+1);
int l=0,r=apple[n];
while(l<=r){
int mid=(l+r)/2;
long long sum=0;
for(int i=1;i<=n;i++){
if(apple[i]>mid) sum+=apple[i]-mid;
}
if(sum>=m){ ans=mid;l=mid+1;}
else r=mid-1;
}
cout<<ans;
return 0;
}
T3：小蚂蚁吃米
#include<bits/stdc++.h>
using namespace std;
int a[100010];
long long s[100010];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
int w;
cin>>w;
for(int i=1;i<=w;i++){
int x,y;
cin>>x>>y;
long long ant=0;
ant+=s[y]-s[x]+a[x];
cout<<ant<<endl;
}
return 0;
}
T4:差分
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100010],s[100010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=a[i]-a[i-1];
}
for(int i=1;i<=m;i++){
int x,y,k;
cin>>x>>y>>k;
s[x]+=k;
s[y+1]-=k;
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+s[i];
cout<<a[i]<<" ";
}
return 0;
}
T5:撤硕管理员
#include<bits/stdc++.h>
using namespace std;
int n,a[20],cnt;
bool vis[20];
bool prime(int n){
if(n<=1)return 0;
for(int i=2;i<n;i++){
if(n%i==0)return 0;
}
return 1;
}
void dfs(int x){
if(x>n){
int sum=0;
for(int i=1;i<=n;i++){
if(vis[i])sum+=a[i];
}
if(prime(sum))cnt++;
return ;
}
vis[x]=1;
dfs(x+1);
vis[x]=0;
dfs(x+1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs(1);
cout<<cnt;
}
T6:连接组件数
#include <bits/stdc++.h>
using namespace std;
bool c(bool h[],int n){
for(int i = 1;i <= n;i++){
if(!h[i]){
return false;
}
}
return true;
}
int main(){
int n,m,u,v,r = 0;
cin>>n>>m;
vector <vector <int> > G(n+1);
for(int i = 1;i <= m;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
bool h[n+1] = {};
queue <int> q;
while(!c(h,n)){
if(q.empty()){
r++;
for(int i = 1;i <= n;i++){
if(!h[i]){
q.push(i);
h[i] = true;
break;
}
}
}
int k = q.front();
q.pop();
h[k] = true;
for(int i = 0;i < G[k].size();i++){
if(!h[G[k][i]]){
q.push(G[k][i]);
h[G[k][i]] = true;
}
}
}
cout<<r<<endl;
return 0;
}
T7：充满希望的骑士与棋盘
#include<bits/stdc++.h>
using namespace std;
int n, m, x, y;
int dx[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
int dy[8] = {2, 2, 1, -1, -2, -2, -1, 1};
int dp[410][410];
struct node{
int x, y;
};
bool check(int x, int y){
return x > 0 && x <= n && y > 0 && y <= m;
}
void bfs(int x, int y){
queue<node> q;
q.push({x, y});
while(q.size()){
node r = q.front();
q.pop();
for(int i = 0; i < 8; i++){
int nx = r.x + dx[i], ny = r.y + dy[i];
if(check(nx, ny) && dp[nx][ny] == -1){
dp[nx][ny] = dp[r.x][r.y] + 1;
q.push({nx, ny});
}
}
}
}
int main() {
cin>>n>>m>>x>>y;
memset(dp,-1,sizeof(dp));
dp[x][y] = 0;
bfs(x, y);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}
return 0;
}
T8:逃离迷宫
#include<bits/stdc++.h>
using namespace std;
int n,m,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char mp[50][50];
bool flag=0,vis[50][50];
bool apple(int x,int y){
if(mp[x][y]=='.'&&x>=1&&x<=n&&y<=m&&vis[x][y]==false) return true;
else return false;
}
void pear(int x,int y){
if(x==n&&y==m){flag=1;return ;}
vis[x][y]=true;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(apple(nx,ny)==true) pear(nx,ny);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
pear(1,1);
if(flag==1) cout<<"YES";
else cout<<"NO";
return 0;
}
T9:组合的输出
#include <bits/stdc++.h>
using namespace std;
int F[100],Ans[100];
void apple(int n,int k,int c){
if(k==c+1){
for(int i=1;i<=c;i++) cout << setw(3) << Ans[i];
cout<<endl;
return ;
}
for(int i=Ans[k-1]+1;i<=n;i++){
if(F[i]==0){
Ans[k]=i;
F[i]=1;
apple(n,k+1,c);
F[i]=0;
}
}
}
int main(){
int n,r;
cin>>n>>r;
apple(n,1,r);
return 0;
}
T10:细胞
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
char mp[1005][1005];
int vis[1005][1005];
int dir[4][2]={-1,0,0,-1,1,0,0,1};
bool check(int x,int y){
return x<=n&&x>=1&&y<=m&&y>=1;
}
void dfs(int x,int y){
for(int i=0;i<4;i++){
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(check(nx,ny)&&mp[nx][ny]!='0'&&!vis[nx][ny]){
vis[nx][ny]=1;
dfs(nx,ny);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]!='0'&&!vis[i][j]){
cnt++;
vis[i][j]=1;
dfs(i,j);
}
}
}
cout<<cnt;
return 0;
}
T11:逃离迷宫2
#include<bits/stdc++.h>
using namespace std;
int n,m,step=0,ans=110,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char mp[50][50];
bool flag=0,vis[50][50];
bool apple(int x,int y){
if(mp[x][y]=='.'&&x>=1&&x<=n&&y<=m&&vis[x][y]==false) return true;
else return false;
}
void pear(int x,int y,int step){
if(x==n&&y==m){
ans=min(ans,step);
return ;
}
vis[x][y]=true;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(apple(nx,ny)==true){
pear(nx,ny,step+1);
vis[nx][ny]=false;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
pear(1,1,0);
if(ans==110) cout<<"-1";
else cout<<ans;
return 0;
}
T12:神庙迷宫2
#include<bits/stdc++.h>
using namespace std;
int n,m,step=0,ans=110,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char mp[50][50];
bool flag=0,vis[50][50];
bool apple(int x,int y){
if(mp[x][y]=='.'&&x>=1&&x<=n&&y<=m&&vis[x][y]==false) return true;
else return false;
}
void pear(int x,int y,int step){
if(x==n&&y==m){
ans=min(ans,step);
return ;
}
vis[x][y]=true;
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(apple(nx,ny)==true){
pear(nx,ny,step+1);
vis[nx][ny]=false;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
pear(1,1,0);
if(ans==110) cout<<"-1";
else cout<<ans;
return 0;
}
T13:迷路的小猫
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,k;
int a[N];
void bfs(int x){
queue<int> Q;
Q.push(x);
a[x] = 0;
while(!Q.empty()){
int r = Q.front();
Q.pop();
if(r == k){
cout<<a[k];
return ;
}else{
if(a[r-1]==0 && r>=1){
a[r-1] = a[r] + 1;
Q.push(r-1);
} if(a[r+1] == 0 && (r+1)<=100000){
a[r+1] = a[r] + 1;
Q.push(r+1);
} if(a[2*r]==0 && 2*r<=100000){
a[2*r] = a[r]+1;
Q.push(2*r);
}
}
}
}
int main(){
cin>>n>>k;
bfs(n);
return 0;
}
谢谢。
有帮助，赞一个