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

2019年信奥赛C提高组csp-s初赛真题及答案解析完善程序第1题第1题匠人的自我修养一个匠人决定要学习 n个新技术。要想成功学习一个新技术他不仅要拥有一定的经验值而且还必须要先学会若干个相关的技术。学会一个新技术之后他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值给定他已有的经验值请问他最多能学会多少个新技术。输入第一行有两个数分别为新技术个数 n(l≤n≤10 3 10^3103)以及己有经验值≤10 7 10^7107。接下来 n行。第 i行的两个正整数分别表示学习第 i个技术所需的最低经验值≤10 7 10^7107以及学会第 i个技术后可获得的经验值≤10 7 10^7107。接下来 n行。第 i行的第一个数 mi _ii​0≤m i m_imi​n表示第 i个技术的相关技术数量。紧跟着 m个两两不同的数表示第 i个技术的相关技术编号。输出最多能学会的新技术个数。下面的程序以 O(n 2 n^2n2) 的时间复杂度完成这个问题试补全程序。#includecstdiousingnamespacestd;constintmaxn1001;intn;intcnt[maxn];intchild[maxn][maxn];intunlock[maxn];intthreshold[maxn],bonus[maxn];intpoints;boolfind(){inttarget-1;for(inti1;in;i)if(①②){targeti;break;}if(target-1)returnfalse;unlock[target]-1;③for(inti0;icnt[target];i)④returntrue;}intmain(){scanf(%d%d,n,points);for(inti1;in;i){cnt[i]0;scanf(%d%d,threshold[i],bonus[i]);}for(inti1;in;i){intm;scanf(%d,m);⑤for(intj0;jm;j){intfa;scanf(%d,fa);child[fa][cnt[fa]]i;cnt[fa];}}intans0;while(find())ans;printf(%d\n,ans);return0;}①处应填A.unlock[i] 0B.unlock[i] 0C.unlock[i] 0D.unlock[i] -1②处应填A.threshold[i] pointsB.threshold[i] pointsC.points threshold[i]D.points threshold[i]③处应填A.target -1B.--cnt[target]C.bonus[target] 0D.points bonus[target]④处应填A.cnt[child[target][i]] - 1B.cnt[child[target][i]] 0C.unlock[child[target][i]] - 1D.unlock[child[target][i]] 0⑤处应填A.unlock[i] cnt[i]B.unlock[i] mC.unlock[i] 0D.unlock[i] -1答案及题解该程序采用类似拓扑排序的思想每次寻找一个满足前置条件和经验值要求的技术进行学习并更新依赖关系和经验值直到无法再学习为止。时间复杂度为 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各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html3、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}