2019年北京邮电大学机试题目
趁着现在还记得赶快写下来，个人回忆版
计算机学院机试题目：
第一题：
题目描述：
输入32位的二进制01串，输出这个数+1和+3后的32位二进制串
输入描述：
先输入T，表示输入的组数
然后输入T行二进制串
输出描述：
输出+1和+3后的二进制串
输入样例：
2
00000000000000000000000000000000
00000000000000000000000000000001
输出样例：
00000000000000000000000000000001
00000000000000000000000000000011
00000000000000000000000000000010
00000000000000000000000000000100
代码：
#include<bits/stdc++.h>
using namespace std;
/*
2
00000000000000000000000000000000
00000000000000000000000000000001
*/
int main()
{
int T;
cin>>T;
while(T--)
{
string str;
cin>>str;
int idx=str.size()-1;//从低位开始
while(str[idx]=='1')
{
str[idx--]='0';//是1，变0，进1
}
str[idx]='1';//是0，加1
cout<<str<<endl;
idx=str.size()-1;
while(str[idx]=='1')
{
str[idx--]='0';
}
str[idx]='1';
idx=str.size()-1;
while(str[idx]=='1')
{
str[idx--]='0';
}
str[idx]='1';
cout<<str<<endl;
}
return 0;
}
第二题：
题目描述：
大概意思就是根据输入父节点的两个子节点，根据输入构建一棵树，然后输入两个节点，寻找两个节点之间的距离
距离定义：
输入描述：
先输入T，表示输入的组数
再输入n,m，n表示父节点个数(n>=1),其中1号节点默认为根节点，m表示查询的组数
输出描述：
每组查询的两个点之间的距离
输入样例（具体样例我忘记了）：
1
5 2
2 3
4 5
6 -1
-1 -1
7 -1
6 7
2 3
输出样例：
5
2
根据输入构建的树：
#include<bits/stdc++.h>
using namespace std;
int father[505];//父节点
int len[505];//当前深度
int dis;//距离
void findRoot(int a,int b)
{
if(a==b)
{
return ;
}
dis++;
if(len[a]>=len[b])
{
findRoot(father[a],b);
}
else if(len[a]<len[b])
{
findRoot(a,father[b]);
}
return ;
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(father,0,sizeof(father));
memset(len,0,sizeof(len));
father[1]=-1;//根节点,初始就存在
len[1]=1;//根节点深度初始为1
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
//若输入为-1表示子节点不存在
if(a!=-1)
{
father[a]=i;
len[a]=len[i]+1;
}
if(b!=-1)
{
father[b]=i;
len[b]=len[i]+1;
}
}
for(int i=0;i<k;i++)
{
int a,b;
cin>>a>>b;//查询的两个节点
dis=0;
findRoot(a,b);
cout<<dis<<endl;
}
}
return 0;
}
第三题：
输入描述（这题很长，题目我真记不住）：
有n（n<=50）个城市，保证每个城市与其他城市之间必然有连接，但是两个城市之间会存在多条道路（即有重边，这点考试开始没说，之后发公告才知道，我想基本3A的原因在此），输入道路连接的两个城市号及道路长度。同时在夜晚，某些道路会封路。请输出在白天和夜晚从城市1到城市n之间的最短路径。
输入描述：
先输入T，表示有T组数据
再输入n，m，k，n表示有n个城市，表示总共有m条边，k表示在夜晚有k条路封路
接下来n行，输入n条边的两个端点及长度
接下来k行，输入夜晚要封第几条路
输出描述：
输出白天和夜晚从1号城市到n号城市的最短距离
输入样例：
1
4 5 1
1 2 1
2 3 2
3 4 3
1 3 1
1 4 7
4
输出样例：
4
6
解释说明：
#include<bits/stdc++.h>
using namespace std;
/*
1
4 5 1
1 2 1
2 3 2
3 4 3
1 3 1
1 4 7
4
*/
const int maxn=100000;//表示不可达
int t[55][55];
struct E{
int a,b;//道路的两个端点
int cost;//道路的长度
}Edge[505];
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m,k;
int res1,res2;//存储两次结果
cin>>n>>m>>k;
//初始化所有城市不可达
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
t[i][j]=maxn;
}
}
//输入边
for(int i=1;i<=m;i++)
{
int a,b,cost;
cin>>a>>b>>cost;
Edge[i].a=a;
Edge[i].b=b;
Edge[i].cost=cost;
}
//将权值存入邻接矩阵
for(int i=1;i<=m;i++)
{
int a=Edge[i].a;
int b=Edge[i].b;
int cost=Edge[i].cost;
//因为有重边，所以要选择最小的那条边放入
if(t[a][b]>cost)
{
t[a][b]=cost;
t[b][a]=cost;
}
}
//Floyed算法
for(int l=1;l<=n;l++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(t[i][l]+t[l][j]<t[i][j])
{
t[i][j]=t[i][l]+t[l][j];
}
}
}
}
res1=t[1][n];
//第二次初始化所有城市不可达
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
t[i][j]=maxn;
}
}
//输入夜晚要封路的边
for(int i=0;i<k;i++)
{
int idx;//要封第idx条边
cin>>idx;
Edge[idx].cost=maxn;
}
//将权值存入邻接矩阵
for(int i=1;i<=m;i++)
{
int a=Edge[i].a;
int b=Edge[i].b;
int cost=Edge[i].cost;
//因为有重边，所以要选择最小的那条边放入
if(t[a][b]>cost)
{
t[a][b]=cost;
t[b][a]=cost;
}
}
//Floyed算法
for(int l=1;l<=n;l++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(t[i][l]+t[l][j]<t[i][j])
{
t[i][j]=t[i][l]+t[l][j];
}
}
}
}
res2=t[1][n];
cout<<res1<<endl;
cout<<res2<<endl;
}
return 0;
}
第四题：
题目描述（具体太长，只说大意，我也没A出来，额，发现我好像理解错题目意思了，大家别看我写的这题了，有点错误）：
给出一张从原图片中沿横纵向剪切后的图片，判断原图片中n*n（n>=1）矩阵的大小
（原图片肯定存在该n*n的矩阵，且唯一）
输入描述：
先输入T，表示输入的组数
再输入n，m，表示矩阵的行列
再输入该剪切后的图片，·表示空白，#表示图片中矩阵的内容
输出描述：
输出原图片中最小n*n矩阵的大小，即n的值，如果不存在则输出-1
举例说明吧
如果原图片是这样：
......###..
......###..
......###..
...........
...........
剪切后的图片可能是：
1）不变
......###..
......###..
......###..
...........
...........
2）
##..
##..
##..
....
....
所以一个原图片可能对应很多剪切后的图片
样例1输入：
##..
##..
##..
....
....
样例1输出：
2
说明：该剪切后的图片中有