BFS
然后每次上升可以的范围是一个区间，然后每次都遍历这个区间的所有点，那么超时。用set等方式，合并这些区间，之前没遍历过的范围才更新（加入BFS需要遍历的队列里）。但是区间的更新特别容易写错……
我的代码 和 造数据
1 /**
2 记录两个vis？
3 1. 向上到达的区间
4 2. 下滑到的点
5 **/
6 //#include <bits/stdc++.h>
7 #include <cstdio>
8 #include <cstdlib>
9 #include <cstring>
10 #include <cmath>
11 #include <cstdbool>
12 #include <string>
13 #include <algorithm>
14 #include <iostream>
15 #include <sstream>
16 #include <ctime>
17 #include <stack>
18 #include <vector>
19 #include <queue>
20 #include <set>
21 #include <map>
22 #include <array>
23 #include <bitset>
24 using namespace std;
25 #define LL long long
26 #define ULL unsigned long long
27
28 const LL mod_1=1e9+7;
29 const LL mod_2=998244353;
30
31 const double eps_1=1e-5;
32 const double eps_2=1e-10;
33
34 const int maxn=3e5+10;
35
36 set<pair<int,int> > s;
37 set<pair<int,int> >::iterator it;
38 vector<pair<int,int> > need_del;
39
40 int q[maxn],hap[maxn],a[maxn],b[maxn],step[maxn],pre[maxn],reach[maxn];
41 bool vis_down[maxn];
42
43 int n,i,head,tail,d,x,y,L,R,pre_x,nex_y,old_y;
44
45 ///test
46 LL TEST_hap_Z=0, TEST_hap_interval=0;
47 bool visz[maxn];
48 bool print_test=0;
49
50 void add_q(int Z1, int Z2)
51 {
52 int Z, cur_pos;
53 if (print_test)
54 TEST_hap_Z++;
55 if (print_test)
56 printf("Z range %d %d\n",Z1,Z2);
57 for (Z=Z1;Z<=Z2;Z++)
58 {
59 if (print_test)
60 {
61 if (visz[Z])
62 {
63 printf("Z overlap\n");
64 exit(1);
65 }
66 visz[Z]=1;
67 }
68
69 cur_pos = Z+b[Z];
70
71 if (!vis_down[cur_pos])
72 {
73 vis_down[cur_pos]=1;
74 tail++;
75 q[tail]=cur_pos;
76 step[cur_pos]=step[d]+1;
77 pre[cur_pos]=d;
78 reach[cur_pos]=Z;
79 }
80 }
81 }
82
83 void print(int D)
84 {
85 if (D==n)
86 return;
87 print(pre[D]);
88 printf("%d ",reach[D]);
89 }
90
91 void test_print()
92 {
93 exit(0);
94 cout<<"TEST_hap_Z="<<TEST_hap_Z<<" TEST_hap_interval="<<TEST_hap_interval<<endl;
95 }
96
97 int main()
98 {
99 if (print_test)
100 memset(visz,0,sizeof(visz));
101
102 memset(hap,0,sizeof(hap));
103 scanf("%d",&n);
104 for (i=1;i<=n;i++)
105 scanf("%d",&a[i]);
106 for (i=1;i<=n;i++)
107 scanf("%d",&b[i]);
108 b[0]=0;
109
110 memset(vis_down,0,sizeof(vis_down));
111 memset(step,0xff,sizeof(step));
112 head=0,tail=1;
113 vis_down[n]=1,step[n]=0,q[1]=n;
114 while (head<tail)
115 {
116 ///不能先添加一个相同的，再删除一个相同的。那么本来要添加的就没有了
117 for (auto pa : need_del)
118 {
119 if (print_test)
120 cout<<"need erase "<<pa.first<<" "<<pa.second<<endl;
121 s.erase(pa);
122 }
123
124 need_del.clear();
125
126 if (print_test)
127 {
128 for (auto auto_set_pair:s)
129 cout<<auto_set_pair.first<<" "<<auto_set_pair.second<<" ; ";
130 cout<<endl;
131 }
132
133 head++;
134 d = q[head];
135 R = d;
136 L = d - a[ d ];
137
138
139 R--;
140 if (L>R)
141 continue;
142
143
144 ///after jump up : range [L,R]
145
146 if (L==0)
147 {
148 printf("%d\n",step[d]+1);
149 print(d);
150 printf("0\n");
151 if (print_test)
152 test_print();
153 return 0;
154 }
155
156 ///>
157 it = upper_bound( s.begin(), s.end(), make_pair(L, R) ); ///v
158
159 if (s.size()==0)
160 {
161 s.insert( make_pair(L, R) );
162 add_q(L, R);
163 continue;
164 }
165 else if (it==s.begin())
166 {
167 x = L;
168 y = s.begin()->second;
169 add_q(L, s.begin()->first-1);
170
171 if (R<=y)
172 {
173 need_del.push_back( *it );
174 s.insert(make_pair(x, y));
175 continue;
176 }
177 }
178 //else if (it==s.end())
179 else
180 {
181 it--;
182 x = it->first;
183 y = it->second;
184 if (R<=y)
185 continue;
186 }
187
188 pre_x = x;
189
190 while (R>y) ///
191 {
192 if (print_test)
193 TEST_hap_interval++;
194
195 old_y = y;
196
197 need_del.push_back( *it );
198
199 it = ++it;
200 if (it!=s.end())
201 {
202 x = it->first; ///new_interval x
203 y = it->second; ///new_interval y
204 }
205 if (it==s.end() || x>R)
206 {
207 add_q(old_y+1, R);
208 s.insert(make_pair(pre_x, R));
209 continue;
210 }
211
212 add_q(old_y+1, x-1);
213 }
214
215 s.insert(make_pair(pre_x, y));
216 }
217
218 printf("-1\n");
219
220 if (print_test)
221 test_print();
222
223 return 0;
224 }
225 /**
226 1
227 1
228 0
229
230 ======
231
232 5
233 1 1 1 1 1
234 2 2 2 1 0
235
236 ======
237
238 5
239 2 2 2 2 2
240 1 1 1 1 0
241
242 =======
243
244 excel
245
246 10
247
248 1 0 0 3 5 0 4 6 3 1
249 7 0 1 0 0 1 0 3 0 0
250
251
252
253 ======
254
255
256
257 5
258 0 2 1 4 1
259 2 0 0 1 0
260
261
262 5
263 1 2 3 1 0
264 2 2 1 0 0
265
266
267 5
268 1 2 0 0 5
269 0 2 1 0 0
270
271
272 5
273 1 2 2 1 4
274 1 0 0 1 0
275
276
277
278 ======
279
280 Z overlap
281
282
283
284 100
285 0 0 3 4 1 5 1 5 3 5 8 3 4 11 11 9 8 0 9 8 4 8 16 24 15 0 0 6 10 17 9 6 32 34 28 1 12 31 15 16 15 18 8 44 9 36 28 33 42 1 28 49 15 36 48 8 2 20 26 37 18 29 29 7 16 32 30 9 19 35 59 58 65 32 42 7 14 29 37 73 6 37 44 21 56 61 66 75 37 44 55 74 56 49 77 66 68 72 5 12
286 19 56 63 56 11 47 74 35 38 33 69 84 55 13 58 15 43 11 27 34 22 45 43 41 58 68 2 28 21 27 27 22 54 50 10 10 19 6 36 48 38 53 17 56 5 47 41 31 47 33 25 24 35 28 39 8 19 10 33 16 33 9 12 30 1 5 33 25 8 23 19 20 3 26 1 11 18 6 19 4 18 16 4 8 1 8 7 7 6 7 2 2 1 0 3 0 3 0 1 0
287
288
289
290
291 15
292 1 1 0 4 5 0 0 5 4 10 3 8 3 3 1
293 1 3 5 0 10 2 1 0 2 0 0 1 2 0 0
294
295
296
297 ======
298
299
300
301 15
302 1 0 1 1 3 3 5 1 6 2 1 4 10 9 1
303 9 4 7 8 8 5 0 0 5 3 4 0 0 1 0
304
305
306 15
307 1 1 2 4 1 2 6 1 0 6 11 3 0 6 14
308 8 2 1 4 2 0 4 5 5 5 3 3 0 0 0
309
310
311 15
312 0 2 0 4 5 5 4 0 6 1 10 12 5 13 4
313 9 10 0 5 4 8 8 7 4 1 1 2 2 1 0
314
315
316 15
317 1 1 0 4 5 0 0 5 4 10 3 8 3 3 1
318 1 3 5 0 10 2 1 0 2 0 0 1 2 0 0
319
320
321 15
322 1 0 0 1 3 3 7 1 3 10 4 2 13 3 3
323 10 3 10 7 5 9 1 7 3 4 4 3 2 0 0
324
325
326 15
327 1 1 1 2 1 5 5 6 4 2 5 4 5 12 3
328 9 9 10 10 9 2 1 5 6 4 2 3 2 1 0
329
330
331 15
332 0 1 1 0 1 1 6 7 5 4 3 4 10 1 13
333 1 9 12 2 10 2 1 4 2 2 2 3 1 0 0
334
335
336 15
337 1 1 1 0 3 3 6 7 0 8 4 1 1 8 2
338 6 13 5 3 10 3 5 3 3 1 0 2 0 0 0
339
340
341 15
342 1 1 3 1 3 4 0 5 3 7 6 6 4 4 4
343 9 10 10 4 3 2 8 7 2 0 2 3 0 0 0
344
345
346 15
347 1 1 2 4 0 5 5 1 5 2 6 8 1 12 7
348 0 12 10 10 6 0 1 5 0 0 3 3 0 0 0
349
350
351
352 **/
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define LL long long
4 #define ULL unsigned long long
5
6 const LL mod_1=1e9+7;
7 const LL mod_2=998244353;
8
9 const double eps_1=1e-5;
10 const double eps_2=1e-10;
11
12 const int maxn=2e5+10;
13
14 void work()
15 {
16 int n=15; ///5 20 50
17 //int n=3e5;
18 int i;
19 printf("%d\n",n);
20 for (i=1;i<=n;i++)
21 printf("%d ", rand()%(i+1) );
22 printf("\n");
23 for (i=1;i<=n;i++)
24 printf("%d ", rand()%(n-i+1) );
25 }
26
27 int main()
28 {
29 //work();
30 srand(time(NULL));
31
32 int times=10;
33 while (times--)
34 {
35 work();
36 printf("\n\n\n");
37 }
38
39 return 0;
40 }
41 /*
42 5
43 0 2 1 4 1
44 2 0 0 1 0
45
46
47 5
48 1 2 3 1 0
49 2 2 1 0 0
50
51
52 5
53 1 2 0 0 5
54 0 2 1 0 0
55
56
57 5
58 1 2 2 1 4
59 1 0 0 1 0
60 */
标签：10,751,1601B,15,cf,12,maxn,const,include From： https://www.cnblogs.com/cmyg/p/18157262