题意:
给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,然后存进去
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
感觉思路好清晰,把它直接转换为图来搜,这种想法受教了