CCF GESP 2024年9月认证 C++ 6级
三
编程题
第 1 题
小杨和整数拆分
题目描述
小杨有一个正整数 $n$，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
编程计算总和为 $n$ 的完全平方数的最小数量。
输入格式
输入只有一行一个正整数 $n$。
输出格式
输出一行一个整数表示答案。
样例说明
样例 1
输入：
18
输出：
2
样例解释：
18 = 9+9 = 16+1+1，其中最少需要 2 个完全平方数。
数据范围
对于全部数据，保证有 $1 \leq n \leq 10^5$。
第 2 题
算法学习
题目描述
小杨计划学习 $m$ 种算法，为此他找了 $n$ 道题目来帮助自己学习，每道题目最多学习一次。
小杨对于 $m$ 种算法的初始掌握程度均为 $0$。第 $i$ 道题目有对应的知识点 $a_i$，即学习第 $i$ 道题目可以令小杨对第 $a_i$ 种算法的掌握程度提高 $b_i$。小杨的学习目标是对于 $m$ 种算法的掌握程度均至少为 $k$。
小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。
输入格式
第一行三个正整数 $m, n, k$，代表算法种类数，题目数和目标掌握程度。
第二行 $n$ 个正整数 $a_1, a_2, ..., a_n$，代表每道题目的知识点。
第三行 $n$ 个正整数 $b_1, b_2, ..., b_n$，代表每道题目提升的掌握程度。
输出格式
输出一个整数，代表小杨最少需要学习题目的数量，如果不存在满足条件的方案，输出 -1。
样例说明
样例 1
输入：
3 5 10
1 1 2 3 3
9 1 10 10 1
输出：
4
样例解释：
对于样例1，一种最优学习顺序为第一道题，第三道题，第四道题，第二道题。
样例 2
输入：
2 4 10
1 1 1 2
1 2 7 10
输出：
-1数据范围
对于全部数据，保证有 $1≤m,n,b_i,k≤10^5，1≤a_i≤m$。
编程题部分已到底了。