【题解】集训day4

这里只写一部分题解，后两题。（E 还没弄出来，明天再搞吧[大哭]）

F. FBI 树

这道题主要就是递归，后序遍历。（左-右-根）

当 $len1$ 为 $1$ 的时候就输出同时 return

#include
#include
#include
using namespace std;
int n,len1;
char s[100009];//数字串 

void build(char s1[100009]){

	len1 = strlen(s1);
//	printf("len1:%d\n",len1);
	if(len1 == 1){
		if(s1[0] == '0')cout << 'B';
		if(s1[0] == '1')cout << 'I';
		return;
	}
	char left[10009],right[10009];
	for(int i=0; i> n;
	cin >> s;
	len1 = strlen(s);
	build(s);
	return 0;
}

然后我写的时候有个玄学错误也不知道为啥，改了一下就过了（

G. 火星人

20pts 做法：枚举所有的排列。（也就是全排列问题）这种做法很好想，但是会 T 飞。

100pts 做法：只不过这次也是搜索排列，但是我们从它给出的那个排列开始搜索。

#include
using namespace std;
int n;
int m;
int a[1100009];//火星人的排列顺序
int vis[100009];
int s[1000009];
int f1 = 0;
int sum=0,pos=-1,wants;
void dfs(int step){
	if(step == n+1){
		f1 = 1;
		sum++;
		if(sum == m+1){
			for(int i=1; i<=n; i++)cout << s[i] << ' ';
			exit(0);
		}
		return;
	}
	for(int i=1; i<=n; i++){
		if(vis[i] == 0){
			s[step] = i;
			if(f1 == 0 && s[step] != a[step])continue;
			vis[i] = 1;
			dfs(step+1);
			vis[i] = 0;
		}
	}
}

int main(){
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		cin >> a[i];
	}
	
	dfs(1);//还没有填位置1 
	return 0;
}