L2-026. 小字辈

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：

输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：

首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：

9

2 6 5 5 -1 5 6 4 7

输出样例：

4

1 9

终于AC了，一波三折啊。

比赛的时候用队列+set 水到15分，回来自己按照比赛的思路敲了下16分。下面是代码：

//Asimple

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn =  + ;

int n, m, res, ans, len, T, k, num, sum, t, cnt;

bool vis[maxn];

struct node{

    int fa;

};

node a[maxn];

void input() {

    ios_base::sync_with_stdio(false);

    cin >> n;

    queue<int> q;

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

        cin >> num;

        a[i].fa = num;

        if( num == - ) {

            q.push(i);

            vis[i] = true;

        } else vis[i] = false;

    }

    set<int> S;

    int cas = ;

    while( !q.empty() ) {

        S.clear();

        while( !q.empty() ) {

            S.insert(q.front());

            q.pop();

        }

        cas ++;

        for(int i=; i<=n; i++) if( !vis[i] ) {

            if( S.count(a[i].fa) ==  ) {

                q.push(i);

            }

        }

    }

    cout << cas << endl;

    bool f = true;

    set<int>::iterator it;

    for(it=S.begin(); it!=S.end(); it++) {

        if( f ) f = false;

        else cout << " ";

        cout << *it;

    }

    cout << endl;

}

int main(){

    input();

    return ;

}

emmmm，然后想了下是不是set的原因时间超限，然后直接用vector保存各个辈分的人。然后15分。。。╮(╯▽╰)╭ 代码：

//Asimple

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn =  + ;

int n, m, res, ans, len, T, k, num, sum, t, cnt;

struct node{

    int fa;

};

node a[maxn];

vector<int> re[maxn];

void input() {

    ios_base::sync_with_stdio(false);

    cin >> n;

    queue<int> q;

    len = ;

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

        cin >> num;

        a[i].fa = num;

        if( num == - ) {

            q.push(i);

            re[len].push_back(i);

        }

    }

    while( !q.empty() ) {

        len ++;

        int T = q.size();

        while( T -- ) {

            int now = q.front(); q.pop();

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

                if( a[i].fa == now ) {

                    q.push(i);

                    re[len].push_back(i);

                }

            }

        }

    }

    cout << len << endl;

    for(int i=; i<re[len-].size(); i++) {

        if( i!=  ) cout << " ";

        cout << re[len-][i];

    }

    cout << endl;

}

int main(){

    input();

    return ;

}

仔细看了下代码，发现自己的BFS每次都要从1循环到n，emmmm，好像挺浪费时间的，不如把关系也用vector存吧，至少每次不用循环那么多次。一交20分。

好像去年有道题目也是被vector坑了，今天还是没有想到vector。真的傻啊。

20分代码：

//Asimple

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn =  + ;

int n, m, res, ans, len, T, k, num, sum, t, cnt;

vector<int> a[maxn];

vector<int> re[maxn];

void input() {

    ios_base::sync_with_stdio(false);

    cin >> n;

    queue<int> q;

    len = ;

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

        cin >> num;

        a[num].push_back(i);

        if( num == - ) {

            q.push(i);

            re[len].push_back(i);

        }

    }

    while( !q.empty() ) {

        len ++;

        int T = q.size();

        while( T -- ) {

            int now = q.front(); q.pop();

            for(int i=; i<a[now].size(); i++) {

                q.push(a[now][i]);

                re[len].push_back(a[now][i]);

            }

        }

    }

    cout << len << endl;

    for(int i=; i<re[len-].size(); i++) {

        if( i !=  ) cout << " ";

        cout << re[len-][i];

    }

    cout << endl;

}

int main(){

    input();

    return ;

}

巴特西

L2-026. 小字辈

最新文章

热门文章