题库 信息学奥赛题库 题目列表 (匠人的自我修养)一个匠人决定要学习n个新技术,要想...
组合题

(匠人的自我修养)一个匠人决定要学习n个新技术,要想成功学习一个新技术,他不仅要拥有一定的 经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的 值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个 新技术。

输入第一行有两个数,分别为新技术个数n(1≤n≤103),以及已有经验值(≤10^7). 接下来n行。第i行的两个整数,分别表示学习第i个技术所需的最低经验值(≤10^7),以及学会第i个技 术后可获得的经验值(≤10^4)。 接下来n行。第i行的第一个数mi(0≤mi<n),表示第i个技术的相关技术数量。紧跟着m个两两不同的 数,表示第i个技术的相关技术编号,输出最多能学会的新技术个数。

下面的程序已O(n^2)的时间复杂完成这个问题,试补全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;
 
int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int points;
int threshold[maxn], bonus[maxn];
 
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题 单选

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.

bbonus[target]

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
评论
134
点击