题目大意:给一个10^200000以内的数字,支持一种操作:在数字之间加若干个加号,把原数字变为加法运算后的结果,要求在三次操作内把数字变成个位数,输出方案。
做法:直观的想法是每两位之间都塞加号,事实证明这样并不一定最优,比如第一次操作后得到1399999,最后一次会得到13。我写了一个比较科学的玄学做法,因为如果这种贪心不够优,第一次得到的数各位和一定比较大,而得到的这个数再加上一些小数字各位和就容易变小,于是如果贪心不行,我就在第一次操作的时候随便把一些两位合并,然后再贪心,不知道能不能被hack,但应该挺科学的。
代码:
#include<cstdio>
#define MN 200000
char s[MN+];
int n,u[MN+];
bool solve()
{
int i,sm=,ss=,sss=,x,y,a[],an=,b[],bn=;
for(i=;i<=n;++i)if(u[i])sm+=(s[i]-'')*+s[i+]-'',++i;else sm+=s[i]-'';
for(x=sm;sm;sm/=)ss+=a[++an]=sm%;
for(y=ss;ss;ss/=)sss+=b[++bn]=ss%;
if(sss<)
{
for(i=;i<=n;++i)
{
if(i>)putchar('+');
putchar(s[i]);
if(u[i])putchar(s[++i]);
}
puts("");
for(i=an;i>;--i)printf("%d+",a[i]);printf("%d\n",a[]);
for(i=bn;i>;--i)printf("%d+",b[i]);printf("%d\n",b[]);
return false;
}
return true;
}
int main()
{
scanf("%d%s",&n,s+);
for(int i=;solve();)
{
for(;s[i]=='';++i);
u[i]=;i+=;
}
}