普达建站快车,重庆相亲网,阿里云建站,商城网站模板图题目
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言#xff0c;但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的#xff0c;首先#xff0c;火星人把一个非常大的数字告诉人类科学家#xff0c;科学家破解这个数… 题目
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的首先火星人把一个非常大的数字告诉人类科学家科学家破解这个数字的含义后再把一个很小的数字加到这个大数上面把结果告诉火星人作为人类的回答。
火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手但这只手上有成千上万的手指这些手指排成一列分别编号为1,2,3,⋯。火星人的任意两根手指都能随意交换位置他们就是通过这方法计数的。
一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为1,2,3,4和5当它们按正常顺序排列时形成了5位数12345当你交换无名指和小指的位置时会形成5位数12354当你把五个手指的顺序完全颠倒时会形成54321在所有能够形成的120个5位数中12345最小它表示112354第二小它表示254321最大它表示120。下表展示了只有3根手指时能够形成的6个3位数和它们代表的数字
三进制数代表的数字123113222133231431253216
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指科学家会告诉你要加上去的很小的数。你的任务是把火星人用手指表示的数与科学家告诉你的数相加并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。
输入输出格式
输入格式
共三行。 第一行一个正整数N表示火星人手指的数目1≤N≤10000。 第二行是一个正整数M表示要加上去的小整数1≤M≤100。 下一行是1到N这N个整数的一个排列用空格隔开表示火星人手指的排列顺序。
输出格式
N个整数表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开不能有多余的空格。
代码1
#includeiostream
using namespace std;
int n,m,a[10005],visit[10005];//a[]数组用来存放排列结果visit[]标记
int flag,amount;//flag用来判别是否找到答案amount用于存储目前在哪个全排列
void dfs(int step){if(flag){//如果已经找到答案就一直return直到dfs函数结束 return;}if(stepn){//如果已经超出边界有一个全排列 amount;//计数一次 if(amountm1){//这里的判别注意是M1因为火星人最开始给出的排序也加在count里面 flag1;//找到了输出 for(int i1;in;i){couta[i] ;}return;}}for(int i1;in;i){if(!amount){//核心代码 ia[step];}if(!visit[i]){//全排列模板 visit[i]1;a[step]i;dfs(step1);visit[i]0;}}
}
int main(){cinnm;for(int i1;in;i){cina[i];}dfs(1);//从1开始搜索 return 0;
}
上述代码的核心代码是if (!amount) i ans[step] 这行核心代码实现的是跳转到这次搜索的起始位置。举一个1到5的全排列的例子在用dfs实现1到5全排列的时候第一个全排列是1 2 3 4 5 。由于在我们的搜索中有循环的存在我们才得以枚举所有情况。那么如果把一个dfs的递归工作栈展开就是一个多重循环那么这个多重循环的i的值都不一样都在特定的位置上搜索到哪个数字就等于哪个数字。由于要快速找到火星人给的顺序就必须确定该顺序的多重循环的每一个i的值。因此使用ians[step]语句;ans存放的是火星人给的排列由此可以确定每一个i。
代码2
#includeiostream
#includealgorithm
using namespace std;
int n,m,a[10005];
int main(){cinnm;for(int i1;in;i){cina[i];}for(int i1;im;i){next_permutation(a1,a1n);//求下一个全排列函数 }for(int i1;in;i){couta[i] ;}return 0;
}
