1.【搜索】Squre
题目：
分析：dfs+剪枝
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N=25; int a[N],n,sum; bool vis[N]; //函数参数：拼到第cnt根，目前这根组合成的长度，遍历起点 bool dfs(int cnt,int len,int x) { //前3根木棒构建完成，因为满足和为边长4倍的条件，无需遍历第4根 if(cnt==3) { return true; } for(int i=x;i<=n;i++) { if(vis[i]) continue; vis[i]=1; if(len+a[i]<sum/4) { if(dfs(cnt,len+a[i],i+1))//往下递归满足条件 return true; } else if(len+a[i]==sum/4)//开始找下一根 { if(dfs(cnt+1,0,1)) return true; } vis[i]=0;//回溯 } return false; } int main() { int t; cin>>t; while(t--) { memset(vis,0,sizeof vis); cin>>n; sum=0; for(int i=1;i<=n;i++) { cin>>a[i]; sum+=a[i]; } sort(a+1,a+1+n,greater<int>());//剪枝：降序排列 //因为所有的边都要被用上，边长为sum/4 if(n<4||sum%4!=0||a[1]>sum/4)//排除不合理情况 { cout<<"no"<<endl; continue; } if(dfs(0,0,1)) cout<<"yes"<<endl; else cout<<"no"<<endl; } return 0; }
2.【搜索】 电路维修
题目：
分析：双端队列bfs
//本质上是个最短路问题 //题目中给出了一些连边，由于可以旋转边，则将旋转后的边看出边权为1，原来的边看作边权为0 //题意可以转化为：从(0,0)点走到(r,c)点所需要的最短距离 //由于边权是0和1，所以可以用双端队列bfs #include <bits/stdc++.h> #define PII pair<int,int> using namespace std; const int N=505; int r,c; char g[N][N];//记录原题 int d[N][N];//记录到每个坐标的最短距离 //点坐标的移动 int yy[4]={-1,1,1,-1};//列 int xx[4]={-1,-1,1,1};//行 //方格坐标的移动,方格坐标都为方格左上角顶点坐标 int y2[4]={-1,0,0,-1}; int x2[4]={-1,-1,0,0}; void bfs() { char op[]="\\/\\/";//从一个节点走四个方向对应的字符 deque<PII> q;//双端队列 q.push_back({0,0}); d[0][0]=0; while(q.size()) { PII t=q.front(); q.pop_front(); int x=t.first,y=t.second; for(int i=0;i<4;i++) { int nx=x+xx[i],ny=y+yy[i]; if(nx<0||nx>r||ny<0||ny>c) continue; int change=0;//判断是否要改变边的方向 int nnx=x+x2[i],nny=y+y2[i]; if(g[nnx][nny]!=op[i]) change=1;//需要改变 //更新最短路 if(d[nx][ny]>d[x][y]+change) { d[nx][ny]=d[x][y]+change; //边权小的加在前面，大的加在后面，保证每次第一个都是最短边权 if(!change) q.push_front({nx,ny}); else q.push_back({nx,ny}); } } } } int main() { int T; cin>>T; while(T--) { memset(d,0x3f,sizeof d); cin>>r>>c; for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { cin>>g[i][j]; } } bfs(); if(d[r][c]==0x3f3f3f3f) cout<<"NO SOLUTION"<<endl; else cout<<d[r][c]<<endl; } return 0; }
3.【搜索】加成序列
题目：
分析：迭代加深
//迭代加深中的dep是长度，因为长度要最小 #include <bits/stdc++.h> using namespace std; const int N=105; int n,seq[N]; bool vis[N]; bool dfs(int now,int dep)//现在要找的位置，深度 { if(now==dep+1) { return seq[now-1]==n; } memset(vis,0,sizeof vis);//每一次加深都要重新遍历 //剪枝：从大到小遍历已经添加进去的数组 for(int i=now-1;i>=1;i--) for(int j=i;j>=1;j--) { int tmp=seq[i]+seq[j]; if(tmp<=n&&!vis[tmp]&&tmp>seq[now-1]) { vis[tmp]=1; seq[now]=tmp; if(dfs(now+1,dep)) return true; } } return false; } int main() { seq[1]=1; while(cin>>n,n) { if(n==1) { cout<<1<<endl; continue; } int dep=2; while(!dfs(2,dep)) { dep++; } for(int i=1;i<=dep;i++) { cout<<seq[i]<<" "; } cout<<endl; } return 0; }
4.【搜索】送礼物
题目：
分析：双向dfs
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=50; int n,num;//num记录的是前半部分得到的不同的重量个数 ll w,g[N],half[1<<25],ans=0;//half用来存储前半部分得到的重量 //搜前半部分 void dfs1(int cnt,ll sum,int dep) {//目前选的礼物，目前的重量，物品数限制 if(cnt==dep) { half[num++]=sum; return; } if(sum+g[cnt]<=w) dfs1(cnt+1,sum+g[cnt],dep);//选 dfs1(cnt+1,sum,dep);//不选 } //搜后半部分 void dfs2(int cnt,ll sum,int dep) { if(cnt>=dep) { int l=0,r=num-1; while(l<r) { int mid=(l+r+1)/2; if(half[mid]+sum<=w) l=mid; else r=mid-1; } ans=max(ans,half[l]+sum); return; } if(sum+g[cnt]<=w) dfs2(cnt+1,sum+g[cnt],dep); dfs2(cnt+1,sum,dep); } int main() { cin>>w>>n; for(int i=0;i<n;i++) cin>>g[i]; sort(g,g+n,greater()); int dep=n/2; dfs1(0,0,dep); //对前一半结果排序，去重（方便后一半的二分） sort(half,half+num); num=unique(half,half+num)-half; dfs2(dep,0,n); cout<<ans; return 0; }
5.【最短路】装满的油箱
题目：
分析：dijkstra+拆点
//将每一种油量状态拆分成单独的点，统计从起点到终点的最短路径（油钱） #include <bits/stdc++.h> using namespace std; const int N=1005,M=20005,C=105; int n,m,p[N]; int h[N],e[M],ne[M],idx,w[M]; int d[N][C];//到i节点，剩余j油量的最小油钱 bool vis[N][C];//这个状态是否经历过 struct node//结构体记录状态参量：节点，剩余油量，油钱 { int loc,oil,mon; bool operator<(const node &a) const { return mon>a.mon; } }; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int dijkstra(int vol,int st,int ed) { memset(d,0x3f,sizeof d); memset(vis,0,sizeof vis); priority_queue<node> heap; heap.push({st,0,0}); d[st][0]=0; while(heap.size()) { node new_node=heap.top(); heap.pop(); int x=new_node.loc,c=new_node.oil; if(x==ed) return d[x][c];//第一个到达终点的状态油钱最少，作为答案返回 if(vis[x][c]) continue; vis[x][c]=1; //操作1：买油 if(c+1<=vol) { if(d[x][c+1]>d[x][c]+p[x]) { d[x][c+1]=d[x][c]+p[x]; heap.push({x,c+1,d[x][c+1]}); } } //操作2：走路 for(int i=h[x];i!=-1;i=ne[i]) { int y=e[i]; if(c>=w[i]) { if(d[y][c-w[i]]>d[x][c]) { d[y][c-w[i]]=d[x][c]; heap.push({y,c-w[i],d[y][c-w[i]]}); } } } } return -1; } int main() { memset(h,-1,sizeof h); cin>>n>>m; for(int i=0;i<n;i++) cin>>p[i]; while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } int q; cin>>q; while(q--) { int c,s,e; cin>>c>>s>>e; int ans=dijkstra(c,s,e); if(ans==-1) cout<<"impossible"<<endl; else cout<<ans<<endl; } return 0; }
6.【搜索】生日蛋糕
题目：
分析：dfs+剪枝
//dfs+剪枝 #include <bits/stdc++.h> using namespace std; const int N=25; const int INF=0x3f3f3f3f; int n,m; int minv[N],mins[N],R[N],H[N],ans=INF; void dfs(int layer,int v,int s)//当前层数，已选体积，已选面积 { if(layer==0) { if(v==n) ans=min(ans,s); return; } if(v+minv[layer-1]>n) return;//可行性剪枝 if(s+mins[layer-1]>=ans) return;//最优性剪枝 if(s+2*(n-v)/R[layer+1]>=ans) return;//最优性剪枝 for(int r=min(R[layer+1]-1,(int)sqrt(n-v));r>=layer;r--)//剪枝:优化搜索顺序，上下界 for(int h=min(H[layer+1]-1,(n-v)/r/r);h>=layer;h--) { R[layer]=r,H[layer]=h; if(layer==m) dfs(layer-1,v+r*r*h,s+2*r*h+r*r);//第一层的顶面积要覆盖 else dfs(layer-1,v+r*r*h,s+2*r*h); } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { minv[i]=minv[i-1]+i*i*i;//每层体积下界 mins[i]=mins[i-1]+2*i*i;//每层面积下界 } R[m+1]=H[m+1]=INF; dfs(m,0,0); if(ans==INF) cout<<0; else cout<<ans; return 0; }
1. 【搜索】噩梦
题目链接：https://www.acwing.com/problem/content/179/
//男孩一次走3步，所以一次需要扩展3步 //vis标记0为未走过，1为男孩走过，2为女孩走过 #include <bits/stdc++.h> #define PII pair<int,int> using namespace std; const int N=805; int n,m,cnt=0;//cnt记录鬼魂的个数 PII g_st,b_st,ghost[2];//女孩、男孩、鬼魂位置 char g[N][N]; int vis[N][N]; int xx[4]={-1,1,0,0}; int yy[4]={0,0,-1,1}; bool check(int x,int y,int time)//判断这个坐标可不可以走 { if(x<1||x>n||y<1||y>m||g[x][y]==‘X‘) return false; for(int i=0;i<cnt;i++)//判断两个鬼魂会不会到当前位置 { if(abs(ghost[i].first-x)+abs(ghost[i].second-y)<=time*2) return false; } return true; } int bfs() { queue<PII> qg,qb; qg.push(g_st),qb.push(b_st); memset(vis,0,sizeof vis); int time=0; while(qg.size()||qb.size()) { time++; //男孩 for(int i=0;i<3;i++)//扩展三次 { int lb=qb.size(); for(int j=0;j<lb;j++) { PII t=qb.front(); qb.pop(); int x=t.first,y=t.second; if(!check(x,y,time)) continue; for(int k=0;k<4;k++) { int nx=x+xx[k],ny=y+yy[k]; if(check(nx,ny,time)) { if(vis[nx][ny]==2)//女孩走过 return time; if(!vis[nx][ny]) { vis[nx][ny]=1; qb.push({nx,ny}); } } } } } //女孩 int lg=qg.size(); for(int j=0;j<lg;j++) { PII t=qg.front(); qg.pop(); int x=t.first,y=t.second; if(!check(x,y,time)) continue; for(int k=0;k<4;k++) { int nx=x+xx[k],ny=y+yy[k]; if(check(nx,ny,time)) { if(vis[nx][ny]==1)//男孩走过 return time; if(!vis[nx][ny]) { vis[nx][ny]=2; qg.push({nx,ny}); } } } } } return -1; } int main() { int T; cin>>T; while(T--) { cin>>n>>m; cnt=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>g[i][j]; if(g[i][j]==‘G‘) g_st={i,j}; if(g[i][j]==‘M‘) b_st={i,j}; if(g[i][j]==‘Z‘) ghost[cnt++]={i,j}; } cout<<bfs()<<endl; } return 0; }
2.【图论】排序
题目链接：https://www.acwing.com/problem/content/345/
思路：Floyd求解传递闭包问题。给出若干对二元关系，判断能否确定所有元素关系，若能，判断是否存在矛盾关系，输出可以推出全部或找出矛盾关系的最小迭代次数。
#include <bits/stdc++.h> using namespace std; const int N=30; int n,m; bool g[N][N],rel[N][N];//rel[i][j]=1表示i<j，rel[i][j]=0表示ij没有关系 bool vis[N]; int floyd() { memcpy(rel,g,sizeof g); for(int k=1;k<=n;k++)//传递关系 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) rel[i][j]|=rel[i][k]&rel[k][j]; for(int i=1;i<=n;i++) if(rel[i][i]) return 2; for(int i=1;i<=n;i++) for(int j=1;j<=i-1;j++) { if(rel[i][j]==0&&rel[j][i]==0) return 0; } return 1; } int main() { while(cin>>n>>m) { if(n==0&&m==0) break; memset(vis,0,sizeof vis); memset(g,0,sizeof g); int t=0;//记录迭代次数 int flag=0;//0表示无法确定,1表示找全关系，2表示存在矛盾 for(int i=1;i<=m;i++) { char x,y; string s; cin>>s; x=s[0],y=s[2]; g[(int)(x-‘A‘+1)][(int)(y-‘A‘+1)]=1;//建立小于关系的有向边 if(!flag)//当还未找全关系，且没有出现矛盾时继续找 { t=i; flag=floyd(); } } if(flag==1) { printf("Sorted sequence determined after %d relations: ",t); //按照从小到大的顺序输出答案 for(int i=1;i<=n;i++)//i表示循环次数 { for(int j=1;j<=n;j++) { bool flag1=1;//判断j是否满足条件 if(vis[j]) continue; //判断有无未遍历的比j小的，即应该出现在j前，那么j不满足条件 for(int k=1;k<=n;k++) { if(vis[k]) continue; if(rel[k][j]) { flag1=0; break; } } if(flag1) { vis[j]=1; cout<<(char)(j+‘A‘-1); break; } } } printf(".\n"); } else if(flag==2) printf("Inconsistency found after %d relations.\n",t); else printf("Sorted sequence cannot be determined.\n"); } return 0; }
?? 补充知识点：传递闭包
概念：在交际网络中，给定若干元素和若干对二元关系，且关系具有传递性。“通过传递性推导出尽量多的元素之间的关系”的问题称为传递闭包。
解法：建立邻接矩阵rel，其中 rel[i,j]=1 表示i与j有关系，rel[i,j]=0 表示i与j没有关系，rel[i,i] 始终为1。
使用Floyd算法解决传递闭包问题：
bool rel[310][310]; int n,m; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) rel[i][i]=1; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); rel[x][y]=rel[y][x]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) rel[i][j]|=rel[i][k]&rel[k][j];//k用于传递i与j的关系 }
3. 【图论】通信线路
题目链接：https://www.acwing.com/problem/content/342/
思路：1. 双端队列+bfs 2.分层图最短路
//解法一：双端队列+bfs #include <bits/stdc++.h> #define PII pair<int,int> using namespace std; const int N=1005,M=20005; int n,m,k; int idx,h[N],e[M],ne[M],w[M]; int d[N]; bool vis[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool bfs(int mid) { memset(d,0x3f,sizeof d); memset(vis,0,sizeof vis); deque<PII> dq; dq.push_back({0,1}); d[1]=0; while(dq.size()) { PII t=dq.front(); dq.pop_front(); int x=t.second; if(vis[x]) continue; vis[x]=1; for(int i=h[x];i!=-1;i=ne[i]) { int y=e[i]; int flag=w[i]>mid;//边权>预设答案mid的是要免费提供升级服务的，计数为1 if(d[y]>d[x]+flag) { d[y]=d[x]+flag; if(flag) dq.push_back({d[y],y}); else dq.push_front({d[y],y}); } } } return d[n]<=k;//判断需要免费服务的有没有超过限制k } int main() { memset(h,-1,sizeof h); cin>>n>>m>>k; while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); } //二分查找答案 int l=0,r=1000001; while(l<r) { int mid=(l+r)/2; if(bfs(mid)) r=mid; else l=mid+1; } if(r==1000001) cout<<-1; else cout<<l; return 0; }
//解法2：分层图最短路 #include <bits/stdc++.h> #define PII pair<int,int> using namespace std; const int N=1e6+5,M=1e6+5;//分层后数组要开大一些 int n,m,k; int idx,h[N],e[M],ne[M],w[M]; int d[N]; bool vis[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void dijkstra()//跑一个正常的dijkstra { memset(d,0x3f,sizeof d); memset(vis,0,sizeof vis); priority_queue<PII,vector<PII>,greater<PII>> heap; heap.push({0,1}); d[1]=0; while(heap.size()) { PII t=heap.top(); heap.pop(); int x=t.second; if(vis[x]) continue; vis[x]=1; for(int i=h[x];i!=-1;i=ne[i]) { int y=e[i]; if(d[y]>max(d[x],w[i])) { d[y]=max(d[x],w[i]); heap.push({d[y],y}); } } } } int main() { memset(h,-1,sizeof h); cin>>n>>m>>k; while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c),add(b,a,c); for(int i=1;i<=k;i++)//给每一层连边 { //i-1和i层之间连边 add(a+(i-1)*n,b+i*n,0); add(b+(i-1)*n,a+i*n,0); //i层内连边 add(a+i*n,b+i*n,c); add(b+i*n,a+i*n,c); } } dijkstra(); if(d[n+k*n]==0x3f3f3f3f) cout<<-1; else cout<<d[n+k*n]; return 0; }
4.【图论】最优贸易
题目链接：https://www.acwing.com/problem/content/343/
思路：建两个图，进行正向和反向两次SPFA，题目要求找到一条1到n的路径，使路径中先后存在两点p和q，q的权值-p的权值最大。正向以1为起点，记录1到节点x的路径中能经过的权值最小点p（由于不满足贪心，不能用dijkstra），反向以n为起点，记录x到n中权值最大点q，最后遍历所有节点，更新答案。
#include <bits/stdc++.h> using namespace std; const int N=1e5+5,M=1e6+5; int n,m,price[N]; int h[N],rh[N],e[M],ne[M],idx; int dmin[N],dmax[N];//到i节点的最小，最大权值 bool vis[N]; void add(int *h,int a,int b)//建两个图只需要换个表头 { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } //为什么不能用dijkstra呢？ //因为dijkstra基于贪心算法，当某节点弹出堆时，它的最小值已经确定，不会再次被更新 //对于本题，是要求起点到x节点中经过的最小值，此时是最小值并不能保证弹出队列后不会更新为更小值 void spfa(int *d,int st,int *h,bool flag)//记录权值的数组，开始节点，表头，求最小还是最大 { if(flag) memset(d,0x3f,sizeof dmin); memset(vis,0,sizeof vis); queue<int> q; q.push(st); d[st]=price[st]; vis[st]=1; while(q.size()) { int x=q.front(); q.pop(); vis[x]=false; for(int i=h[x];i!=-1;i=ne[i]) { int y=e[i]; if(flag&&d[y]>min(d[x],price[y])||!flag&&d[y]<max(d[x],price[y])) { if(flag) d[y]=min(d[x],price[y]); else d[y]=max(d[x],price[y]); if(!vis[y]) { vis[y]=1; q.push(y); } } } } } int main() { memset(h,-1,sizeof h); memset(rh,-1,sizeof rh); cin>>n>>m; for(int i=1;i<=n;i++) cin>>price[i]; while(m--) { int a,b,c; cin>>a>>b>>c; add(h,a,b),add(rh,b,a);//连正向边和反向边 if(c==2) add(h,b,a),add(rh,a,b); } spfa(dmin,1,h,true);//正向求最小边权 spfa(dmax,n,rh,false);//反向求最大边权 int ans=0; for(int i=1;i<=n;i++) { ans=max(ans,dmax[i]-dmin[i]); } cout<<ans; return 0; }
Bye~