PAT A1103 Integer Factorization ——如果你愿意一层一层一层的剥开我的心~

2023-12-27 03:10

本文主要是介绍PAT A1103 Integer Factorization ——如果你愿意一层一层一层的剥开我的心~,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

PAT A1103 Integer Factorization

  • 此题简单的描述不禁使我浮想联翩,质因数分解啦,几次方再求和怎么处理啦,遍历的范围和定位啦。。。最后终于步入正轨,应该先把N范围以内的K次方先放到数组里边备选,于是就变成了从一个有序数组中挑选M个数字使之总和=N(不是连续子序列有点可惜)。
  • 开始想用hash数组定位K次方数,从N开始倒着循环,搞到一半发现每个数都是可以取多次的,我这一个循环显然不行 ——感觉变成了完全背包了呦,可这个包我暂时还不会
  • 于是偷看了书上的,居然用的dfs。。。并且有理有据,使人信服。对于每个位置idx都有选和不选两种情况,if选,呢么idx放入序列数组,同时增加个数、次方总和与序列总和,并把问题仍然扔给当前的idx(因为选了她,所以下次仍由她来决定);if不选,先要把刚才push进去的吐出来(因为是逐层向下并且逐层返回的,所以dfs之后pop的就是dfs之前push的),然后直接把问题丢给前一个位置idx-1,因为没有放,所以那几个数据都不用增加,原包装转手,后面的事情由idx-1去处理
  • 最后一小点是Impossible并不能由vans.size()==0来判断,起码应该是!=M
  • 在这里插入图片描述
#include<iostream>
#include<vector>
#include<cmath>using namespace std;vector<int> v,vans,vtmp;
int max_fsum = -1;
int N,M,K;void dfs(int idx,int cnt,int sum,int facsum){if(cnt == M && sum == N){if(facsum > max_fsum){max_fsum = facsum;vans = vtmp;}return;}if(cnt > M || sum > N) return;if(idx >= 1){vtmp.push_back(idx);dfs(idx,cnt + 1,sum + v[idx],facsum + idx);vtmp.pop_back();dfs(idx - 1,cnt,sum,facsum);}
}int main(){scanf("%d %d %d",&N,&M,&K);int tmp = 0;for(int i = 1;tmp <= N;i ++){v.push_back(tmp);tmp = pow(i,K);} dfs(v.size() - 1,0,0,0);if(max_fsum == -1){printf("Impossible");return 0;} printf("%d = ",N);for(int i = 0;i < vans.size();i ++){printf("%d^%d",vans[i],K);if(i < vans.size() - 1) printf(" + ");}return 0;
}

这篇关于PAT A1103 Integer Factorization ——如果你愿意一层一层一层的剥开我的心~的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/541720

相关文章

为什么现在很多人愿意选择做债务重组?债重组真的就这么好吗?

债务重组,起初作为面向优质企业客户的定制化大额融资策略,以其高效周期著称,一个月便显成效。然而,随着时代的车轮滚滚向前,它已悄然转变为负债累累、深陷网贷泥潭者的救赎之道。在此路径下,个人可先借助专业机构暂代月供,经一段时间养护征信之后,转向银行获取低成本贷款,用以替换高昂网贷,实现利息减负与成本优化的双重目标。 尽管债务重组的代价不菲,远超传统贷款成本,但其吸引力依旧强劲,背后逻辑深刻。其一

PAT甲级-1044 Shopping in Mars

题目   题目大意 一串项链上有n个钻石,输入给出每个钻石的价格。用m元买一个连续的项链子串(子串长度可为1),如果不能恰好花掉m元,就要找到最小的大于m的子串,如果有重复就输出多个,按递增顺序输出子串的前端和后端索引。 原来的思路 取连续的子串使和恰等于m,没有恰等于就找最小的大于。可以将子串依次累加,使得每个位置都是起始位置到该位置的序列和,整个数组显递增顺序,就可以用右边减左边

PAT (Advanced Level) Practice——1011,1012

1011:  链接: 1011 World Cup Betting - PAT (Advanced Level) Practice (pintia.cn) 题意及解题思路: 简单来说就是给你3行数字,每一行都是按照W,T,L的顺序给出相应的赔率。我们需要找到每一行的W,T,L当中最大的一个数,累乘的结果再乘以0.65,按照例子写出表达式即可。 同时还需要记录每一次选择的是W,T还是L

翻译论文的关键部分 | Parallel Tiled QR Factorization for Multicore Architectures

SSRFB DTSQT2 DLARFB DGEQT2 1, 对角子矩阵分解 DGEQT2 这个例程被开发出来,用于针对对角Tile子矩阵: ,执行不分块的QR分解。 这个运算产生: 一个上三角矩阵 一个酉下三角矩阵,这个矩阵包含 b 个 Householder 反光面、 一个上三角矩阵 ,在WY技术中,这个矩阵被定义用来累计Householder变换。 和 能够写进 所占据的内存空间,

如何简便的将List<Integer>转换成int[]?

使用Java 8的流(Streams)  ArrayList<Integer> list = new ArrayList<>();int[] intArray = list.stream().mapToInt(Integer::intValue).toArray();  若是maven项目可使用Apache Commons Lang库 <dependency> <groupId>

[LeetCode] 7. Reverse Integer

题:https://leetcode.com/problems/reverse-integer/description/ 题目 Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123Output: 321Example 2:Input: -123Output: -321Ex

LeetCode - 12. Integer to Roman

12. Integer to Roman  Problem's Link  ---------------------------------------------------------------------------- Mean:  将一个int型的整数转化为罗马数字. analyse: 没什么好说的,直接维基百科. Time complexity: O(

带小数的String转整数Integer

其实String和Integer、Float、Double等相互转换这都很容易。可是带小数的String转Float、Double可能会出现“模糊数字”。 那么怎么避免呢?见下实例和结论。 System.out.println("**********2.4***********");String a = "2.4"; System.out.println(a); // 2.4System.o

Insertion Sort Integer Array Insertion Sort Linked List

Sort Integer Array using Insertion sort. //********************************************************************************************************/* Insertion Sort 原理:就是前面的sort部分全部是相对值,从后面拿一个元素,然后跟

Subtract the Product and Sum of Digits of an Integer

Given an integer number n, return the difference between the product of its digits and the sum of its digits. Example 1: Input: n = 234Output: 15 Explanation: Product of digits = 2 * 3 * 4 = 24