wix建站教程,做推文的编辑网站,公司logo设计免费生成软件,做网站费用滁州这道题对于一类题都有一个通用思路#xff1a;反向递减序列即为正向字典序。 对于逆向思维的题还要多做才能培养这种对于逆向思维的感觉。 想到这种方法之后#xff0c;就很简单了。 因为nm不会炸#xff0c;所以反向LIS叠一个贪心就能过了。 直接甩题目代码 Descripti… 这道题对于一类题都有一个通用思路反向递减序列即为正向字典序。 对于逆向思维的题还要多做才能培养这种对于逆向思维的感觉。 想到这种方法之后就很简单了。 因为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的上升序列。N10000M1000 Output 对于每个询问如果对应的序列存在则输出否则打印Impossible. Sample Input 6 3 4 1 2 3 6 3 6 4 5 Sample Output Impossible 1 2 3 6 Impossible 1 /**************************************************************2 Problem: 10463 User: PencilWang4 Language: C5 Result: Accepted6 Time:1860 ms7 Memory:952 kb8 ****************************************************************/9
10 #includestdio.h
11 #includemath.h
12 #includealgorithm
13 using namespace std;
14 int m,n;
15 int s[11000];
16 int d[11000],sb[11000],ass;
17 int bound(int L,int R,int num)
18 {
19 while(LR)
20 {
21 int mid(LR)1;
22 if(d[mid]num)
23 Lmid1;
24 else Rmid-1;
25 }
26 return L;
27 }
28 void fuck()
29 {
30 int t;
31 for(int in;i1;i--)
32 {
33 tbound(1,ass,s[i]);
34 if(tass)ass;
35 sb[i]t;
36 if(s[i]d[t])d[t]s[i];
37 }
38 return ;
39 }
40 void suck(int num)
41 {
42 int star;
43 for(int i1;in;i)
44 {
45 if(sb[i]num)
46 {
47 stari;
48 num--;
49 break;
50 }
51 }
52 printf(%d,s[star]);
53 if(!num)return ;
54 for(int istar1;innum;i)
55 if(s[i]s[star]sb[i]num)printf( %d,s[i]),stari,num--;
56 return ;
57 }
58 int main()
59 {
60 int num;
61 scanf(%d,n);
62 for(int i1;in;i)scanf(%d,si);
63 fuck();
64 scanf(%d,m);
65 for(int i1;im;i)
66 {
67 scanf(%d,num);
68 if(numass)printf(Impossible\n);
69 else suck(num),printf(\n);
70 }
71 return 0;
72 } 转载于:https://www.cnblogs.com/PencilWang/p/6007421.html
