题库 信息学奥赛题库 题目列表 完善程序(单选题,每小题 3 分,共计 30 分)(匠人...
组合题

完善程序(单选题,每小题 3 分,共计 30 分)


(匠人的自我修养)

一个匠人决定要学习 n 个新技术。要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,

他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。


输入第一行有两个数,分别为新技术个数 n(l≤n≤103),以及己有经验值(≤107)。


接下来 n 行。第 i 行的两个正整数,分别表示学习第 i 个技术所需的最低经验值(≤107),以及学会第i个技术后可获得的经验值(≤107)


接下来 n 行。第 i 行的第一个数 

(0≤mi<n),表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数,表示第 i 个技术的相关技术编号。


输出最多能学会的新技术个数。


下面的程序以 O(n2) 的时间复杂度完成这个问题,试补全程序。


#include<cstdio>

using namespace std;

const int maxn = 1001;


int n;

int cnt[maxn];

int child [maxn][maxn];

int unlock[maxn];

int threshold[maxn], bonus[maxn];

int points;

bool find(){

    int target = -1;

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

        if(① && ②){

            target = i;

            break;

    }

    if(target == -1)

        return false;

    unlock[target] = -1;

    ③

    for (int i = 0; i < cnt[target]; ++i)

        ④

    return true;

}


int main(){

    scanf("%d%d", &n, &points);

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

        cnt[i] = 0;

        scanf("%d%d", &threshold[i], &bonus[i]);

    }

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

        int m;

        scanf("%d", &m);

        ⑤

        for (int j = 0; j < m; ++j){

            int fa;

            scanf("%d", &fa);

            child[fa][cnt[fa]] = i;

            ++cnt[fa];

        }

    }


    int ans = 0;

    while(find())

        ++ans;


    printf("%d\n", ans);

    return 0;

}

①处应填()


②处应填()


③处应填()


④处应填()


⑤处应填()

第1题 单选
A.

unlock[i] <= 0

B.

unlock[i] >= 0

C.

unlock[i] == 0

D.

unlock[i] == -1

第2题 单选
A.

threshold[i] > points

B.

threshold[i] >= points

C.

points > threshold[i]

D.

points >= threshold[i]

第3题 单选
A.

target = -1

B.

--cnt[target]

C.

bonus[target] = 0

D.

points += bonus[target]

第4题 单选
A.

cnt[child[target][i]] -= 1

B.

cnt[child[target][i]] = 0

C.

unlock[child[target][i]] -= 1

D.

unlock[child[target][i]] = 0

第5题 单选
A.

unlock[i] = cnt[i]

B.

unlock[i] = m

C.

unlock[i] = 0

D.

unlock[i] = -1

题目信息
2019年 初赛
-
正确率
0
评论
55
点击