刷题向》一道逆向思维题（BZOJ1046）（NORMAL）

　　这道题对于一类题都有一个通用思路：反向递减序列即为正向字典序。

　　对于逆向思维的题还要多做才能培养这种对于逆向思维的感觉。

　　想到这种方法之后，就很简单了。

　　因为n×m不会炸，所以反向LIS叠一个贪心就能过了。

　　直接甩题目&代码

Description

　　对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 < ax
2 < … < axm)。那么就称P为S的一个上升序列。如果有多个P满足条件，那么我们想求字典序最小的那个。任务给
出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先
x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.

Input

　　第一行一个N，表示序列一共有N个元素第二行N个数，为a1,a2,…,an 第三行一个M，表示询问次数。下面接M
行每行一个数L，表示要询问长度为L的上升序列。N<=10000，M<=1000

Output

　　对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.

Sample Input

6
3 4 1 2 3 6
3
6
4
5

Sample Output

Impossible
1 2 3 6
Impossible

 /**************************************************************
     Problem: 1046
     User: PencilWang
     Language: C++
     Result: Accepted
     Time:1860 ms
     Memory:952 kb
 ****************************************************************/ #include<stdio.h>
 #include<math.h>
 #include<algorithm>
 using namespace std;
 int m,n;
 int s[];
 int d[],sb[],ass;
 int bound(int L,int R,int num)
 {
     while(L<=R)
     {
         int mid=(L+R)>>;
         if(d[mid]>num)
         L=mid+;
         else R=mid-;
     }
     return L;
 }
 void fuck()
 {
     int t;
     for(int i=n;i>=;i--)
     {
     t=bound(,ass,s[i]);
     if(t>ass)ass++;
     sb[i]=t;
     if(s[i]>d[t])d[t]=s[i];
     }
     return ;
 }
 void suck(int num)
 {
     int star;
     for(int i=;i<=n;i++)
     {
         if(sb[i]>=num)
         {
         star=i;
         num--;
         break;
         }
     }
     printf("%d",s[star]);
     if(!num)return ;
     for(int i=star+;i<=n&&num;i++)
     if(s[i]>s[star]&&sb[i]>=num)printf(" %d",s[i]),star=i,num--;
     return ;
 }
 int main()
 {
     int num;
     scanf("%d",&n);
     for(int i=;i<=n;++i)scanf("%d",s+i);
     fuck();
     scanf("%d",&m);
     for(int i=;i<=m;i++)
     {
     scanf("%d",&num);
     if(num>ass)printf("Impossible\n");
     else suck(num),printf("\n");
     }
     return ;
 }