洛谷p1249最大乘积 题解

乘积 题解"/>

洛谷p1249最大乘积 题解

题目链接：tP1249 最大乘积 - 洛谷 | 计算机科学教育新生态 (luogu)

在第一眼看到这个题思考后除了暴力模拟没想到其他解法，但想了想暴力的话复杂度得炸。于是本蒟蒻本着借鉴他人思路的想法看了看题解，洛谷上这个题题解分析地很好，看完后也有了思路接下来就是代码实现。附上我的ac代码

#include<iostream>
#include<vector>
using namespace std;
vector<int> jc(vector<int>A,int b){vector<int>c;for(int i=0,t=0;i<A.size()||t;i++){if(i<A.size()) t+=A[i]*b;c.push_back(t%10);t/=10;}while(c.size()>1&&c.back()==0) c.pop_back();return c;
}
int main()
{int x,sum=0,arr[1010],i=2;for(int i=0;i<1010;i++) arr[i]=1;vector<int>A;A.push_back(1); cin>>x;for(;sum<x;i++){sum+=i;arr[i]=i;}if(sum-x==2){arr[2]-=1;}else if(sum-x==1){arr[i-1]+=1;arr[2]-=1;}else{arr[sum-x]-=sum-x-1;}if(x==3){cout<<"1 2"<<endl;cout<<"2";}else if(x==4){cout<<"1 3"<<endl;cout<<"3";}else{for(int i=1000;i>=1;i--){if(arr[i]!=1) A=jc(A,arr[i]);}for(int i=1;i<1000;i++) if(arr[i]!=1) cout<<arr[i]<<" ";cout<<endl;for(int i=A.size()-1;i>=0;i--) cout<<A[i];}return 0;
}

第一想法没想着把3和4单拎出来，交了以后发现有一组数据没过，就去试了试边界，发现果然是边界问题，输出的时候应该是包含1的，但在我的代码中时排1的，所以自然在3和4时会Wa，暂时没想到代码那块主体进行优化的思路，就把这两组数据单拎出来输出。

--------------------------------------------------------------------------------------------------

稍微优化了一下

#include<iostream>
#include<vector>
using namespace std;
vector<int> jc(vector<int>A,int b){vector<int>c;for(int i=0,t=0;i<A.size()||t;i++){if(i<A.size()) t+=A[i]*b;c.push_back(t%10);t/=10;}while(c.size()>1&&c.back()==0) c.pop_back();return c;
}
int main()
{int x,sum=0,arr[1010],i=2;for(int i=0;i<1010;i++) arr[i]=1;vector<int>A;A.push_back(1); cin>>x;for(;sum<x;i++) sum+=i,arr[i]=i;int mid=i;if(sum-x==2) arr[2]-=1;else if(sum-x==1) arr[i-1]+=1,arr[2]-=1;else arr[sum-x]-=sum-x-1;for(int i=mid;i>=2;i--) A=jc(A,arr[i]);if(x<5) cout<<"1 "<<x-1<<endl<<x-1;else{for(int i=2;i<mid;i++) if(arr[i]!=1) cout<<arr[i]<<" ";cout<<endl;for(int i=A.size()-1;i>=0;i--) cout<<A[i];}return 0;
}

看标签跟题解这个题还有贪心的想法，但我还没学到这块就先略过相关部分

---------------------------------------------------------------------------------------------------------------------------------

Tips:交题以前自己先测一下边界，养成良好习惯，白白给罚时还是很蠢的。