杭州监狱8月第一期XP03A-Day01

银色子弹

2025-08-09 15:04:05

发布于：浙江

59阅读

0回复

0点赞

今日内容：基础算法（XP02）复习
重点：时间复杂度(O)、二分查找、二分答案、前缀和、差分、深度优先搜索(DFS)、广度优先搜索(BFS)

一、二分查找相关习题

#include<iostream>
#include<algorithm>
using namespace std;
int a[200005];
int main(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(q--){
        int x;
        cin>>x;
        //lower_bound()：查找a[]第一个≥x数的位置，返回地址
        int ans=lower_bound(a+1,a+n+1,x)-a;
        cout<<ans<<endl;
    }
    return 0;
}

题目参照T41335.查找第一个大于等于目标的数

二、二分答案相关习题

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int a[1000010];

bool check(int mid){//判断是否符合题目条件的函数
    long long cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]>mid){
            cnt+=a[i]-mid;
        }
    }
    return cnt>=m;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);//使数组有序（拥有单调性）
    //二分答案
    int l=0,r=a[n],ans;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){//如果高度足够
            l=mid+1;//更改范围，锯片高度尽量更大
            ans=mid;//记录可能答案
        }else{
            r=mid-1;//更改范围，锯片高度应变小
        }
    }
    cout<<ans;
    return 0;
}

题目参照T43051.保护环境人人有责

三、前缀和相关习题

#include<iostream>
using namespace std;
int a[100010],s[100010];//前缀和数组定义
int main(){
    int n,q;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];//前缀和数组初始化（前和+当前数）
    }
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        //s[r]-s[l-1]即为a[l]~a[r]的和
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}

题目参照T48460.小蚂蚁吃米

四、差分相关习题

#include<iostream>
using namespace std;
int a[100010],d[100010];//定义差分数组，操作硬背
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    //差分数组初始化，为当前项与上一项的差
    for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1];
    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        d[l]+=c,d[r+1]-=c;//差分操作
    }
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+d[i];//a的第i项=前一项加差分当前项
        cout<<a[i]<<' ';
    }
    return 0;
}

题目参照T49397.差分

五、深度优先搜索相关习题

#include<iostream>
using namespace std;
int n,ans=0;
int a[20];
bool vis[20];//判断第i人有没有吃过美食

bool is_prime(int n){//判断费用和是否为质数函数
    if(n<=1) return false;
    for(int i=2;i*i<=n;i++) if(n%i==0) return false;
    return true;
}

void check(){
    int cnt=0;//用cnt求各个和
    for(int i=1;i<=n;i++){
        if(vis[i]) cnt+=a[i];
    }
    if(is_prime(cnt)) ans++;//调用函数，cnt是否为质数
    return;
}

void dfs(int now){//深搜函数
    if(now==n+1){//递归边界，如果所有人都吃完，统计ans
        check();
        return;
    }
    //i要上
    vis[now]=true;//i吃过了，标记为1
    dfs(now+1);
    vis[now]=false;//回溯，求其他答案
    //i不上
    dfs(now+1);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(1);//深搜函数调用
    cout<<ans;
    return 0;
}

题目参照T41325.撤硕管理员
（王老师：一个抽象的老师出了一道抽象的题）

#include<iostream>
#include<vector>
using namespace std;
int n,m,cnt;
vector<int> v[110];//记录顶点
bool vis[110];//记录v[i]是否与其他顶点相连
void dfs(int x){
    vis[x]=true;//标记v[i]相连
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i];//y为v[x]的一个相连顶点
        if(vis[y]==0){//若这个顶点当前无其他相连顶点
            dfs(y);//递归（与L25-L27同理）
        }
    }
}
int main(){
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);//v[x]可与y连接
        v[y].push_back(x);//v[y]可与x连接，注意是无向图
    }
    for(int i=1;i<=n;i++){//遍历v[i]数组
        if(vis[i]==0){//如果v[i]数组当前不与任何顶点相连
            cnt++;//答案（部分数）+1
            dfs(i);//调用深搜函数
        }
    }
    cout<<cnt;
    return 0;
}

题目参照T41351.连接组件数

#include<iostream>
#include<queue>
using namespace std;
int n,m,x,y;
int vis[1005][1005];//起点——{x,y}的步数
int dx[8]={1,1,-1,-1,2,2,-2,-2},
    dy[8]={2,-2,2,-2,1,-1,1,-1};//两个偏移量数组

struct node{
    int x,y;
};

bool check(int x,int y){//判断是否越界函数
    if(x<=0||y<=0||x>n||y>m) return false;
    if(vis[x][y]!=-1) return false;
    return true;
}

int main(){
    cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            vis[i][j]=-1;
        }
    }
    queue<node> q;
    q.push({x,y});//将起点位置入队
    vis[x][y]=0;//到起点的步数
    while(!q.empty()){
        int wx=q.front().x,wy=q.front().y;//取队首坐标
        q.pop();//队首出队
        for(int i=0;i<8;i++){
            int nx=wx+dx[i],ny=wy+dy[i];//马移动后的坐标
            if(check(nx,ny)){//调用判断函数
                q.push({nx,ny});//新坐标入队
                vis[nx][ny]=vis[wx][wy]+1;
                //起点——新坐标的步数比起点——原坐标的步数多1
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d ",vis[i][j]);//打印每个步数
        }
        cout<<endl;
    }
    return 0;
}

题目参照T55137.充满希望的骑士与棋盘

#include<iostream>
using namespace std;
char mp[45][45];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//偏移量数组
bool vis[45][45],f;//f判断是否有一条或多条路径
int n,m;

void dfs(int x,int y){
    //递归边界，如果坐标抵达右下角，说明有路径
    if(x==n&&y==m){
        f=true;
        return;
    }
    //向四个方向移动
    for(int i=0;i<4;i++){
        //新坐标
        int nx=x+dir[i][0],ny=y+dir[i][1];
        //判断是否越界、是否能访问、是否已被访问
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m
           &&mp[nx][ny]=='.'&&!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];
        }
    }
    vis[1][1]=1;//起点被标记已访问
    dfs(1,1);//从坐标（1,1）开始走
    if(f) cout<<"YES";
    else cout<<"NO";
    return 0;
}

题目参照T42061.逃离迷宫

#include<iostream>
#include<iomanip>//控制函数setw()头文件
using namespace std;
int n,m;
bool f[30];//标记数字i是否已被使用
int a[30];//
void dfs(int k){
    //递归边界
	if(k>m){//如果k超出m，输出1项~k项的每个组合
		for(int i=1;i<k;i++){
			cout<<setw(3)<<a[i];//每个数场宽为3
		}
		cout<<endl;
	}
	else{
        //组合范围：(a[k-1]+1)~n
		for(int i=a[k-1]+1;i<=n;i++){
			a[k]=i;
			dfs(k+1);//递归
		}
	}
}
int main(){
 	cin>>n>>m;
 	dfs(1);//从数字1开始排列组合
	return 0;
}

题目参照T42065.组合的输出

六、深度优先搜索相关习题

#include<bits/stdc++.h>
using namespace std;
char mp[1009][1009];
bool vis[1009][1009];
int n,m;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct node{
    int x,y;
}l,r;
void bfs(int x,int y) {
    queue<node> q;
    q.push({x,y});
    vis[x][y]=true;
    while(q.size()){
        r=q.front();
        q.pop();
        for(int i=0;i<4;i++) {
            l.x=r.x+dir[i][0];
            l.y=r.y+dir[i][1];
            if(l.x>=1&&l.x<=n&&l.y>=1&&l.y<=m&&
                !vis[l.x][l.y]&&mp[l.x][l.y]!='0'){
                vis[l.x][l.y]=true;
                q.push(l);
            }
        }
    }
    
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>mp[i]+1;
    }
    int cnt=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(!vis[i][j]&&mp[i][j]!='0') {
                cnt++;
                bfs(i,j);
            }
        }
    }
    cout<<cnt;
    return 0;
}

题目参照T42063.细胞

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
char mp[45][45];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//偏移量数组
bool vis[45][45],flag;//标记数组、变量
int n,m,x,y;
vector<int> v;

void dfs(int x,int y,int step){
    //递归边界
    if(x==n&&y==m){//若走到右下角
        flag=1;//标记有这样一条路径
        v.push_back(step);//向v[]中加入步数
        return;
    }
    //向四个方向走，记录新坐标
    for(int i=0;i<4;i++){
        int nx=x+dir[i][0],ny=y+dir[i][1];
        //判断新坐标是否越界、是否可访问、是否已被访问
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m
           &&mp[nx][ny]=='.'&&!vis[nx][ny]){
            vis[nx][ny]=1;//标记已访问
            dfs(nx,ny,step+1);//递归，需要的步数+1
            vis[nx][ny]=0;//回溯
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    }
    vis[1][1]=1;//标记起点已访问
    dfs(1,1,0);//起点步数为0，坐标为（1,1）
    if(flag==0) cout<<-1;
    else{
        //输出v[]中最小值，即最少步数
        cout<<*min_element(v.begin(),v.end());
    }
    return 0;
}

题目参照T42062.逃离迷宫2

//与上题相似，此题已广搜模版作为演示，不重复相同注释
#include<iostream>
#include<queue>
using namespace std;

const int N=105;
int n,m;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//偏移量数组
char a[105][105];
bool vis[105][105];//标记数组

struct node{
    int x,y,step;
};

void bfs(int x,int y){
    queue<node> q;
    q.push({x,y,0});//队首入队
    vis[x][y]=true;//标记(x,y)已访问
    while(!q.empty()){
        node t=q.front();//取队首
        q.pop();//删队首
        if(t.x==n&&t.y==m){//返回条件
            cout<<t.step;
            return;
        }
        for(int i=0;i<4;i++){
            //新坐标
            int nx=t.x+dir[i][0],ny=t.y+dir[i][1];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&
               !vis[nx][ny]&&a[nx][ny]=='.'){//判断
                q.push({nx,ny,t.step+1});//入队
                vis[nx][ny]=true;//标记
            }
        }
    }
    cout<<-1;//无路径
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    bfs(1,1);//调用
    return 0;
}

题目参照T46845.神庙迷宫2

#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;
}