更多PAT甲级题解尽在我的个人博客--acking-you.github.io

题目


OJ平台

题目大意

这题看了描述后，大概就能清楚题目是这么个意思：

  • 输入： 输入N个人，并给出这N个人的关注列表。以及层级限制 L 和 K 次询问。
  • 输出： K次询问，每次询问第 i 个人发博客后，在它树形关注图 L 层级内最多有多少人收到这个博客通知？

把题目往这一摆，很快发现，这个题目就是一个普通的BFS，只不过建图的时候需要注意：输入给出的是每个人的关注列表，我们需要根据关注列表得出每个人被哪些人关注了。

代码拆解

输入处理

int N, L; //给出的用户数\可以间接转发的树的高度
vector<int> node[1001]; //形成树形结构--存储每个用户被关注哪些用户所关注
vector<int> question;   //存储问题

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> N >> L;
    for (int i = 1; i <= N; i++) {
        int t;
        cin >> t;
        while (t--) { //这个由于是输入的每个人的关注列表，需要转换为某个人被关注列表
            int val;
            cin >> val;
            node[val].push_back(i); //更新每个树的子节点
        }
    }
    int c;
    cin >> c;
    while (c--) { //输入询问的问题，其实也可以在这里打印，只不过会让单个程序变得复杂
        int val;
        cin >> val;
        question.push_back(val);
    }
}

输出处理

//@bfs获取每次询问的答案
int get_res(int n) {
    bitset<1001> check(0);  //用于防止重复计数
    check[n] = 1;          //不能自己给自己转发
    queue<int> Q;         //用于BFS层序遍历
    Q.push(n);
    int res = 0, step = 0;
    while (!Q.empty() && step < L) {
        for (int i = Q.size(); i > 0; i--) {
            int t = Q.front();
            Q.pop();
            for (auto &&tt:node[t]) {
                if (!check[tt]) {
                    res++;
                    Q.push(tt);
                    check[tt] = 1;
                }
            }
        }
        step++;
    }
    return res;
}
//@打印答案
void print() {
    int sz = question.size();
    for (int i = 0; i < sz; i++) {
        if (i != sz - 1) {
            cout << get_res(question[i]) << '\n';
        } else {
            cout << get_res(question[i]);
        }
    }
}

整合代码得出答案

效率应该在这题来说是数一数二了(还能通过直接在输入阶段打印结果提升效率的。

#include<bits/stdc++.h>
using namespace std;
int N, L; //给出的用户数\可以间接转发的树的高度
vector<int> node[1001]; //形成树形结构--存储每个用户被关注哪些用户所关注
vector<int> question;   //存储问题

//@输入处理
void Input() {
    ios::sync_with_stdio(false);
    cin >> N >> L;
    for (int i = 1; i <= N; i++) {
        int t;
        cin >> t;
        while (t--) { //这个由于是输入的每个人的关注列表，需要转换为某个人被关注列表
            int val;
            cin >> val;
            node[val].push_back(i); //更新每个树的子节点
        }
    }
    int c;
    cin >> c;
    while (c--) { //输入询问的问题，其实也可以在这里打印，只不过会让单个程序变得复杂
        int val;
        cin >> val;
        question.push_back(val);
    }
}

//@bfs获取每次询问的答案
int get_res(int n) {
    bitset<1001> check(0);  //用于防止重复计数
    check[n] = 1;              //不能自己给自己转发
    queue<int> Q;            //用于BFS层序遍历
    Q.push(n);
    int res = 0, step = 0;
    while (!Q.empty() && step < L) {
        for (int i = Q.size(); i > 0; i--) {
            int t = Q.front();
            Q.pop();
            for (auto &&tt:node[t]) {
                if (!check[tt]) {
                    res++;
                    Q.push(tt);
                    check[tt] = 1;
                }
            }
        }
        step++;
    }
    return res;
}
//@打印答案
void print() {
    int sz = question.size();
    for (int i = 0; i < sz; i++) {
        if (i != sz - 1) {
            cout << get_res(question[i]) << '\n';
        } else {
            cout << get_res(question[i]);
        }
    }
}

int main() {
    Input();
    print();
    return 0;
}