青少年编程知识记录

2021年10月10日

【题解】找零钱—动态规划

给定一些人民币的面额，数量不限，要求找出金额为m元且人民币张数最少的方案。这个问题既可以是一个贪心问题也可以是一个动态规划的问题。对于现行的人民币面额：1、2、5、10、20、50、100，我们找任何金额的零钱都可以使用贪心法求解，比如找72元 = 50 + 20 + 2，3张人民币即可实现。但如果面额发生变化的话，则用贪心算法无法求出最优解，例如面额为1、3、6、7，要找12元的话只能是 12 = 7 + 3 + 1 + 1必须使用4张人民币，而最优解为12 = 6 + 6，两张人民币即可。

2021年10月10日

【算法】动态规划(三)——解题方法与解题思路

0.前言动态规划最核心的思想就是：拆分子问题，记住过往，减少重复计算。动态规划可以从下面的参考网上的一个例子：A ："1+1+1+1+1+1+1+1 =？" A ："上面等式的值是多少" B ：计算 "8" A : 在上面等式的左边写上 "1+" 呢？ A : "此时等式的值为多

2021年10月04日

【题解】2020-T1 优秀的拆分

【题目描述】一般来说，一个正整数可以拆分成若干个正整数的和。例如，1=1,10=1+2+3+4等。对于正整数n的一种特定拆分，当且仅当在这种拆分下，n被分解为若干个不同的2的正整数次幂。注意，一个数x能被表示成2的正整数次幂，当且仅当x能通过正整数个2相乘在一起得到。例如，10=8+2=23+21是一个优秀的拆分。但是，7=4+2+1=22+21+20 就不是一个优秀的拆分，因为1不是2的正整数次幂。现在，给定正整数n,你需要判断这个数的所有拆分中，是否存在优秀的拆分，若

2021年10月04日

组合数的写法

前面我们写过全排列和排列数等。这篇文章。我们写一下组合数。例题：从n个数中，选出m个，一共有多少种不同的选法？这是一道典型的组合数公式。我们直接用dfs公式肯定会出现重复的。#include<bits/stdc++.h> using namespace std; int n,m; int pd[100],ans[100];//pd数组是判断是否用过这个数，ans是结果数组 void print() {

2021年10月04日

【题解】2002-T2 选数

【题目描述】

已知

n

个整数x

x_{1}, x_{2}, \dots \dots x_{n}

,以及一个整数

K (K ＜ n)

。从

n

个整数中任选k个整数相加,可分别得到一系列的和。例如当

$n = 4$ , $k = 3$ , $4$ 个整数分别为3 $3, 7, 12, 19$ 时,可得全部的组合与它们的和为:

3+7+12=22　　 3+7+19=29　　 7+12+19=38　 3+12+19=34

现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:(3+7+19=29)。

【输入描述】

第一行为n和k(1≤n≤20,k＜n)

第二行为n个数 $x_{1} x_{2} \dots \dots x_{n} (1 \leq x_{i} \leq 5000000)$ ,各数之间用一个空格隔开)

【输出描述】

一个整数（满足所有条件的种数）

【样例输入】

4 3   3 7 12 19

【样例输出】

2021年10月04日

普及组CSP-J
序号	省市	CSP-J人数	CSP-J晋级	晋级比例	最高分	晋级最低分
1	甘肃	134	133	99.25%	86	15
2	宁夏	103	101	98.06%	65	24
3	天津	463	451	97.41%	86	15.5
4	云南	402	378	94.03%	79.5	17
5	湖北	680	632	92.94%	89.5	26
6	海南	186	170	91.40%	73.5	29
7	陕西	493	447	90.67%	93.5	28
8	广西	795	680	85.53%	86	28
9	山西	773	628	81.24%	95.5	30
10	贵州	447	331	74.05%	71	30
11	吉林	454	332	73.13%	91	33
12	河南	1114	798	71.63%	88.5	34.5
13	内蒙古	56	40	71.43%	58	34.5
14	黑龙江	354	205	57.91%	82	24.5
15	新疆	425	238	56.00%	81.5	39
16	江西	485	247	50.93%	86.6	36.5
17	辽宁	475	23	50.32%	90	40
18	湖南	1528	744	48.69%	93.5	15
19	香港	72	35	48.61%	100	45.5
20	河北	1122	518	46.17%	93.5	40
21	澳门	103	39	37.86%	82	31
22	重庆	1430	541	37.83%	94	51.5
23	上海	2841	1007	35.45%	94.5	52.5
24	安徽	4731	1558	32.93%	98.5	34
25	北京	3397	941	27.70%	96.5	53
26	四川	3028	704	23.25%	98.5	17
27	江苏	4172	737	17.67%	98.5	38
28	广东	5627	986	17.52%	95.5	58.5
29	浙江	6067	946	15.59%	98	66
30	山东	11450	1326	11.58%	98	15

山东普及组分数线55

小学组43