4.17算法考核

其实算法题没有想象中的那么可怕，掌握套路一般难度的题目是不成问题的。
A
题意：一块冰块移到另一冰块上，只能是水平或竖直方向，求最少需要几块才能使得任意两块之间都能移动。
题解：手推几组数据后可以发现，连通的集合个数-1就是答案，判断连通用并查集。

#include<bits/stdc++.h>
using namespace std;
int x[110],y[110],f[110];
int find(int x)
{
return x==f[x]?x:f[x]=find(f[x]);
}
void merge(int x,int y)
{
int xx=find(x),yy=find(y);
if(xx!=yy)f[yy]=xx;
}
int main()
{
int n,i,j,cnt=0;cin>>n;
for(i=1;i<=n;i++)
cin>>x[i]>>y[i],f[i]=i;
for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++)
if(x[i]==x[j]||y[i]==y[j])merge(i,j);
for(i=1;i<=n;i++)
if(f[i]==i)cnt++;
cout<<cnt-1<<endl;
}

C
题意：仓库点到非仓库点的最小距离。
题解：在读入的边中，看这条边的两个端点是否为一个仓库点和一个非仓库点，比较它们的最小距离即可。

#include<bits/stdc++.h>
using namespace std;
struct node
{
int s,e,l;
}edge[100010];
int vis[100010],a[100010];
int main()
{
int n,m,k,i,mmin=1e9+10;cin>>n>>m>>k;
for(i=1;i<=m;i++)
cin>>edge[i].s>>edge[i].e>>edge[i].l;
for(i=1;i<=k;i++)
{
cin>>a[i];
vis[a[i]]=1;
}
for(i=1;i<=m;i++)
{
if(vis[edge[i].s]+vis[edge[i].e]==1)
mmin=min(mmin,edge[i].l);
}
mmin==1e9+10?cout<<-1<<endl:cout<<mmin<<endl;
}

E
题意：有两种路线，一种铁路，一种马路，求两种路线中顶点1到顶点n的最小距离。
题解：判断1到n的现有路线，如果是铁路就走马路，因为走铁路的距离已经知道，再求马路距离比较最小值，同理，如果是马路就走铁路。这题数据不大最优方法为Floyd。

#include<bits/stdc++.h>
using namespace std;
int e[410][410];
int main()
{
int n,m,u,v,i,j,k;cin>>n>>m;
for(i=1;i<=m;i++)
{
cin>>u>>v;
e[u][v]=e[v][u]=1;
}
if(e[1][n])
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
e[i][j]=1-e[i][j];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
{
if(!e[j][i]||!e[i][k])continue;
if(!e[j][k])e[j][k]=e[j][i]+e[i][k];
e[j][k]=min(e[j][k],e[j][i]+e[i][k]);
}
e[1][n]?cout<<e[1][n]<<endl:cout<<-1<<endl;
}

F
题意：多组输入，每组一行，遇‘#’结束输入，求单词个数。
题解：一开始我想着输入的字符串可能有多个空格就根据先读字母再读空格结束的方式存字符串，再用map标记一下，但是莫名地错了。然后换了个思路，空格作为间断点，注意循环结束后还得再判断一次，因为最后一个字符串后面可能没有空格。

#include<bits/stdc++.h>
#include<string.h>
#include<map>
using namespace std;
char a[1010];
int main()
{
while(gets(a)&&a[0]!='#')
{
map<string,int>mp;
int i,l=strlen(a),cnt=0;
string str="";
mp[str]=1;
for(i=0;i<l;i++)
{
if(a[i]==' ')
{
if(!mp[str])cnt++;
mp[str]=1,str="";
}
else str+=a[i];
}
if(!mp[str])cnt++;
cout<<cnt<<endl;
}
}

G - 统计难题
题意：先输入一堆字符串，以空行结束，再输入一堆前缀，问在前一堆字符串中同前缀的有几个。
题解：这题正统点的方法应该用字典树，但是可以取巧，逆序读取字符串，将当前字符赋以‘’，再用map巧妙地标记前缀。还有空行可以通过长度判断。

#include<bits/stdc++.h>
#include<map>
#include<string.h>
using namespace std;
char a[20];
int main()
{
map<string,int>mp;
while(gets(a))
{
int i,l=strlen(a);
if(!l)break;
for(i=l;i>0;i--)
a[i]='',mp[a]++;
}
while(gets(a))
cout<<mp[a]<<endl;
}

最后

以上就是虚幻小丸子为你收集整理的4.17算法考核的全部内容，希望文章能够帮你解决4.17算法考核所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。