PAT (Advanced Level) Practice 1101~1120

1101

---

1102

---

1103 Integer Factorization

题意：
给定正整数 N、K、P，将 N 表示成 K 个正整数（可以相同且递减排列）的 P 次方的和，即 $N=n_1^P+...+n_k^P$。如果有多种方案，那么选择底数和 $n_1+\dots +n_k$ 最大的方案；如果还有多种方案，那么选择底数序列的字典序最大的方案。

思路：

1. 由于 $p>1$，因此可以定义一个 vector< int > fac，在输入 p 之后就预处理出所有不超过 n 的 $i^p$。为了使得下标与元素一 一对应，这里应把0也存进去。比如 n = 10, p = 2 时有 fac[0]=0、fac[1]=1、fac[2]=4、fac[3]=9；
2. 接下来思考 DFS 函数。DFS 函数从 fac 中选择若干个数（可以重复选），使得它们的和等于 n。对于 fac 中的每个数，根据选与不选来进入两个递归，因此 DFS 的参数中必须有：

当前处理到的是 fac 的几号位，也就是哪个底数数，不妨记为 index；
当前已经选择了几个底数，记为 nowK；
要使选出的数之和为 n，因此参数中需要记录当前选择出的数之和 sum；
为了保证有多个方案时底数之和最大，还需要在参数中记录当前选择出的数的底数之和 facSum；
还需要定义一个 vector< int > ans，用来存放最优的底数序列，而用一个 vector< int > temp 来存放当前选中的底数组成的临时序列；

3. 为了让结果能保证字典序大的序列优先被选中，让 index 从大到小递减来遍历，这样就总是能先选中 fac 中较大的数了；
4. 考虑递归本身。如果当前需要对 fac[index] 进行选择，那么就会有“选”与“不选”两种选择。

如果不选，就可以把问题转化为对fac[index - 1] 进行选择，此时nowK、sum、facSum 均不变，因此递归处理 DFS(index - 1, nowK, sum, facSum)；

如果选，由于每个数字可以重复选择，因此下一步还应当对 fac[index] 进行选择，但由于当前选了 fac[index]，需要把底数 index 加入当前序列 temp 中，同时让 nowK 加1、sum 加上 fac[index]、facSum 加上 index，因此递归处理 DFS(index, nowK+ 1, sum + fac[index ], facSum + index) 。

显然，DFS 必须在 index >= 1 时执行，因为题目求的是正整数的幂次之和。

5. 那么，递归边界是什么呢？首先，如果到了某个时候 sum == n 并且 nowK == k 成立，说明找到了一个满足条件的序列（就是temp，注意 temp 保存的是底数序列），此时为了处理多方案的情况，需要判断底数之和 facSum 是否比一个全局记录的最大底数之和 maxFacSum 更大，若是，则更新maxFacSum，并把 temp 赋给 ans。除此之外，当 sum > n 或者 nowK > k 时，不可能会产生答案，可以直接返回。

注意点：

• 多方案时判断是否更优的做法的时间复杂度最好是 O(1)，否则容易超时。因此必须在 DFS 的参数中记录当前底数之和 facSum，避免在找到一组解时计算序列的底数之和。
• 同上，不要在找到一组解时才判断 temp 序列与 ans 序列的字典序关系，而应该让 index 从大到小进行选择，这样 fac[index] 大的就会相对早地被选中。
• 对于 vector 容器 a 和 b，要使 a 中的元素替换为 b，只需要令 a = b 即可。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;int n, k, p, maxFacSum =-1; // n, k, p如题所述，maxFacSum 记录最大底数之和
// fac 记录 0^p, 1^p...i^p，使得 i^p 为不超过 n 的最大数
// ans 存放最大底数序列，temp 存在放递归中的临时底数序列
vector<int> fac, ans, temp;int power(int x) // power 函数计算 x^p
{
    int ans = 1;for (int i = 0; i < p; ++i)ans *= x;return ans;
}void init() // init 函数预处理 fac 数组，注意把0也存进去
{
    int i = 0, temp = 0;while (temp <= n) //当 i^p 没有超过 n 时，不断把 i^p 加入 fac{
    fac.push_back(temp);temp = power(++i);}
}// DFS 函数，当前访问 fac[index]，nowK 为当前选中数的个数
// sum 为当前选中的数之和, facSum 为当前选中的底数之和
void DFS(int index, int nowK, int sum, int facSum)
{
    if (sum == n && nowK == k) // 找到一个满足的序列{
    if (facSum > maxFacSum) // 底数之和更大{
    ans = temp; // 更新最优底数序列maxFacSum = facSum; // 更新最大底数之和}}if (sum > n || nowK > k)return; // 这种情况下不会产生答案，直接返回if (index - 1 >= 0) // fac[0] 不需要选择{
    temp.push_back(index); // 把底数 index 放入临时序列 tempDFS(index, nowK + 1, sum + fac[index], facSum + index); // 递归，选 indextemp.pop_back(); // 上面的递归结束后，把刚加进去的数弹出DFS(index - 1, nowK, sum, facSum); // 递归，不选 index}
}int main()
{
    scanf("%d%d%d", &n, &k, &p);init(); // 初始化数组 facDFS(fac.size() - 1, 0, 0, 0); // 从 fac 的最后一位开始往前搜索if (maxFacSum == -1)printf("Impossible\n"); // 没有找到满足的序列else{
    printf("%d = %d^%d", n, ans[0], p); // 输出 ans 的结果for (int i = 1; i < ans.size(); ++i)printf(" + %d^%d", ans[i], p);}return 0;
}

---

1104 Sum of Number Segments

一道纯考察数学规律的题目。

第 i 个数	a	b	c	d
在长度为1的片段中出现的次数	1	1	1	1
在长度为2的片段中出现的次数	1	2	2	1
在长度为3的片段中出现的次数	1	2	2	1
在长度为4的片段中出现的次数	1	1	1	1
总计出现次数	4	6	6	4

第 i 个数	a	b	c	d	e
在长度为1的片段中出现的次数	1	1	1	1	1
在长度为2的片段中出现的次数	1	2	2	2	1
在长度为3的片段中出现的次数	1	2	3	2	1
在长度为4的片段中出现的次数	1	2	2	2	1
在长度为5的片段中出现的次数	1	1	1	1	1
总计出现次数	5	8	9	8	5

第 i 个数	a	b	c	d	e	f
在长度为1的片段中出现的次数	1	1	1	1	1	1
在长度为2的片段中出现的次数	1	2	2	2	2	1
在长度为3的片段中出现的次数	1	2	3	3	2	1
在长度为4的片段中出现的次数	1	2	3	3	2	1
在长度为5的片段中出现的次数	1	2	2	2	2	1
在长度为6的片段中出现的次数	1	1	1	1	1	1
总计出现次数	6	10	12	12	10	6

第 i 个数	a	b	c	d	e	f	g
在长度为1的片段中出现的次数	1	1	1	1	1	1	1
在长度为2的片段中出现的次数	1	2	2	2	2	2	1
在长度为3的片段中出现的次数	1	2	3	3	3	2	1
在长度为4的片段中出现的次数	1	2	3	4	3	2	1
在长度为5的片段中出现的次数	1	2	3	3	3	2	1
在长度为6的片段中出现的次数	1	2	2	2	2	2	1
在长度为7的片段中出现的次数	1	1	1	1	1	1	1
总计出现次数	7	12	15	16	15	12	7

可以发现，如果当前是第 i 个数，那么其总的出现次数为 i * (n + 1 - i)。

注意点：

• ans 一定要用 long double 来定义，否则精度会不够，因为 v 的输入不一定是0.1，0.2这一类，有可能是尾数很长的小数，这样做乘法后误差会更大。此外 v 也建议用 long double 来定义。
• i 不要下意识的从0开始，而是从1开始，这一步卡了我十几分钟。

#include<cstdio>
using namespace std;int main()
{
    int n;long double v, ans = 0; // ans 必须要用 long double 型来定义，否则会导致测试点3错误scanf("%d", &n);for (int i = 1; i <= n; ++i){
    scanf("%llf", &v); // 第 i 位的值为 vans += v * i * (n + 1 - i); // 第 i 位的总出现次数为 v * i * (n + 1 - i)}printf("%.2llf\n", ans);return 0;
}

---

1105

---

1106

---

1107

---

1108

---

1109

---

1110

1111

---

1112

---

1113

---

1114

---

1115

---

1116

---

1117

---

1118

---

1119

---

1120

---

一定要自己写一遍哦~~