1103. Integer Factorization (30)

题目:

https://www.patest.cn/contests/pat-a-practise/1103

大概描述:

将一个展开成k项,每一项的值都是某个数的p次方

特征词:

dfs

使用语言:

C++

解题思想:

深度优先遍历,每一层的寻找合适的数值,层层筛选

题目得分:

25

提交次数:

2

时间

120分钟

代码

#include<cstdio>
#include<vector>

using namespace std;

vector<int> m;//用于存储指数值
vector<int> mm;//用于存储条件
vector<int> limm;//每个最大e存储的临时数
vector<int> zmm;//最终结果
int n,k,p,indx,limax,zmax;
int pow1(int a,int b){
 int m = 1 ,i= 0;
 for(i = 0;i < b;i++){
 m *= a;
 }
 return m;
}
void init(){
 int j = 0;
 indx = 1;
 while(j < n){
 j = pow1(indx,p);
 indx ++;
 }
}

//找出最大为e,所剩下的次数,需要实现的值,是的最合适列表
void dsf(int e,int ci,int num){
 //printf("e = %d ci = %d num = %d",e,ci,num);
 int i= 0;
 //printf("现在临时表为:\n");
 int y = mm.size();
 for(i = 0;i < y;i++){
 // printf("%d ",mm[i]);
 }
// printf("\n");
 if(ci == 0 && num != 0){
 return ;
 }
 if(num <= 0 && ci != 0){
 return;
 }
 if(num == 0&&ci == 0){
 // printf("OOOOOOOOOOOOk\n");
 int sun = 0;
 for(i = 0;i < mm.size();i ++){
 sun += mm[i];
 }
 if(sun > limax){
 // printf("OOOOOOOOOOOOk\n");
 limax = sun;
 limm.clear();
 for(i = 0;i < mm.size();i++){
 limm.push_back(mm[i]);
 }
 }
 return;
 }
 int uu = pow1(e,p);
 // printf("ppppppppppppppowowowowow%d\n",pow1(e,p));
// printf("uuuuuuuuuuuuuuuuuuuuuu%d",uu);
 if(num - uu >= 0){
 // printf("装前我先瞧一瞧 e = %d,num =%d uu =%d\n",e,num,uu);
 mm.push_back(e);
 int j = 0;
 for(j = e ;j >= 1;j--){

 dsf(j,ci - 1,num - uu);
 }
 if(j == 0){
 mm.pop_back();
 }
 }
}

int main(){
 scanf("%d %d %d",&n,&k,&p);
 //printf("OOOOOOOOOk\n");
 init();//完成指数表的建立
 //printf("OOOOOOkk\n");
 int zs = 0;
 int u = 0;
 int i = 0;
 while(zs < n / k){
 u ++;
 zs = pow1(u,p);
 }
// printf("最小的头u = %d\n",u);
 zmax = -1;
 while(indx >= u){
 limax = -1;
 // printf("即将降入头为%d的深度遍历\n",indx);
 limm.clear();
 mm.clear();
 dsf(indx --,k,n);
 //printf("个头最强组合\n");
 int y = limm.size();
 for(i = 0;i < y;i++){
 //printf("%d ",limm[i]);
 }
 // printf("\n");
 if(limax > zmax){
 zmm.clear();
 int w = limm.size();
 for(i = 0;i < w;i++){
 zmm.push_back(limm[i]);
 }
 }
 if(limax == zmax){
 int w = limm.size();
 for(i = 0;i < w;i++){
 if(zmm[i] != limm[i]){
 if(zmm[i] < limm[i]){
 zmm.clear();
 int w = limm.size();
 for(i = 0;i < w;i++){
 zmm.push_back(limm[i]);
 }
 }
 break;
 }
 }
 }
 }
 //printf("Now i will give you answer\n");
int o = zmm.size();
 if(o != 0){
 printf("%d = ",n);

 for(i = 0;i < o;i++){
 printf("%d^%d",zmm[i],p);
 if(i != o -1)
 printf(" + ");
 }
 return 0;
 }
 /*if(169 == n&&k== 5 &&p == 2)
 printf("169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2");
else*/
printf("Impossible");


}

运行结果

25

 成长

做完这一题只想感叹,老衲,苦无心

首先最开始的思路,刚刚开始看到这题时,这题难道是,数学问题的那一类,感觉不简单,然后就没有思路,了,(;´д`)ゞ

后来查了一些资料,竟然是dfs,后来一想对呀,就是一层层的寻找,合适的值吗,思想还是要灵活些,得再练练,参悟其中得dfs的精髓

另外还学到了pop_back的使用,表示o(* ̄▽ ̄*)ブ

不过还一件比较悲伤的事,想偷偷的用一下,刚刚偷看到的pow函数,结果才发现这个函数就是个坑,他处理数据类型是浮点型的一类,而我一直用整形作为参数,这就是为什么会出现pow(10,2) = 99的原因。

老衲,只想说一句“路漫漫其修远兮,吾将上下而求索”,

真带劲

发表评论

电子邮件地址不会被公开。 必填项已用*标注