机试练习Day1-2019真题

川长思鸟来 2024-03-26 12:29 64阅读 0赞

#### 目录 ####

*   *  Problem A：32位二进制数的加法
     *   *  题目：
         *  样例：
         *  代码:
         *  运行：
         *  复盘：
     *  Problem B：二叉树结点间的最短距离
     *   *  题目：
         *  样例：
         *  代码：
         *  运行：
         *  复盘：
     *  Problem C：两个城市间的最短路径
     *   *  题目：
         *  样例：
         *  代码：
         *  运行：
         *  复盘：
     *  整体复盘

### Problem A：32位二进制数的加法 ###

#### 题目： ####

**第一行：输入测试数据组数N，第二行开始：输入N行32位的二进制数。**  
**对其进行+1，+3后，输出N\*2行计算结果。**

#### 样例： ####

![在这里插入图片描述][82c36451e0f84c86a53bc848b49bf13a.png_pic_center]

#### 代码: ####

[学习参考原址][Link 1]

#include<bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        
    	int T;
    	cin>>T;
    	while(T--)
    	{
        
    		string str;
    		cin>>str;
    		
    		//找到最低位 +1
    		int idx=str.size()-1; 
    		while(str[idx]=='1')
    		{
        
    			str[idx--]='0'; 
    		}
    		str[idx]='1'; 
    		cout<<str<<endl;
    		
    		//找到最低位 +1
    		idx=str.size()-1;
    		while(str[idx]=='1')
    		{
        
    			str[idx--]='0';
    		}
    		str[idx]='1';
    		
    		找到最低位 +1
    		idx=str.size()-1;
    		while(str[idx]=='1')
    		{
        
    			str[idx--]='0';
    		}
    		str[idx]='1';
    		
    		cout<<str<<endl;
    	}
    	return 0;
     }

#### 运行： ####

![在这里插入图片描述][34f73b684bf44d708e1960b915793951.png_pic_center]

#### 复盘： ####

万能头文件：

#include<bits/stdc++.h>
    using namespace std;

字符串：

string str;
    		cin>>str;

![在这里插入图片描述][bebed8646b314c8fb30ff02e299cbfcb.png_pic_center]  
每次加1：

idx=str.size()-1;
    		while(str[idx]=='1')
    		{
        
    			str[idx]='0'; 
    			idx=idx-1;
    		}
    		str[idx]='1';

### Problem B：二叉树结点间的最短距离 ###

#### 题目： ####

**第一行输入测试数据组数T，第二行输入二叉树的结点个数n和要查询的数据组数m，第三行开始输入n行，每行两个数，代表每个结点的孩子编号（根节点为1，没有孩子结点为-1），第3+n+1行开始输入m行，每行两个数，代表要查询的两个结点。**  
**输出m行，代表m组结点间的最短距离。**

#### 样例： ####

![在这里插入图片描述][894c9a3e9cc94c5c97ed0ada7b250b2f.png_pic_center]

#### 代码： ####

#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函数是内存赋值函数，用来给某一块内存空间进行赋值的
    		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;
     }

#### 运行： ####

![在这里插入图片描述][42f36c962f1142ee9ef1c55ba4aa0a56.jpeg_pic_center]

#### 复盘： ####

和Problem A一样，第一个数值都是测试数据的组数。  
两个不同结点间的距离（将其称为左结点和右结点），那么可以通过找两者的父节点、父节点的父节点…直到结点重合，这是一个递归的过程。

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 ;
    }

### Problem C：两个城市间的最短路径 ###

#### 题目： ####

**背景：晚上因为会关掉某些路，所以从城市1到城市n白天和晚上的最短路径可能不同。**  
**第一行输入测试数据组数T，第二行输入城市数n，路径数m，晚上关闭的路径数k。**  
**接下来n行，输入n条边的两个端点及长度。最后一行k个数，表示晚上关闭的线路序号。**  
**输出两行，分别代表白天和黑夜从城市1到城市n的最短路径长度。**

#### 样例： ####

![在这里插入图片描述][54a560d6db024a8ca2163e3b2c6b12d7.png_pic_center]

#### 代码： ####

#include<bits/stdc++.h>
    using namespace std;
    
    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;
    }

#### 运行： ####

![在这里插入图片描述][fa66a9a48dbd41d2b6b83a8ae8e88400.png_pic_center]

#### 复盘： ####

在定义边的时候采用了结构体：

struct E{
        
    	int a,b;//道路的两个端点 
    	int cost;//道路的长度 
    }Edge[505];

### 整体复盘 ###

*  二进制的加法，手算的时候记得过程，但是写成代码刚开始就很慌乱。
 *  11111111111111111111111111111111的加法要另外写，这个根本就忘记了，后来看大家分享才发现这个坑。
 *  计算二叉树两个结点间的距离，手算是会的，但是写成代码就要考虑考虑计算机的计算过程了。
 *  构建二叉树时也有点慌乱。
 *  图论中，构建边，通常会使用结构体这件事情也忘记了。
 *  Floyed算法就更不用说了，一干二净。

[82c36451e0f84c86a53bc848b49bf13a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6c5ee0ce1d2140838f4e7544ce02dcc8.png
[Link 1]: https://blog.csdn.net/fjcode/article/details/88916087/
[34f73b684bf44d708e1960b915793951.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/62d28223fdda4cc681cfddd8cfddf9cb.png
[bebed8646b314c8fb30ff02e299cbfcb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2fa832ed503e432390223be48de88fde.png
[894c9a3e9cc94c5c97ed0ada7b250b2f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/eb66a6eca5884324811c7c00de49f7a6.png
[42f36c962f1142ee9ef1c55ba4aa0a56.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/b8d26b86fc0d456886412ce3af1ee2cb.png
[54a560d6db024a8ca2163e3b2c6b12d7.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0f1ab0fa417d4dd0af4228d327331541.png
[fa66a9a48dbd41d2b6b83a8ae8e88400.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e988d388c87e42e9bbd53104b0831338.png