牛客普及赛2020.10.29

本文主要是介绍牛客普及赛2020.10.29，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2020.10.29 牛客 普及 300pts

A:https://ac.nowcoder.com/acm/contest/7614/A
这道题就不讲思路了。
代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
long long n,cs=1,cf=1;
int ans=1;
int main()
{cin>>n;while(cs<n)cf*=7,cs+=cf,ans++;cout<<ans;return 0;
}

因为是指数级增长，所以运行次数极少，直接判断就行了。

B:https://ac.nowcoder.com/acm/contest/7614/B
这道题其实是一道水题
首先你们可以先想清楚一个问题，两点之间线段最短。
所以不存在我从a镇走到c镇又走到b镇的距离小于a镇到b镇的距离，因此，不是最短路！
然后因为有传送门的存在，所以对于i到i+1点的最短距离除了直接到达还有从每个有传送门的镇到第i个镇的距离，所用时间复杂度O(n*m)，所以我们只用考虑上述两个情况就可AC了。
代码如下

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
int x[5001],y[5001]; 
int zd[5001][5001];//邻接矩阵 从第i点到第j点的距离 
int cs[5001];//传送门 
int w[5001];
int ans;
int jl(int q,int p)
{return abs(x[q]-x[p])+abs(y[q]-y[p]);
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);	 for(int i=1;i<=m;i++)scanf("%d",&cs[i]);for(int i=2;i<=n;i++){w[i]=jl(i-1,i);for(int j=1;j<=m;j++)w[i]=min(jl(i,cs[j]),w[i]);ans+=w[i];}cout<<ans;return 0;
}

C:https://ac.nowcoder.com/acm/contest/7614/C
这道题思想不难，但是，总是会出一些垃圾错误气死人 因为我菜。
首先我先设了一个数组，deep代表在第i层的时候空的位置有多少
然后设一个变量u表示对于当前情况下你可以移到的最深深度。
然后我们来讨论一下u什么时候会被改变，首先u要初始化为1，然后从第二层开始循环，如果他可以往下到下一层，那么我们u++。
什么时候不可以到达下一层呢？
1
. .
xx

2
x.
.x

3
.x
x.
如果遇到这三种情况，那么肯定是到不了下一层的，所以u最低到达当前的i高度。
代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
int n;
string s;
char a[300001][2];
int deep[300001];//这一层有多少个空位 
int u;//下 
int ans;
int main()
{cin>>n;for(int i=n;i>=1;i--){cin>>s;a[i][0]=s[0],a[i][1]=s[1];if(a[i][0]=='.')//球和“x”都是障碍物deep[i]++;if(a[i][1]=='.')deep[i]++;}u=1;for(int i=2;i<=n;i++){if((a[i-1][0]=='x'&&a[i-1][1]=='x')||(a[i-1][0]=='x'&&a[i][1]=='x')||(a[i][0]=='x'&&a[i-1][1]=='x'))u=i;	if(a[i][0]=='o'){while(!deep[u]&&u<i)u++;deep[i]++;//移除，多出一个空位ans+=i-u;deep[u]--;//下来，少了一个空位}if(a[i][1]=='o'){while(!deep[u]&&u<i)//防止u>iu++;deep[i]++;ans+=i-u;deep[u]--;}}cout<<ans;return 0;
}

D:https://ac.nowcoder.com/acm/contest/7614/D
SPFA+特判（处理自环）
没有什么思想难度
代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int head[2001],d[2001],n,m,k,tot=1;
queue<int> q;
struct f{int to,next,w;
} b[10001];
bool book[2001];
void add(int x,int y,int z)
{b[tot].to=y;b[tot].w=z;b[tot].next=head[x];head[x]=tot;tot++;
}
void spfa(int x)
{q.push(x);for (int i=1;i<=n;i++){if (book[i]) d[i]=0,q.push(i);else d[i]=2000*1000+20;}d[x]=0;while (q.size()){int xx=q.front();q.pop();for (int i=head[xx];i;i=b[i].next){if (d[b[i].to]>d[xx]+b[i].w){d[b[i].to]=d[xx]+b[i].w;q.push(b[i].to);}}}
}
int main()
{cin>>n>>m>>k;for (int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;if (x==y) continue;add(x,y,z);add(y,x,z);}for (int i=0;i<k;i++){int x;cin>>x;book[x]=1;}long long s=0;for (int i=1;i<n;i++){if (book[i+1]) continue;spfa(i);s+=d[i+1];}cout<<s<<endl;return 0;
}

这道题是比赛结束后做的，AK梦破碎。。。。无奈

这篇关于牛客普及赛2020.10.29的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---