杭州监狱8月第一期XP03A-Day01
2025-08-02 18:56:03
发布于：浙江
11阅读
0回复
0点赞
今日内容：基础算法（XP02）复习
重点：时间复杂度(O)、二分查找、二分答案、前缀和、差分、深度优先搜索(DFS)、广度优先搜索(BFS)动态规划4了
提一嘴：这期杭州XP03基地换成酒店了
两人一间，房间好，生态好，讲师好，饭菜更好，比前面XP02的研学中心好太多了！
一、二分查找相关习题
#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;
}
题目参照T42072.迷路的小猫
—————————————————————————————————————
上述为杭州监狱今日习题
咱就说XP02的时候主播懒得发
我XP02的讲尸是唐老师和顾老师，顾老师是挑战赛出题人，江湖人称MoonMapple,即中午枫叶，简称午枫，不然你以为挑战赛的主人公怎么全是小午和小枫呢
忘川秋库因此改了会儿名——午枫拿五分。现在忘川秋库和滚蛋吧C++全在我们XP03A-3班，可谓大佬集结。
这句话是唐老师代码出错时，我给他找茬的时候他说的
有帮助，赞一个