Mirror Number SPOJ - MYQ10

2018-06-17 21:49:34来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Mirror Number SPOJ - MYQ10

题意:http://blog.csdn.net/hcbbt/article/details/38349367

稍微改一下http://www.cnblogs.com/hehe54321/p/loj-1205.html就行

 1 #include<cstdio>
 2 #include<cstring>
 3 typedef long long LL;
 4 LL ans[60][60][2];
 5 LL w[60];
 6 LL T;
 7 char l[100],r[100];
 8 LL temp[60];
 9 LL dp(LL tot,LL pos,bool pre0,bool limit)
10 {
11     if(pos<1)    return 1;
12     if(!limit&&ans[tot][pos][pre0]!=-1)
13         return ans[tot][pos][pre0];
14     LL i,res=0,end=limit?w[pos]:9;
15     for(i=0;i<=end;i++)
16     {
17         if(i!=0&&i!=1&&i!=8)    continue;
18         temp[pos]=i;
19         if(i==0&&pre0)
20             res+=dp(tot-1,pos-1,1,0);
21             //res+=dp(tot,pos-1,1,0);这样会错
22         else if(pos>tot/2)//5-->5,4,3 6-->6,5,4 如果在前一半则可以随便填
23             res+=dp(tot,pos-1,0,limit&&i==w[pos]);
24         else if(temp[pos]==temp[tot-pos+1])//如果在后一半就必须和前一半一样
25             res+=dp(tot,pos-1,0,limit&&i==w[pos]);
26     }
27     if(!limit)    ans[tot][pos][pre0]=res;
28     return res;
29 }
30 LL get(char x[])
31 {
32     LL len=strlen(x);
33     for(LL i=0;i<len;i++)    w[len-i]=x[i]-'0';
34     return dp(len,len,1,1);
35 }
36 bool ok(char x[])
37 {
38     LL len=strlen(x);
39     for(LL i=0;i<len;i++)
40         if(x[i]!=x[len-i-1]||(x[i]!='0'&&x[i]!='1'&&x[i]!='8'))
41             return false;
42     return true;
43 }
44 int main()
45 {
46     LL iii;
47     memset(ans,-1,sizeof(ans));
48     scanf("%lld",&T);
49     for(iii=1;iii<=T;iii++)
50     {
51         scanf("%s%s",l,r);
52         printf("%lld\n",get(r)-get(l)+ok(l));
53     }
54     return 0;
55 }

错误点:

错误的ok函数

1 bool ok(char x[])
2 {
3     LL len=strlen(x);
4     for(LL i=0;i<len/2;i++)
5         if(x[i]!=x[len-i-1]||(x[i]!='0'&&x[i]!='1'&&x[i]!='8'))
6             return false;
7     return true;
8 }

错在:如果是奇数位,且最中间一位不是0,1,8,其他位满足镜像回文,那么会误判为true(实际为false)。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:hdu 2828 Buy Tickets

下一篇:Palindromic Numbers LightOJ - 1205