Codeforeces-1272E

Nearest Opposite Parity

题目大意：给你n（编号为：1，2，...，n）个点，每次我可以从编号为i的点移动到编号为i-a[i]的点。问

对于编号为i的点，是否能移动到j点，并使得a[i]和a[j]的奇偶性不同

解题思路：对于每个点，移动方向只有两个（题目中所说），因此我们可以建立一个有向图来处理这个问题。如果我们能从一个奇数顶点到一个偶数顶点，那我们我们也可以看作可以从这个偶数顶点到达这个奇数顶点

因此需要建立从i-a[i]到i的边通过编号为ide点移动到的点进行反向遍历，即可得出所需要的最小步数，后面操作两边bfs即可

链接：https://codeforces.com/contest/1272/problem/E

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int d[maxn],ans[maxn],a[maxn],aflag[maxn],n;
vector<int>q[maxn];
void bfs(int flag)
{
    memset(d,-1,sizeof(d));
    queue<int>v;  //1的话从奇数开始走
    if(flag==1)
    {
        for(int i=1;i<=n;i++)
        {
            if(a[i]%2)
            {
                v.push(i);
                d[i]=0;
            }
        }
    }
    else{
         for(int i=1;i<=n;i++)
        {
            if(a[i]%2==0)
            {
                v.push(i);
                d[i]=0;
            }
        }
    }
    while(!v.empty())
    {
        int u=v.front();
        v.pop();
        for(int i=0;i<q[u].size();i++)
        {
            int to=q[u][i];
            if(d[to]==-1)
            {
                v.push(to);
                d[to]=d[u]+1;
            }
        }
    }
    if(flag)
    {
    for(int i=1;i<=n;i++)
    {
        if(a[i]%2==0) ans[i]=d[i];
    }
    }
    else{

     for(int i=1;i<=n;i++)
    {
        if(a[i]%2==1) ans[i]=d[i];
    }

    }


}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        int l=i-a[i];
        int r=i+a[i];
        if(l>0) q[l].push_back(i);
        if(r<=n) q[r].push_back(i);
    }
    memset(ans,-1,sizeof(ans));
    bfs(1);
    bfs(0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}