欢迎来到本文 个人简介：陈童学哦，目前学习C/C++、算法、Python、Java等方向，一个正在慢慢前行的普通人。 系列专栏：陈童学的日记 其他专栏：C++STL，感兴趣的小伙伴可以看看。 希望各位→点赞 + 收藏⭐️ + 留言 ⛱️学习应使你快乐！望与诸君共勉！
Day4集训
A - 医院设置解题思路示例代码
B - Destroyer解题思路示例代码
C - 单源最短路径（弱化版）解题思路示例代码
D - 某最短路解题思路示例代码
E - Sasha and Array Coloring解题思路示例代码
总结
A - 医院设置
来源：洛谷P1364 医院设置 算法标签：动态规划,dp、树形数据结构、广度优先搜索,BFS、最短路
解题思路
这题是一道最短路问题，先用邻接矩阵建一棵树，然后用Floyd（弗洛伊德）算法求任意两点间的最短路，然后再遍历所有节点看看在哪个节点距离和最小
示例代码
#include
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][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=sum; } cout< } B - Destroyer 来源：Codeforces A. Destroyer 解题思路 统计每个数出现的次数，只需满足a[i]<=a[i-1]即可 示例代码 #include 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 - 单源最短路径（弱化版） 来源：洛谷P3371 【模板】单源最短路径（弱化版） 算法标签：图论、最短路、O2优化 解题思路 这题的数据用邻接矩阵的话好像过不了，我不会做（手动流泪），我看有大佬们有用Floyd优化的、Dijkstra+堆优化、SPFA优化等，我这里参考了一位用链式向前星储存图+Dijkstra的大佬的代码。真难啊家人们。 示例代码 #include 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=ans[i]; position=i; } } } for(int i=1;i<=m;i++) cout< } D - 某最短路 来源：洛谷B3647 【模板】Floyd 算法 算法标签：最短路 解题思路 要求任意两点之间的距离，数据也不是很大，这题用Floyd跑一遍就OK了 示例代码 #include 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< cout< } } E - Sasha and Array Coloring 来源：CodeforcesA. Sasha and Array Coloring 解题思路 这题模拟一下，要得到最大值，采用贪心策略，先对数组进行排序，然后每次用末尾数减去首位数，全部相加即可求解 示例代码 #include 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 cin>>a[i]; sort(a,a+n); int i=0,j=n-1; while(i { sum+=a[j]-a[i]; i++; j--; } cout< } } 总结 Day4的题主要考察最短路径、图论问题，这类题较难。 算法：贪心、Floyd、Dijkstra、SPFA、DFS、BFS、dp 感悟：图论最短路的题比较难，有时难得我头炸裂（哭脸） 总结：对于求最短路的各类算法还不是太熟练，还需多加练习加以掌握 推荐阅读
您阅读本篇文章共花了：
发表评论