首页 > 代码库 > Problem-A 老衲的嘱托
Problem-A 老衲的嘱托
这道题很简单，该怎么做，题目已经告诉我们了！
解题思路：考的就是一个DFS的应用，然后在进行一个选择判断就行了！
由于时间的关系，为了避免超时，可以优化进行剪枝一下！就是在找到了我们所需要的答案后，就不必再进行DFS搜索了，即可直接退出来了，然后输出答案即可！
代码如下：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,cot,pp[100],yw[100],a[800000][10];
bool vis[100];
void dfs(int cur)
{
if(cur>=n)
{
for(int k=0; k<n; k++)
a[cot][k]=pp[k];
cot++;
return ;
}
for(int i=1; i<=n; i++)
if(!vis[i])
{
vis[i]=true;
pp[cur]=i;
dfs(cur+1);
vis[i]=false;
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
cot=1;
memset(yw,0,sizeof(yw));
memset(vis,false,sizeof(vis));
for(int i=0; i<n; i++)
cin>>yw[i];
dfs(0);
//cout<<cot<<endl;
/* for(int i=1;i<cot;i++)
{
for(int j=0;j<n;j++)
printf("%d ",a[i][j]);
printf("\n");
}*/
for(int i=1; i<cot; i++)
{
int flag=0;
for(int j=0; j<n; j++)
if(a[i][j]!=yw[j])
{
flag=1;
break;
}
if(!flag)
{
cout<<i<<endl;
break;
}
}
}
return 0;
}
Description
和尚最近突然对道家有了兴趣，他偶然得到在青城山上有一个神秘宝藏的消息。于是他带着他的和尚班的小伙伴们上山寻找，在寻宝地图的帮助下，他们成功来到藏宝地点，并拿出了藏宝的宝箱。只见这藏箱上只有几个数字，并且这几个数字看似是1~n的一个排列，和尚由于小时候数学是体育老师教的，一筹莫展。 特来向你求助，想请你帮他打开宝箱。 尽管和尚的数学是体育老师教的，但是他的历史却是考古学家教的，他老师告诉他，古时候青城山的人喜欢用数字的全排列是其字典序排列的第几作为密码，并且留下这个排列作为密码的提示。和尚觉着这宝箱上面的排列是这n个数字全排列的第几个应该就是密码了，他想让你帮他找出来。
Input
测试数据包含多组
每组测试数据第一行包含一个N( 1 < = n < = 9 )，代表宝箱上数字的个数
第二行包含n个数字，分别为宝箱上的数字
Output
输出答案仅包含一个，即密码
Sample Input
31 2 322 1
Sample Output
12
Problem-A 老衲的嘱托
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。