Codeforces Round #605 (Div. 3)E

题意:

给n长度的数组,a1,a2,a3,a4,a5…an,他可以实现跳跃从 ai 跳到a(i-ai)或者a(i+ai)这其中i-ai>=1  i+ai<=n

问如果他跳跃到的地方与他ai值的奇偶不同,就停止跳跃,比如 1 2 3,a1->a(1+1)=2就停止了,a2->a(2+2or2-2)都不符合所以没有跳,输出-1

其中跳不了和跳不到与ai奇偶不同的地方就输出-1

问每个位置需要最少跳几次。

思路

搜索,怎么搜呢,先找到一步就能跳到的点,ai%2!=aj%2同时i+ai==j或者i-ai==j这种。

然后这里就是看别人大佬的思路了,思路贼清晰,建一个ai%2==aj%2 && i+ai==j或者i-ai==j

前者建边是ai+i->i   后者是i-ai->i 的。为什么这样呢,这是从 一步就跳到的点 开始广搜。从最小步数往大步数搜。如果这个点之前没搜到过的点,就是bu+1,然后存进去

 

Codeforces Round #605 (Div. 3)E
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define ull unsigned long long
 5 #define il inline
 6 #define it register int
 7 #define inf 0x3f3f3f3f
 8 #define lowbit(x) (x)&(-x)
 9 #define pii pair<int,int>
10 #define mak(n,m) make_pair(n,m)
11 #define mem(a,b) memset(a,b,sizeof(a))
12 #define mod 998244353
13 const int maxn=2e5+10;
14 struct node{
15     int v,next;
16 }a[maxn<<1];
17 int cnt,head[maxn],n,m,t,aa[maxn];
18 il void add(int u,int v){
19     a[cnt].v=v;a[cnt].next=head[u];
20     head[u]=cnt++;
21 }
22 int bu[maxn];
23 queue<int>q;
24 int main(){
25     mem(head,-1);mem(bu,-1);
26     scanf("%d",&n);
27     for(it i=1;i<=n;i++){
28         scanf("%d",&aa[i]);
29     }
30     for(it i=1;i<=n;i++){
31         if(i-aa[i]>0 && aa[i]%2==aa[i-aa[i]]%2){
32             add(i-aa[i],i);
33         }
34         if(i+aa[i]<=n && aa[i]%2==aa[i+aa[i]]%2){
35             add(i+aa[i],i);
36         }
37     }
38     for(it i=1;i<=n;i++){
39         if(i-aa[i]>0 && aa[i]%2!=aa[i-aa[i]]%2 || i+aa[i]<=n && aa[i]%2!=aa[i+aa[i]]%2){
40             bu[i]=1;q.push(i);
41         }
42     }
43     while(!q.empty()){
44         int u=q.front();q.pop();
45         for(it i=head[u];~i;i=a[i].next){
46             int v=a[i].v;
47             if(bu[v]==-1 || bu[v]>bu[u]+1){
48                 bu[v]=bu[u]+1;q.push(v);
49             }
50         }
51     }
52     for(it i=1;i<=n;i++){
53         printf(i==n?"%d\n":"%d ",bu[i]);
54     }
55     return 0;
56 }
View Code

 

感觉思路好清晰,把它直接转换为图来搜,这种想法受教了

上一篇:605. 种花问题


下一篇:vue实现左右两列竖直分别滑动,且双向关联的选项卡