题目链接
题目大意
给你一个十进制数s 你需要将他分成n块 使这n块加起来和等于s
并且这n块加起来的十一进制数最大
题目思路
让十一进制和最大
就要满足在最高位的数字和尽可能地多
易知 当每一位的数字和大于n时不需要考虑上述情况 可以很容易的得到答案
但当每一位数字和小于n时 则需要考虑将某一个位上的数字拆分成小于该位的数量更多的数字
例如100为满足数量的限制就要拆分为10和90
100若要拆分为11项就可分为 90 和十个1
一开始我想的是对于从小至大的每一位进行拆分 后来发现太过复杂难以实现
经过该大佬的点拨之后发现 可以将s加到一个动态数组里面 每次拆分就进行一次更新数组
最后判断数组数量就可得答案 其实很多数据规模不是大数的类似的数学模拟题都可以用类似的思想去解决 这样去做就不需要考虑譬如一百到底是要分成三十份还是分成三份的情况了
详情请见代码
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
int t,n,s;
int a[maxn];
ll quickpow(ll a,ll b)
{ll ans=1;while(b>0){if(b&1){ans*=a;//ans%=mod1;}a*=a;//使用自乘来快速幂。//a%=mod1;b>>=1;}return ans;
}
bool check(int x)//判断是否可分
{int cnt=0;int mx=0;while(x){cnt+=(x%10>0);mx=max(mx,x%10);x/=10;}return cnt>=2||mx!=1;
}
int len(int x)
{int res=0;while(x){res++;x/=10;}return res;
}
int main()
{cin>>t;while(t--){cin>>s>>n;vector<int >v;v.push_back(s);while(v.size()<n){int flag=1;for(int i=0;i<v.size();i++){int ma=v[i];if(check(ma)){flag=0;v.erase(v.begin()+i);int mx=quickpow(10,len(ma)-1);v.push_back(mx);v.push_back(ma-mx);break;}} if(flag){int mi=1e9;int id=0;for(int i=0;i<v.size();i++){int now=v[i];if(mi>v[i]&&v[i]!=1){mi=v[i];id=i;}}v.erase(v.begin()+id);int mx=quickpow(10,len(mi)-2);v.push_back(mi-mx);v.push_back(mx); }}for(int i=0;i<v.size();i++){cout<<v[i]<<" ";}cout<<endl;}return 0;
}