2014
02-12

# Sequence two

Search is important in the acm algorithm. When you want to solve a problem by using the search method, try to cut is very important.
Now give you a number sequence, include n (<=100) integers, each integer not bigger than 2^31, you want to find the first P subsequences that is not decrease (if total subsequence W is smaller than P, than just give the first W subsequences). The order of subsequences is that: first order the length of the subsequence. Second order the subsequence by lexicographical. For example initial sequence 1 3 2 the total legal subsequences is 5. According to order is {1}; {2}; {3}; {1,2}; {1,3}. If you also can not understand , please see the sample carefully.

The input contains multiple test cases.
Each test case include, first two integers n, P. (1<n<=100, 1<p<=100000).

The input contains multiple test cases.
Each test case include, first two integers n, P. (1<n<=100, 1<p<=100000).

3 5
1 3 2
3 6
1 3 2
4 100
1 2 3 2

1
2
3
1 2
1 3

1
2
3
1 2
1 3

1
2
3
1 2
1 3
2 2
2 3
1 2 2
1 2 3

HintHint : You must make sure each subsequence in the subsequences is unique. 

//给你一个序列，要求找出它的递增子序列，按照长度从小到大，序列元素按字典序
//然后输入前m个子序列
/*
按照深度一层一层的搜索，如果在寻找该层中满足条件的元素时，
要判断之前是否出现过（是指之前找该层时是否出现过相等的元素）
如果之前出现过，continue就可以了。
没有的话，保留当前位置的值
比如2 3 3 4
我们上一层找到2了，这一层先找到3，因为3没出现过所以pre=3；
然后循环继续，有找到该层中满足情况的一个3(3>=2)，因为之前已经出现过一个3了，所以continue就可以了。
然后继续，找到满足的一个4(4>=2)，4之前没出现过，更新pre=4;
*/
#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
#define N 101

int a[N];
int n,m;
struct node
{
int n,pos;
}A[N];
int f;
int cnt;
int len;
int path[N];
bool cmp(node a,node b)
{
if(a.n!=b.n)
return a.n<b.n;
return a.pos<b.pos;
}

void print(int len)
{
int i;
for(i=0;i<len-1;i++)
printf("%d ",path[i]);
printf("%d\n",path[i]);

}
//dep为深度,pos为搜索的位置，repos表示重复的位置
int dfs(int dep,int pos,int repos)
{
if(dep==len)
{
cnt++;
print(len);
if(cnt==m)return 1;
return 0;
}
int pre;
int f=0;
for(int i=pos;i<=n;i++)
{
//子串的下标也是递增的
if(A[i].pos>repos)
{
if(f==0){f=1;pre=A[i].n;}//判重
//如果相等的话，说明有重的，continue
else if(pre==A[i].n)continue;//判重
pre=A[i].n;//如果不相等的话保留当前位置的值
path[dep]=A[i].n;
if(dfs(dep+1,i+1,A[i].pos))return 1;
}
}
return 0;
}

int main()
{
int i;
while(scanf("%d%d",&n,&m)!=-1)
{
for(i=1;i<=n;i++)
{
scanf("%d",&A[i].n);
A[i].pos=i;
}
sort(A+1,A+1+n,cmp);
cnt=0;
for(i=1;i<n;i++)
{
len=i;
if(dfs(0,1,0))break;
}
printf("\n");
}
return 0;
}

1. 周星驰！我只知道他演的霹雳先锋，捕风汉子，最佳女婿，龙在天涯，流氓差婆，望夫成龙，一本漫画闯天涯，龙凤茶楼，风雨同路，咖喱辣椒，小偷阿星，师兄撞鬼，赌圣，无敌幸运星，江湖最后一个大佬，赌侠，整蛊专家，龙的传人，新精武门，逃学威龙，情圣，漫画威龙，家有喜事

2. 我刷得真辛苦。这样真不好。本来我想直接回复在原有的留言那里的。结果又变成一条新留言。这样我要帮谁实现愿望。谁又帮我实现愿望。一切都乱了。提议统一说愿望。留联系方式。愿意帮你实现愿望的就自己主动联系。

3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确