The Fourth Dimension Space

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

集训专题训练1::搜索 福州大学全国邀请赛 Divisibility by Thirty-six 状态空间搜索

和整除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;
}


代码依旧非常猥琐。。。

posted on 2010-07-03 17:30 abilitytao 阅读(1523) 评论(1)  编辑 收藏 引用

评论

# re: 集训专题训练1::搜索 福州大学全国邀请赛 Divisibility by Thirty-six 状态空间搜索 2010-07-10 09:30 wuyichen

把函数都改成内联的应该会快一点  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理