PTA甲级 1103 Integer Factorization (30分)

    科技2024-11-08  12

    文章目录

    题目原文Input Specification:Output Specification:Sample Input 1:Sample Output 1:Sample Input 2:Sample Output 2: 生词如下:题目大意:代码如下:核心代码(模板)柳神的代码: 强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬

    本文由参考于柳神博客写成

    柳神的博客,这个可以搜索文章

    柳神的个人博客,这个没有广告,但是不能搜索

    还有就是非常非常有用的 算法笔记 全名是

    算法笔记 上级训练实战指南 //这本都是PTA的题解 算法笔记

    PS 今天也要加油鸭

    题目原文

    The K−P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K and P.

    Input Specification:

    Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P (1<P≤7). The numbers in a line are separated by a space.

    Output Specification:

    For each case, if the solution exists, output in the format:

    N = n[1]^P + ... n[K]^P

    where n[i] (i = 1, …, K) is the i-th factor. All the factors must be printed in non-increasing order.

    Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122+42+22+22+12, or 112+62+22+22+22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen – sequence { a1,a2,⋯,a**K } is said to be larger than { b1,b2,⋯,b**K } if there exists 1≤L≤K such that a**i=b**i for i<L and a**L>b**L.

    If there is no solution, simple output Impossible.

    Sample Input 1:

    169 5 2

    Sample Output 1:

    169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

    Sample Input 2:

    169 167 3

    Sample Output 2:

    Impossible

    生词如下:

    PS:有事朦胧题,但是这题如果我不翻译的话,肯定是做不出来的.我只知道这题可以套模板,但是并不知道,这题的变量都是啥.

    Factorization 因子分解

    题目大意:

    给你一个数N 然后一个数K,一个数P

    要你吧N因数分解成K个数的p次方的和

    而且要求这K个数的和是最大的

    这是一道非常经典的DFS算法.

    我们采用的方法就是套用模板

    代码如下:

    #include<vector> #include<algorithm> #include<iostream> using namespace std; //n ,k,p如题所示,maxFacsum就是最大底数之和 int n, k, p, maxFacSum = -1; //fac记录0^p 1^p ..... i^p是的i^p为不超过n的最大数 //ans存放最优底数序列,temp存放递归中的临时底数序列 vector<int> fac, ans, temp; //power函数计算x^p int power(int x) { int ans = 1; for (int i = 0; i < p; ++i) { ans *= x; } return ans; } //init函数预处理fac数组,注意吧0也存进去. void init() { 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; } return; } if (sum > n || nowK > k) return; //这种情况下不会产生答案,直接返回 if (index - 1 >= 0) { //fac[0]不需要选择 temp.push_back(index); //把底数index加入临时序列temp DFS(index, nowK + 1, sum + fac[index], facSum + index); temp.pop_back(); DFS(index-1, nowK, sum, facSum);//不选的分支 } } int main(void) { scanf("%d%d%d", &n, &k, &p); init(); //初始化init数组 DFS(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; }

    核心代码(模板)

    void DFS(int index, int nowK, int sum, int facSum) { if (sum == n && nowK == k) { //找到一个满足的序列 if (facSum > maxFacSum) { //底数之和更优 ans = temp; //更新最优底数序列 maxFacSum = facSum; } return; } if (sum > n || nowK > k) return; //这种情况下不会产生答案,直接返回 if (index - 1 >= 0) { //fac[0]不需要选择 temp.push_back(index); //把底数index加入临时序列temp DFS(index, nowK + 1, sum + fac[index], facSum + index); temp.pop_back(); DFS(index-1, nowK, sum, facSum);//不选的分支 } }

    柳神的代码:

    #include <iostream> #include <vector> #include <cmath> using namespace std; int n, k, p, maxFacSum = -1; vector<int> v, ans, tempAns; void init() { int temp = 0, index = 1; while (temp <= n) { v.push_back(temp); temp = pow(index, p); index++; } } void dfs(int index, int tempSum, int tempK, int facSum) { if (tempK == k) { if (tempSum == n && facSum > maxFacSum) { ans = tempAns; maxFacSum = facSum; } return; } while(index >= 1) { if (tempSum + v[index] <= n) { tempAns[tempK] = index; dfs(index, tempSum + v[index], tempK + 1, facSum + index); } if (index == 1) return; index--; } } int main() { scanf("%d%d%d", &n, &k, &p); init(); tempAns.resize(k); dfs(v.size() - 1, 0, 0, 0); if (maxFacSum == -1) { printf("Impossible"); return 0; } printf("%d = ", n); for (int i = 0; i < ans.size(); i++) { if (i != 0) printf(" + "); printf("%d^%d", ans[i], p); } return 0; }
    Processed: 0.049, SQL: 8