19计算机院机试真题

计算机院的机试题真难，没有4A的，第四题的题目看了一下，好像是矩阵的，题目记不清了，如果你考计算机院也不建议你准备第四题。18年的第四题是动态规划，也是0A。今年网研的机试题比较简单，有不少4A的。

Problem A 二进制

题目描述
32位二进制数 X ，对其进行X+1,X+3操作，并输出。注意不能忽略前导0。
输入
第一行，一个整数 T ,代表测试数据组数。接着 T 行，输入32为二进制数输出对每组测试数据。
输出
两行，第一行为X+1,第二行为X+3.
测试样例
输入
2
00000000000000000000000000000000
00000000000000000000000000000001
输出
00000000000000000000000000000001
00000000000000000000000000000011
00000000000000000000000000000010
00000000000000000000000000000100
分析
这个比较容易，我就直接用的数组，模拟手算。还可以有更多方式，可以参考我的另一篇博客
c/c++进制转换方法汇总（含全部代码）
代码

#include<bits/stdc++.h>
using namespace std;
int ans[32];
string s1="00000000000000000000000000000001";
string s2="00000000000000000000000000000011";//输出结果函数 
void Print()
{for(int i=0;i<32;i++){cout<<ans[i];}cout<<endl;
}//二进制加法函数
void Add(string a, string b)
{int carry = 0;//进位memset(ans,0,sizeof(ans));for(int i = 31;i>=0;i--){ans[i] = a[i]-'0'+b[i]-'0'+carry;if(ans[i]>1)//需要进位 {ans[i] = 0;carry = 1;}	elsecarry = 0;}Print();
} //主函数 
int main()
{int T;string s;cin>>T;while(T--){cin>>s;Add(s,s1);	Add(s,s2);}return 0;	
}

结果截图

Problem B 二叉树

题目描述
对二叉树，计算任意两个结点的最短路径长度。
输入
第一行输入测试数据组数 T
第二行输入 n , m 。 n 代表结点的个数， m 代表要查询的数据组数。
接下来 n 行，每行输入两个数，代表1~ n 结点的孩子结点，如果没有孩子结点则输入-1，根节点为1。
接下来 m 行，每行输入两个数，代表要查询的两个结点。
输出
每组测试数据输出 m 行，代表查询的两个结点之间的最短路径长度。
测试样例
输入
1
8 4
2 3
4 5
6 -1
-1 -1
-1 7
-1 -1
8 -1
-1 -1
1 6
4 6
4 5
8 1
输出
2
4
2
4
分析
第一感觉，最近公共祖先，可以用双亲表示法。后来想想，可以用图。
代码1（树）

/*
双亲表示法，记录父节点 
记录高度
同等高度一起爬找祖先，相等即为最近公共祖先 
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e+5;int high[maxn];//当前结点高度 
int fa[maxn];//记录父节点 //初始化函数
void init()
{fa[1]=0;//memset(high,0,sizeof(high));
}//打印 
void print(int n)
{cout<<"结点号"<<"\t"<<"父节点"<<"\t"<<"高度"<<endl; for(int i=1;i<=n;i++){cout<<i<<"\t"<<fa[i]<<"\t"<<high[i]<<endl;}
}//返回最短路径长度 
int minlen(int x,int y)
{int len=0;int max,min;//记录深浅的两个结点max = high[x]>high[y]? x:y;min = high[x]>high[y]? y:x; //深的结点回到与浅的结点同一高度 while(high[max]!=high[min]){max=fa[max];++len;}//同时向上爬 while(max!=min){len+=2;max=fa[max];min=fa[min];}return len;
}//主函数 
int main()
{int T;int n,m;int x,y;scanf("%d",&T);while(T--){init();                     //初始化scanf("%d %d",&n,&m);       //读入结点数与查询数 for(int i=1;i<=n;i++)       //建树 {scanf("%d %d",&x,&y);if(x!=-1){fa[x]=i;}if(y!=-1){fa[y]=i;}} for(int i=1;i<=n;i++)     //计算高度 {int cur_node = i;while(fa[cur_node]!=0){high[i]++;cur_node=fa[cur_node];}}//print(n);                  //调试用 for(int i=0;i<m;i++)       //读入查询 {scanf("%d %d",&x,&y);printf("%d\n",minlen(x,y));}}return 0;
}

用例图

结点双亲表

结点	双亲
1	0
2	1
3	1
4	2
5	2
6	3
7	5
8	7

结点高度表

结点	高度
1	0
2	1
3	1
4	2
5	2
6	2
7	3
8	4

结果截图
测试用例结果截图
代码2（图）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4;
const int INF = 1e9;ll d[maxn+1][maxn+1];//最短路径距离 //初始化函数
void init(int n)
{for(int i=1;i<=n;++i)//初始化d {for(int j=1;j<=n;++j)d[i][j]=i==j?0:INF;	}
} 
//弗洛伊德算法 
void floyd(int n)
{for(int k=1;k<=n;++k)for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){if(d[i][k]!=INF&&d[k][j]!=INF&&d[i][j]>d[i][k]+d[k][j]){d[i][j]=d[i][k]+d[k][j];}		}	
}
//打印函数
void print(int n)
{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<d[i][j]<<" ";cout<<endl;}	
} 
//主函数 
int main()
{int T;int n,m;int x,y;scanf("%d",&T);while(T--){scanf("%d %d",&n,&m);init(n);               //初始化 for(int i=1;i<=n;++i)  //读入边 {scanf("%d %d",&x,&y);if(x!=-1)d[i][x]=d[x][i]=1;//无向图if(y!=-1)d[i][y]=d[y][i]=1; }floyd(n);//print(n);for(int i=1;i<=m;i++)//读入查询 {scanf("%d %d",&x,&y);printf("%d\n",d[x][y]);}}return 0;	
}

结果截图
运行结果截图

Problem C 最短路径

题目描述
在白天和黑夜要从城市1到城市 n ，黑夜会关掉若干条线路，分别寻找城市1到城市 n 的在白天和黑夜的最短路径。
输入
第一行数据组数 T
第二行输入 n , m , k . n 代表城市数， m 代表路径数， k 代表夜间关闭的路径数
接下来 m 行，每行输入两个数 x , y ，代表城市 x 和城市 y 之间连通
最后一行 k 个数，代表晚上关闭的线路序号（线路序号指的是1~ m ）
输出
每组数据输出两行，分别代表白天和黑夜，城市1到 n 的最短路径
测试样例
输入
1
4 4 1
1 2
2 3
3 4
1 4
4
输出
1
3
分析
这题之前没有说清楚题意，后面好像说输入数据可能有重边。好像13个3A的，大神看见的话请评论吧
代码