### 1031 - CSP 2019 提高组第一轮第19题
```
三、完善程序(单选题,每小题3分,共计30分)
1. (匠人的自我修养)一个匠人决定要学习nn个新技术。要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最 多能学会多少个新技术。
输入第一行有两个数,分别为新技术个数 $n\ (1\le n\le 10^3)$
,以及己有经验值 $(\le 10^7)$。
接下来n行。第i行的两个正整数,分别表示学习第i个技术所需的最低经验值 $(\le 10^7)$,以及学会第i个技术后可获得的经验值 $(\le 10^7)$
接下来 $n$ 行。第 $i$ 行的第一个数 $m_i\ (0\le m_i<n)$,表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数,表示第 $i$ 个技术的相关技术编号。
输出最多能学会的新技术个数。
下面的程序以 $n^2$ 的时间复杂度完成这个问题,试补全程序。
```
by hh0592821 @ 2020-09-08 10:34:54
### 1031 - CSP 2019 提高组第一轮第15题
```
正实数构成的数字三角形排列形式如图所示。第一行的数为 $a_{1,1}$;第二行的数从左到右依次为 $a_{2,1},a_{2,2}$,第 $n$ 行的数为 $a_{n,1},a_{n,2},......,a_{n,n}$。从 $a_{1,1}$ 开始, 每一行的数 $a_{i,j}$ 只有两条边可以分别通向下一行的两个数 $a_{i+1,j}$ 和 $a_{i+1,j+1}$ 。用动态规划算法找出一条从 $a_{1,1}$ 向下通到 $a_{n,1},a_{n,2},......,a_{n,n}$ 中某个数的路径,使得该路径上的数之和最大。令 $C_{i,j}$ 是从 $a_{1,1}$ 到 $a_{i,j}$ 的路径上的数的最大和,并且 $C_{i,0}=C_{0,j}=0$,则 $C_{i,j}=$()。
A. $\max\{C_{i-1,j-1},C_{i-1,j}\}+A_{i,j}$
B. $C_{i-1,j-1}+C_{i-1,j}$
C. $\max\{C_{i-1,j-1},C_{i-1,j}\}+1$
D. $\max\{C_{i,j-1},C_{i-1,j}\}+A_{i,j}$
```
by hh0592821 @ 2020-09-08 10:37:17
[1017 - NOIP 2015 普及组初赛试题](https://ti.luogu.com.cn/problemset/1017) 第 27 题 第二小题
错误答案:
(offset + dayNum[i]) % 7 / dayNum[m]
应改为:
(offset + dayNum[i]) % 7
by hh0592821 @ 2020-09-08 11:31:30
[1012 - NOIP 2012 提高组初赛试题](https://ti.luogu.com.cn/problemset/1012/training) 第 25 题
```
\```
#include <iostream>
using namespace std;
const int SIZE = 20;
int data[SIZE];
int n, i, h, ans;
void merge()
{
data[h-1] = data[h-1] + data[h];
h--;
ans++;
}
int main()
{
cin>>n;
h = 1;
data[h] = 1;
ans = 0;
for (i = 2; i <= n; i++)
{
h++;
data[h] = 1;
while (h > 1 && data[h] == data[h-1])
merge();
}
cout<<ans<<endl;
}
\```
(1)
输入:8
输出:_________
(2)
输入:2012
输出:_________
```
代码那加了 `\` 防止格式错乱。
by Implicit @ 2020-09-08 13:02:29
https://www.luogu.com.cn/discuss/show/235148
by songxiao @ 2020-09-08 21:55:47
www.luogu.com.cn/problem/P1828
样例图形(错误):
```
P2
P1 @--1--@ C1
|
|
5 7 3
|
| C3
C2 @--5--@
P3 P4
```
样例图形(正确):
```
P2
P1 @--1--@ C1
\ |\
\ | \
5 7 3
\ | \
\| \ C3
C2 @--5--@
P3 P4
```
by 小蓝伞 @ 2020-09-09 22:14:31
@[hh0592821](/user/96686) 第一个貌似有个地方 $LaTeX$ 错了
code:
```latex
三、完善程序(单选题,每小题3分,共计30分)
1. (匠人的自我修养)一个匠人决定要学习 $n$ 个新技术。要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最 多能学会多少个新技术。
输入第一行有两个数,分别为新技术个数 $n\ (1\le n\le 10^3)$
,以及己有经验值 $(\le 10^7)$。
接下来n行。第i行的两个正整数,分别表示学习第i个技术所需的最低经验值 $(\le 10^7)$,以及学会第i个技术后可获得的经验值 $(\le 10^7)$
接下来 $n$ 行。第 $i$ 行的第一个数 $m_i\ (0\le m_i<n)$,表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数,表示第 $i$ 个技术的相关技术编号。
输出最多能学会的新技术个数。
下面的程序以 $n^2$ 的时间复杂度完成这个问题,试补全程序。
```
by SteveFang @ 2020-09-10 06:10:28
@[小蓝伞](/user/92817) 本帖只解决有题的初赛题目题面问题,对于主站的题目请直接在题目附属讨论区反馈。
by hh0592821 @ 2020-09-10 10:50:38
第16题判断题第四题题面修改
原题面:
4) 当程序执行到第16行时,若ans - i> 2,则a[i + 1] < a[i]。 ()
新题面:
4) 当程序执行到第16行时,若ans - i> 2,则a[i + 1] <= a[i]。 ()
by Smile_Cindy @ 2020-09-10 18:19:51
上面说的是CSP 2019 提高组第一轮
by Smile_Cindy @ 2020-09-10 18:20:35