The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

集训专题训练1::搜索 福大校赛 G 整除45问题,状态空间搜索

五月份做的吧 那个时候用了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神牛指点。

posted on 2010-07-03 10:58 abilitytao 阅读(1491) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理