Codeforces Round #605 (Div. 3) E - Nearest Opposite Parity

题目链接：http://codeforces.com/contest/1272/problem/E

题意：给定n，给定n个数a[i]，对每个数输出d[i]。

对于每个i，可以移动到i+a[i]和i-a[i]（如果i+a[i]<=n，i-a[i]>=1）

d[i]是指从i移动到任意一个j的步数，需满足条件a[i]和a[j]的奇偶性不同

不论奇偶，相连的边先放进vector邻接表中

如果i和i+a[i]奇偶性不同，那么ans[i]为1，把i放到queue队列里

同理，如果i和i-a[i]奇偶性不同，那么ans[i]为1，把i放到queue队列里

（bfs）

queue队列里存的是每个有答案的点，刚开始队列里所有点的ans都为1。

由于需要a[i]和a[j]奇偶性不同，则只需要跟有答案的点奇偶性相同即可。

#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+;

vector<int> v[maxn];

int ans[maxn],a[maxn];

int main()

{

    memset(ans,-,sizeof ans);

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)cin>>a[i];

    queue<int> q;

    for(int i=;i<=n;i++)

    {

        int j=i+a[i];

        if(j<=n)

        {

            v[j].push_back(i);

            if(a[j]%!=a[i]%)

            {

                ans[i]=;

                q.push(i);

            }

        }

        j=i-a[i];

        if(j>=)

        {

            v[j].push_back(i);

            if(a[j]%!=a[i]%)

            {

                ans[i]=;

                q.push(i);

            }

        }

    }

    while(!q.empty())//bfs

    {

        int cur=q.front();

        q.pop();

        for(int n:v[cur])

        {

            if(ans[n]==-&&a[n]%==a[cur]%)

            {

                ans[n]=ans[cur]+;

                q.push(n);

            }

        }

    }

    for(int i=;i<=n;i++)

    {

        cout<<ans[i]<<" ";

    }

    return ;

}

巴特西

Codeforces Round #605 (Div. 3) E - Nearest Opposite Parity

最新文章

热门文章