五月份做的吧 那个时候用了dp 死活过不了 后来听人说dp是可行的 但我还是不会，囧。。。这题用了比较快的广搜算法，用v[i][j][k]存储余数从i->j,去掉数字为k的情况，由于状态空间<1000，所以穷搜状态空间是可行的。这题具体来说可以分成三种情况：
1.字符串中既没有5也没有0，那么可以直接impossble掉
2.如果字符串中有5但是没有0，可以先去掉一个5，然后在穷搜，最后在末尾添加上。
3.其他情况，只要有0，末尾一定是0。
代码如下：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
struct node
{
int num[10];
int r;
}q[1010];
int getd(int num[])//统计这个大数的位数
{
int ans=0;
for(int i=0;i<10;i++)
{
ans+=num[i];
}
return ans;
}
int getsum(int num[])//统计这个大数每位之和
{
int ans=0;
for(int i=0;i<10;i++)
{
ans+=num[i]*i;
}
return ans;
}
int v[11][11][11];//hash判重
int num[10];//初始大数
int flagnum[10];
char s[2000];//字符串
int t;
bool haszero;//有0吗？
bool hasfive;//有5吗？
int ansnum[10];//最终结果，有中间处理，注意加0加5的情况
int ansflag;
int cmp(int ansnum[],int num[])
{
int len1=getd(ansnum);
int len2=getd(num);
//特别处理一下两个数是全0的情况
if(getsum(ansnum)==0&&getsum(num)==0)
return 0;
else if(getsum(ansnum)==0&&getsum(num)!=0)
return -1;
else if(getsum(ansnum)!=0&&getsum(num)==0)
return 1;
//end
if(len1>len2)
return 1;
else if(len1<len2)
return -1;
else
{
int i;
for(i=9;i>=1;i--)
{
if(ansnum[i]>num[i])
return 1;
else if(ansnum[i]<num[i])
return -1;
}
return 0;
}
}
void copy(int t[],int s[])//copy s里面的东西到t
{
int i;
for(i=0;i<=9;i++)
t[i]=s[i];
}
void input()//从1开始存储
{
ansflag=0;
hasfive=haszero=0;
scanf("%s",s+1);
memset(ansnum,0,sizeof(ansnum));
memset(num,0,sizeof(num));
memset(v,0,sizeof(v));
int i;
int len=strlen(s+1);
for(i=1;i<=len;i++)
{
int tt=(s[i]-'0');
num[tt]++;
if(tt==0)
haszero=1;
if(tt==5)
hasfive=1;
}
}
void output(int num[])//没有加回车,注意预先去掉的数字
{
for(int i=9;i>=0;i--)
{
if(num[i]!=0)
for(int j=1;j<=num[i];j++)
printf("%d",i);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
input();
if(!haszero&&!hasfive)
{
printf("impossible\n");
continue;
}
/**//*
if(haszero&&!hasfive)
{
int l,r;
l=r=1;
copy(q[1].num,num);
int tem=getsum(q[1].num);
tem%=9;
q[1].r=tem%9;
v[tem][tem][0]=1;
while(l<=r)
{
if(cmp(q[l].num,ansnum)==1&&q[l].r==0)
{
ansflag=1;
copy(ansnum,q[l].num);
}
for(int i=1;i<10;i++)
{
int nr=(q[l].r-i+9)%9;
if(q[l].num[i]>0&&v[q[l].r][nr][i]==0)
{
r++;
copy(q[r].num,q[l].num);
q[r].num[i]--;
q[r].r=nr;
v[q[l].r][nr][i]=1;
}
}
l++;
}
if(ansflag==1)
{
output(ansnum);
printf("\n");
}
else
printf("0\n");
}
*/
else if(!haszero&&hasfive)//没有0但是有5
{
int l,r;
l=r=1;
copy(q[1].num,num);
q[1].num[5]--;
int tem=getsum(q[1].num);
q[1].r=tem%9;
tem%=9;
v[tem][tem][0]=1;
while(l<=r)
{
if(cmp(q[l].num,ansnum)==1&&q[l].r==4)
{
ansflag=1;
copy(ansnum,q[l].num);
}
for(int i=1;i<10;i++)
{
/**//*
if(i==5)
{
__asm
{
int 3;
}
}
*/
int nr=(q[l].r-i+9)%9;
if(q[l].num[i]>0&&v[q[l].r][nr][i]==0)
{
r++;
copy(q[r].num,q[l].num);
q[r].num[i]--;
q[r].r=nr;
v[q[l].r][nr][i]=1;
}
}
l++;
}
if(ansflag==1)
{
output(ansnum);
printf("5\n");
}
else
printf("impossible\n");
}
else //没有0但是有5或者有0有5，情况相同
{
int l,r;
l=r=1;
copy(q[1].num,num);
int tem=getsum(q[1].num);
tem%=9;
q[1].r=tem%9;
v[tem][tem][0]=1;
while(l<=r)
{
if(cmp(q[l].num,ansnum)==1&&q[l].r==0)
{
ansflag=1;
copy(ansnum,q[l].num);
}
for(int i=1;i<10;i++)
{
int nr=(q[l].r-i+9)%9;
if(q[l].num[i]>0&&v[q[l].r][nr][i]==0)
{
r++;
copy(q[r].num,q[l].num);
q[r].num[i]--;
q[r].r=nr;
v[q[l].r][nr][i]=1;
}
}
l++;
}
if(ansflag==1)
{
output(ansnum);
printf("\n");
}
else
printf("0\n");
}
}
return 0;
}
代码写的比较长比较猥琐，不知道能把几个广搜合并下么。
感谢messidou神牛指点。