2019年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第1题）

2019年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第1题）

第1题（匠人的自我修养）

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

输入第一行有两个数，分别为新技术个数 n(l≤n≤

10

3

10^3

103)，以及己有经验值（≤

10

7

10^7

107）。

接下来 n行。第 i行的两个正整数，分别表示学习第 i个技术所需的最低经验值（≤

10

7

10^7

107），以及学会第 i个技术后可获得的经验值（≤

10

7

10^7

107）。

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

i

_i

i​（0≤

m

i

m_i

mi​<n），表示第 i个技术的相关技术数量。紧跟着 m个两两不同的数，表示第 i个技术的相关技术编号。

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

下面的程序以 O(

n

2

n^2

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;
}

答案及题解

该程序采用类似拓扑排序的思想，每次寻找一个满足前置条件和经验值要求的技术进行学习，并更新依赖关系和经验值，直到无法再学习为止。时间复杂度为 O(n²)。

• ①处应填 C. unlock[i] == 0，表示该技术的所有前置技术已学会（即未学习的依赖数为0），可以尝试学习。
• ②处应填 D. points >= threshold[i]，表示当前经验值足够学习该技术。
• ③处应填 D. points += bonus[target]，表示学会目标技术后增加经验值。
• ④处应填 C. unlock[child[target][i]] -= 1，表示将依赖该技术的所有技术的未学习前置数减1。
• ⑤处应填 B. unlock[i] = m，初始化每个技术的未学习前置数为它的相关技术数量。

专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}