2023-12 · 6级 · 工作沟通

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 1582 字

CCF 原卷官方标程 · 数组与向量、字符串、STL、搜索 · 本地编译通过

2023-12
数组与向量

正文

// GESP 2023-12 C++ 6级 编程题 2 · 工作沟通
// 原题：https://oj.yecheng.tv/p/gs2312l6p2
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1584918408724512.pdf
// 题意：某公司有名员工，编号从至 。
// 知识点：数组与向量、字符串、STL、搜索
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：样例验证 2/2 通过
//
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int N = 305;
int fa[N], dep[N];
bool vis[N];
vector<int> ch[N];
int getdep(int x) {
    return x == 0 ? 0 : getdep(fa[x]) + 1;
}
void dfs(int x) {
    vis[x] = 1;
    for (int y : ch[x])
        dfs(y);
}
bool check(int x, int n, const vector<int> &vec) {
    for(int i = 0; i <= n; i ++)
        vis[i] = 0;
    dfs(x);
    for (int y : vec)
        if(! vis[y])
            return 0;
    return 1;
}
int main() {
    // freopen("data/1.in", "r", stdin);
    // freopen("tmp.txt", "w", stdout);
    int n;
    scanf("%d", &n);
    for(int i = 1; i < n; i ++) {
        scanf("%d", &fa[i]);
        ch[fa[i]].push_back(i);
    }
    for(int i = 1; i < n; i ++)
        dep[i] = getdep(i);
    int q;
    scanf("%d", &q);
    while(q --) {
        int m, mnd = n + 1;
        scanf("%d", &m);
        vector<int> vec(m);
        for(int i = 0; i < m; i ++) {
            scanf("%d", &vec[i]);
            mnd = min(mnd, dep[vec[i]]);
        }
        for (int i = n - 1; i >= 0; i --)
            if (dep[i] <= mnd && check(i, n, vec)) {
                printf("%d\n", i);
                break ;
            }
    }
    return 0;
}

2023-12 · 6级 · 工作沟通

正文

GESP 标程 · 考级真题的其它内容