【蓝桥杯】堆积木

题目

蒜头君有 $块积木，编号分别为到。$

一开始，蒜头把第 $块积木放在位置。$

蒜头君进行 $次操作，每次操作，蒜头把位置上的积木整体移动到位置上面。$

比如 $位置的积木是，位置的积木是，那么把位置的积木移动到位置后，位置上的积木从下到上依次为。$

输入格式

第一行输入 $<math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application/x-tex"> 2 </annotation> </semantics> </math> 个整数 <math> <semantics> <mrow> <mi> n </mi> <mo separator="true"> , </mo> <mi> m </mi> <mo> ( </mo> <mn> 1 </mn> <mo> ≤ </mo> <mi> n </mi> <mo> ≤ </mo> <mn> 10000 </mn> <mo separator="true"> , </mo> <mn> 0 </mn> <mo> ≤ </mo> <mi> m </mi> <mo> ≤ </mo> <mn> 10000 </mn> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> n,m(1 \le n \le 10000, 0 \le m \le 10000) </annotation> </semantics> </math>$

接下来 $<math> <semantics> <mrow> <mi> m </mi> </mrow> <annotation encoding="application/x-tex"> m </annotation> </semantics> </math> 行，每行输入 <math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application/x-tex"> 2 </annotation> </semantics> </math> 个整数 <math> <semantics> <mrow> <mi> a </mi> <mo separator="true"> , </mo> <mi> b </mi> <mo> ( </mo> <mn> 1 </mn> <mo> ≤ </mo> <mi> a </mi> <mo separator="true"> , </mo> <mi> b </mi> <mo> ≤ </mo> <mi> n </mi> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> a, b(1 \le a, b \le n) </annotation> </semantics> </math>$

输出格式

输出 $行，第行输出位置从下到上的积木编号，如果该行没有积木输出一行空行。$

样例输入

2 2

1 2

1 2

样例输出

1 2

样例输入

4 4

3 1

4 3

2 4

2 2

样例输出


2 4 3 1

题解

#include<iostream>
#include<algorithm>
#include<vector> 
using namespace std;
int main(){
	int n,m;
	vector<vector<int> > v;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		vector<int> t;
		t.push_back(i);
		v.push_back(t);
	}
	int d1,d2;
	for(int i=0;i<m;i++){
		cin>>d1>>d2;
		d1--;
		d2--;
		if(d1!=d2){
			// 将位置 d2 上的积木整体移动 
			for(int j=0;j<v[d2].size();j++)
				v[d1].push_back(v[d2][j]);
			// 清空动态数组内存,clear不行 
			{   
				vector<int> t;
				v[d2].swap(t); 
			}
		}
	}
	for(int i=0;i<n;i++){
		if(v[i].size()){
			cout<<v[i][0];
			for(int j=1;j<v[i].size();j++)
				cout<<" "<<v[i][j];
		}
		cout<<endl;
	}
	return 0;
}

返回目录，查看更多