A - 医院设置
来源：洛谷P1364 医院设置
算法标签：动态规划,dp、树形数据结构、广度优先搜索,BFS、最短路
解题思路
这题是一道最短路问题，先用邻接矩阵建一棵树，然后用Floyd（弗洛伊德）算法求任意两点间的最短路，然后再遍历所有节点看看在哪个节点距离和最小
示例代码
#include<bits/stdc++.h> using namespace std; int a[105],g[105][105]; int main() { int n,l,r,minn,sum; cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) g[i][j]=0x3f3f3f3f; } for(int i=1;i<=n;i++) { g[i][i]=0; cin>>a[i]>>l>>r; if(l>0) g[i][l]=g[l][i]=1; if(r>0) g[i][r]=g[r][i]=1; } //Floyd求最短路 for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { if(i!=k) { for(int j=1;j<=n;j++) { if(i!=j&&k!=j&&g[i][k]+g[k][j]<g[i][j]) g[i][j]=g[i][k]+g[k][j]; } } } } minn=0x7fffffff; for(int i=1;i<=n;i++) { sum=0; for(int j=1;j<=n;j++) sum+=g[i][j]*a[j]; if(sum<minn) minn=sum; } cout<<minn; }
B - Destroyer
解题思路
统计每个数出现的次数，只需满足a[i]<=a[i-1]即可
示例代码
#include <bits/stdc++.h> using namespace std; void solve() { int n,num; cin>>n; int a[105]={0}; //memset(a,0,sizeof a); for(int i = 1 ; i <=n ; i++) { cin>>num; a[num]++; } int judge = 1; for(int i=1;i<105;i++) { if(a[i] > a[i-1]) { judge = 0; break; } } if(judge) cout<<"YES\n"; else cout<<"NO\n"; } int main() { int t; cin>>t; while(t--) { solve(); } return 0; }
C - 单源最短路径（弱化版）
算法标签：图论、最短路、O2优化
解题思路
这题的数据用邻接矩阵的话好像过不了，我不会做（手动流泪），我看有大佬们有用Floyd优化的、Dijkstra+堆优化、SPFA优化等，我这里参考了一位用链式向前星储存图+Dijkstra的大佬的代码。真难啊家人们。
示例代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1000010; int head[N],cnt; ll ans[N]; bool visit[N]; int n,m,s; struct node { int to; int nextt; int wei; }edge[N]; void addedge(int x,int y,int z) { edge[++cnt].to=y; edge[cnt].wei=z; edge[cnt].nextt=head[x]; head[x]=cnt; } int main() { cin>>m>>n>>s; for(int i=1;i<=n;i++) ans[i]=2147483647; ans[s]=0; int a,b,c; for(int i=1;i<=n;i++) { cin>>a>>b>>c; addedge(a,b,c); } int position=s; while(visit[position]==0) { ll minn =2147483647; visit[position]=1; for(int i=head[position];i!=0;i=edge[i].nextt) { if(!visit[edge[i].to]&&ans[edge[i].to]>ans[position]+edge[i].wei) ans[edge[i].to]=ans[position]+edge[i].wei; } for(int i=1;i<=m;i++) { if(ans[i]<minn&&visit[i]==0) { minn=ans[i]; position=i; } } } for(int i=1;i<=m;i++) cout<<ans[i]<<" "; }
D - 某最短路
算法标签：最短路
解题思路
要求任意两点之间的距离，数据也不是很大，这题用Floyd跑一遍就OK了
示例代码
#include<bits/stdc++.h> using namespace std; int n,m; int u,v,w; int g[105][105]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j) g[i][j]=0; else g[i][j]=1e9; } for(int i=1;i<=m;i++) { cin>>u>>v>>w; g[u][v]=g[v][u]=w; } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(g[i][j]>g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j]; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) cout<<g[i][j]<<" "; cout<<endl; } }
E - Sasha and Array Coloring
来源：CodeforcesA. Sasha and Array Coloring
解题思路
这题模拟一下，要得到最大值，采用贪心策略，先对数组进行排序，然后每次用末尾数减去首位数，全部相加即可求解
示例代码
#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; int a[105],sum=0; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); int i=0,j=n-1; while(i<j) { sum+=a[j]-a[i]; i++; j--; } cout<<sum<<endl; } }
总结
Day4的题主要考察最短路径、图论问题，这类题较难。
算法：贪心、Floyd、Dijkstra、SPFA、DFS、BFS、dp
感悟：图论最短路的题比较难，有时难得我头炸裂（哭脸）
总结：对于求最短路的各类算法还不是太熟练，还需多加练习加以掌握
