判断是否为连乘数字串
序号：#32难度：非常难时间限制：1000ms内存限制：10M
描述
给出一个字符串S，判断S是否为连乘字符串。 连乘字符串定义为： 字符串拆分成若干数字，后面的数字（从第三个数字开始）为前面2个数字的乘积。 例如： 122，可以拆成{1|2|2}，有12=2 1122242，可以拆成{11|22|242}，有1122=242 1224832256，可以拆成{1|2|2|4|8|32|256}，有12=2，22=4，24=8，48=32，8*32=256。
若是连乘字符串，则输出true，否则输出false。(PS:不考虑乘以0)
输入
一个正整数字符串
输出
字符串true或者false，表示是否可以拆成连乘数字。
输入样例
122 113 1122242
复制样例
输出样例
true false true
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long ll;
ll num(int l,int r,string s)
{
ll res=0;
int len=r-l+1;
ll tmp=1;
for(int i=r;i>=l;i--)
{
res+=(s[i]-'0')*tmp;
tmp*=10;
}
return res;
}
bool ok2(ll a,ll b,string s)
{
ll next=a*b;
string tmp=std::to_string(next);
if(s.size()<tmp.size())return false;
if(s.size()==tmp.size())
{
return s==tmp;
}
if(s.size()>tmp.size())
{
int len=tmp.size();
for(int i=0;i<len;i++)if(s[i]!=tmp[i])return false;
string sub_s="";
for(int i=len;i<s.size();i++)sub_s+=s[i];
return ok2(b,next,sub_s);
}
}
bool ok(string s)
{
int len=s.size();
bool f=0;
for(int i=0;i<len;i++)
{
for(int j=i+1;j<len;j++)
{
ll a=num(0,i,s);
ll b=num(i+1,j,s);
string sub_s="";
for(int t=j+1;t<len;t++)sub_s+=s[t];
if(ok2(a,b,sub_s)){f=1;break;}
}
if(f)break;
}
return f;
}
bool judge(string s)
{
return ok(s);
}
int main()
{
// freopen("in.txt","r",stdin);
string ss;
while(cin>>ss)
{
cout<<(judge(ss)?"true":"false")<<endl;
}
return 0;
}