当前位置:网站首页>PAT 甲级 1103 Integer Factorizatio
PAT 甲级 1103 Integer Factorizatio
2022-07-07 12:54:00 【柘木木】
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,⋯,aK } is said to be larger than { b1,b2,⋯,bK } if there exists 1≤L≤K such that ai=bi for i<L and aL>bL.
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
题意:给169(N)作因式分解,分解成5(K)项,每个因式可以选多次,最后输出选择的因式的2(p)次方(递减顺序,且要保证该序列的序列和是所有解里面最大的)
n,p,k依据题目输入
思路:联想到完全背包问题,即一个物品可以被选择多次,每个物品有选和不选两种情况,所以就有项数联想到背包物品,数n联想到背包容量,序列和最大联想到背包最大价值,因此可以写出完全背包的深度优先搜索模型
//因为是先选,嵌套一次就选一次,这样就可以体现出完全背包问题了;
temp.push_back( );//先选;
DFS(index,sum,facsum);//选择的情况;
temp.pop_back( )//选择的情况结束;
DFS(index-1,sum,facsum);//这一项不选,进入下一项的判断;
代码:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,k,p;//数,有n项数,p次方;
int maxfac=-1;//用于判断是否有最优解,最优解是什么;
vector<int > fac,temp,ans;//放置预处理的平方和,临时的答案序列,最终的答案序列;
int power(int x){//算数的p次方;
int ans=1;
for(int i=0;i<p;i++){
ans*=x;//求x的p次方,乘多少次就是多少次方嘛;
}
return ans;
}
void deal( ){//预处理平方和到fac里面;
int temp=0,i=0;
while(temp<=n){
fac.push_back(temp);
temp=power(++i);
}
}
//当前处理到index项,现在已选入nowk个数,此时的选的数的p次方的和,因式和(用于判断该解的因式是不是最大的);
void DFS(int index,int nowk,int sum,int sumfac){
if(sum==n&&nowk==k){//进来先判断临界条件;
if(maxfac<sumfac){//目前是最优序列;
ans=temp;//vector数组可以直接替换;
maxfac=sumfac;//更新最大值;
}
return ;
}
if(sum>n||nowk>k)return ;//修叶;
if(index-1>=0){//fas[0]不用选择;
temp.push_back(index);//先选;
DFS(index,nowk+1,sum+fac[index],sumfac+index);//选进去了看看还能不能选;
temp.pop_back();//不能再选了或者不满足条件不选;
DFS(index-1,nowk,sum,sumfac);//进入其他分支判断;
}
}
int main( ){
scanf("%d %d %d",&n,&k,&p);
deal( );//预处理,将各项的p次方算出来;
DFS(fac.size()-1,0,0,0);//一定不要忘记使用深度优先搜索找到最优解,即不要忘了调用函数;
if(maxfac==-1) printf("Impossible");
else
for(int i=0;i<ans.size();i++) i==0?printf("%d = %d^%d",n,ans[i],p):printf(" + %d^%d",ans[i],p);
return 0;
}
无注释代码:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,k,p;
int maxfac=-1;
vector<int > fac,temp,ans;
int power(int x){
int ans=1;
for(int i=0;i<p;i++){
ans*=x;
}
return ans;
}
void deal( ){
int temp=0,i=0;
while(temp<=n){
fac.push_back(temp);
temp=power(++i);
}
}
void DFS(int index,int nowk,int sum,int sumfac){
if(sum==n&&nowk==k){
if(maxfac<sumfac){
ans=temp;
maxfac=sumfac;
}
return ;
}
if(sum>n||nowk>k)return ;
if(index-1>=0){
temp.push_back(index);
DFS(index,nowk+1,sum+fac[index],sumfac+index);
temp.pop_back();
DFS(index-1,nowk,sum,sumfac);
}
}
int main( ){
scanf("%d %d %d",&n,&k,&p);
deal( );
DFS(fac.size()-1,0,0,0);
if(maxfac==-1) printf("Impossible");
else
for(int i=0;i<ans.size();i++) i==0?printf("%d = %d^%d",n,ans[i],p):printf(" + %d^%d",ans[i],p);
return 0;
}
边栏推荐
猜你喜欢
安恒堡垒机如何启用Radius双因素/双因子(2FA)身份认证
[today in history] July 7: release of C; Chrome OS came out; "Legend of swordsman" issued
⼀个对象从加载到JVM,再到被GC清除,都经历了什么过程?
Ctfshow, information collection: web2
Niuke real problem programming - day13
Huawei cloud database DDS products are deeply enabled
Change win10 Screensaver
MicTR01 Tester 振弦采集模塊開發套件使用說明
Navigation - are you sure you want to take a look at such an easy-to-use navigation framework?
EfficientNet模型的完整细节
随机推荐
PAG体验:十分钟完成AE动效部署上线各平台!
Discussion on CPU and chiplet Technology
JS image to Base64
ES日志报错赏析-maximum shards open
Ctfshow, information collection: web4
C# 6.0 语言规范获批
Ctfshow, information collection: web5
Pytorch model trains practical skills and breaks through the bottleneck of speed
Ascend 910 realizes tensorflow1.15 to realize the Minist handwritten digit recognition of lenet network
Full details of efficientnet model
Why do we use UTF-8 encoding?
Cocos creator direction and angle conversion
Niuke real problem programming - Day17
PyTorch模型训练实战技巧,突破速度瓶颈
How bad can a programmer be? Nima, they are all talents
Half an hour of hands-on practice of "live broadcast Lianmai construction", college students' resume of technical posts plus points get!
PD virtual machine tutorial: how to set the available shortcut keys in the parallelsdesktop virtual machine?
[today in history] July 7: release of C; Chrome OS came out; "Legend of swordsman" issued
在软件工程领域,搞科研的这十年!
Instructions d'utilisation de la trousse de développement du module d'acquisition d'accord du testeur mictr01