轉載請注明出處： http://www.cnblogs.com/fraud/ ——by fraud
ZZX and Permutations
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 181 Accepted Submission(s): 38
Problem Description ZZX likes permutations.
ZZX knows that a permutation can be decomposed into disjoint cycles(see https://en.wikipedia.org/wiki/Permutation#Cycle_notation). For example:
145632=(1)(35)(462)=(462)(1)(35)=(35)(1)(462)=(246)(1)(53)=(624)(1)(53)……
Note that there are many ways to rewrite it, but they are all equivalent.
A cycle with only one element is also written in the decomposition, like (1) in the example above.
Now, we remove all the parentheses in the decomposition. So the decomposition of 145632 can be 135462,462135,351462,246153,624153……
Now you are given the decomposition of a permutation after removing all the parentheses (itself is also a permutation). You should recover the original permutation. There are many ways to recover, so you should find the one with largest lexicographic order.
Input First line contains an integer t, the number of test cases.
Then t testcases follow. In each testcase:
First line contains an integer n, the size of the permutation.
Second line contains n space-separated integers, the decomposition after removing parentheses.
n≤105. There are 10 testcases satisfying n≤105, 200 testcases satisfying n≤1000.
Output Output n space-separated numbers in a line for each testcase.
Don't output space after the last number of a line.
Sample Input 2 6 1 4 5 6 3 2 2 1 2
Sample Output 4 6 2 5 1 3 2 1
和題解的解法幾乎一緻，然而卻在比賽結束後才意識到自己跪在了一個傻逼的地方，真是2333333
貪心，先放第一個位置，放盡可能大的值，然後依次往後，對于每個值，看其後面的一個位置，或者前面沒有使用過的連續區間
1 //#####################
2 //Author:fraud
3 //Blog: http://www.cnblogs.com/fraud/
4 //#####################
5 //#pragma comment(linker, "/STACK:102400000,102400000")
6 #include <iostream>
7 #include <sstream>
8 #include <ios>
9 #include <iomanip>
10 #include <functional>
11 #include <algorithm>
12 #include <vector>
13 #include <string>
14 #include <list>
15 #include <queue>
16 #include <deque>
17 #include <stack>
18 #include <set>
19 #include <map>
20 #include <cstdio>
21 #include <cstdlib>
22 #include <cmath>
23 #include <cstring>
24 #include <climits>
25 #include <cctype>
26 using namespace std;
27 #define XINF INT_MAX
28 #define INF 0x3FFFFFFF
29 #define MP(X,Y) make_pair(X,Y)
30 #define PB(X) push_back(X)
31 #define REP(X,N) for(int X=0;X<N;X++)
32 #define REP2(X,L,R) for(int X=L;X<=R;X++)
33 #define DEP(X,R,L) for(int X=R;X>=L;X--)
34 #define CLR(A,X) memset(A,X,sizeof(A))
35 #define IT iterator
36 typedef long long ll;
37 typedef pair<int,int> PII;
38 typedef vector<PII> VII;
39 typedef vector<int> VI;
40 int Scan() {
41 int res=0, ch;
42 while(ch=getchar(), ch<'0'||ch>'9');
43 res=ch-'0';
44 while((ch=getchar())>='0'&&ch<='9')
45 res=res*10+ch-'0';
46 return res;
47 }
48 void Out(int a) {
49 if(a>9)
50 Out(a/10);
51 putchar(a%10+'0');
52 }
53 int a[100010];
54 int vis[100010];
55 int pos[100010];
56 int fa[100010];
57 int dp[600010];
58 int ans[100010];
59 set<int> ms;
60 int n;
61 set<int>::IT it;
62 int find(int x){
63 if(fa[x]!=x)fa[x] = find(fa[x]);
64 return fa[x];
65 }
66 void push_up(int cur){
67 dp[cur] = max(dp[cur<<1],dp[cur<<1|1]);
68 }
69 void build(int l,int r,int cur){
70 if(l==r){
71 dp[cur] = a[l];
72 return;
73 }
74 int mid = (l+r)>>1;
75 build(l,mid,cur<<1);
76 build(mid+1,r,cur<<1|1);
77 push_up(cur);
78 }
79 void update(int l,int r,int cur,int x,int inc){
80 if(l==r&&l==x){
81 dp[cur] = inc;
82 return;
83 }
84 int mid = (l+r)>>1;
85 if(x<=mid)update(l,mid,cur<<1,x,inc);
86 else update(mid+1,r,cur<<1|1,x,inc);
87 push_up(cur);
88 }
89 void update(int x,int num){
90 update(1,n,1,x,num);
91 }
92 int query(int l,int r,int lx,int rx,int cur){
93 if(l>=lx&&r<=rx)return dp[cur];
94 if(lx>r||rx<l)return 0;
95 int mid = (l+r)>>1;
96 return max(query(l,mid,lx,rx,cur<<1),query(mid+1,r,lx,rx,cur<<1|1));
97 }
98 int query(int l,int r){
99 return query(1,n,l,r,1);
100 }
101 int main(){
102 int t;
103 t = Scan();
104 while(t--){
105 n = Scan();
106 for(int i = 1;i<=n;i++){
107 a[i] = Scan();
108 vis[i] = 0;
109 pos[a[i]] = i;
110 fa[i] = i;
111 }
112 for(int i=0;i<=3*n;i++)dp[i] = 0;
113 build(1,n,1);
114 ms.clear();
115 ms.insert(0);
116 ms.insert(-INF);
117 for(int i=1;i<=n;i++){
118 if(vis[i])continue;
119 int l;
120 int posi = pos[i];
121 int maxx = find(i);
122 int p =pos[maxx];
123 if(posi+1<=n&&!vis[a[posi+1]]){
124 if(a[posi+1]>maxx){
125 p = posi+1;
126 maxx = a[p];
127 }
128 }
129 if(posi>1){
130 it = ms.upper_bound(-posi);
131 l = *it;
132 l = -l;
133 l++;
134 int tmp = query(l,posi);
135 //tmp = find(tmp);
136 //cout<<l<<" "<<tmp<<endl;
137 if(tmp>maxx){
138 maxx = tmp;
139 p = pos[tmp];
140 }
141 }
142 if(p==posi){
143 ans[i] = i;
144 vis[i] = 1;
145 ms.insert(-posi);
146 }else if(p==posi+1){
147 fa[maxx] = fa[i];
148 //ans[posi] = maxx;
149 update(p,0);
150 }else{
151 ans[i] = a[p];
152 vis[a[p]] = 1;
153 for(int j=p+1;j<=posi;j++){
154 ans[a[j-1]] = a[j];
155 vis[a[j]] = 1;
156 }
157 ms.insert(-posi);
158 }
159 /* cout<<i<<" "<<p<<" "<<maxx<<endl;
160 for(int i=1;i<=n;i++){
161 cout<<ans[i]<<" ";
162 }
163 cout<<endl;*/
164 }
165 for(int i=1;i<=n;i++){
166 if(i!=1)putchar(' ');
167 Out(ans[i]);
168 }
169 puts("");
170 }
171 return 0;
172 }
173
174 轉載于:https://www.cnblogs.com/fraud/p/4690549.html
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)