和整除45差不多，枚举后两位。复杂度应该是25*1000 ，但很奇怪跑了390MS...可能中间计算常数时间比较大。
再说几句，这题输出相当恶心啊，我挑了1个小时才大致理出输出的逻辑顺序，也许还不一定完全正确呢。这题还有优化的可能。
请各路神牛指点
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
struct node
{
int num[10];
int r;
}q[1010];
int dir[25][2]=
{
{0,0},
{0,4},
{0,8},
{1,2},
{1,6},
{2,0},
{2,4},
{2,8},
{3,2},
{3,6},
{4,0},
{4,4},
{4,8},
{5,2},
{5,6},
{6,0},
{6,4},
{6,8},
{7,2},
{7,6},
{8,0},
{8,4},
{8,8},
{9,2},
{8,6}
};
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 orinum[10];//初始大数
int num[10];
int flagnum[10];
char s[2000];//字符串
int t;
int ansnum[10];//最终结果，有中间处理，注意加0加5的情况
int ansflag;
int haszero;//有0吗
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 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);
}
}
bool check(int a,int b)//判断字符串中是否有a,b
{
int ma=0;
int len=strlen(s+1);
for(int i=1;i<=len;i++)
if(s[i]-'0'==a)
ma=i;
if(ma==0)
return false;
for(int i=1;i<=len;i++)
{
if(i==ma)
continue;
if(s[i]-'0'==b)
return true;
}
return false;
}
void zerozero()
{
int len=strlen(s+1);
for(int i=1;i<=len;i++)
if(s[i]-'0'==0)
{
haszero=1;
return;
}
haszero=0;
}
bool allzero()
{
int i;
for(i=1;i<10;i++)
if(ansnum[i]!=0)
return false;
return true;
}
int main()
{
int t;
scanf("%d",&t);
int ca=0;
while(t--)
{
ca++;
scanf("%s",s+1);
int last1=-1;
int last2=-1;
memset(ansnum,0,sizeof(ansnum));
memset(orinum,0,sizeof(orinum));
zerozero();
int len=strlen(s+1);
for(int i=1;i<=len;i++)
{
orinum[s[i]-'0']++;
}
for(int k=0;k<25;k++)
{
if(check(dir[k][0],dir[k][1])==false)
continue;
memset(v,0,sizeof(v));
memset(num,0,sizeof(num));
copy(num,orinum);
int l,r;
l=r=1;
copy(q[1].num,num);
q[1].num[dir[k][0]]--;
q[1].num[dir[k][1]]--;
int tem=getsum(q[1].num);
q[1].r=tem%9;
tem%=9;
v[tem][tem][0]=1;
int realreminder=((-dir[k][0]-dir[k][1])%9+9)%9;
while(l<=r)
{
if(cmp(q[l].num,ansnum)>=0&&q[l].r==realreminder)
{
//ansflag=1;
last1=dir[k][0];
last2=dir[k][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(last1==-1&&haszero)
{
printf("Case %d: ",ca);
printf("0\n");
}
else if(last1==-1)
printf("Case %d: impossible\n",ca);
else if(last1==last2&&last1==0&&allzero())
{
printf("Case %d: ",ca);
printf("0\n");
}
else if(allzero())
{
printf("Case %d: ",ca);
printf("%d%d\n",last1,last2);
}
else if(!allzero())
{
printf("Case %d: ",ca);
output(ansnum);
printf("%d%d\n",last1,last2);
}
}
return 0;
}代码依旧非常猥琐。。。