Mirror Number SPOJ - MYQ10
2018-06-17 21:49:34来源:未知 阅读 ()
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Add Two Numbers 2019-08-16
- leetcode 136 Single Number bit Option 2019-08-16
- 2018-10-13 21:30:51 conversion of number systems 2018-10-14
- POJ3252Round Numbers(数位dp) 2018-09-18
- SPOJ2713GSS4 - Can you answer these queries IV(线段树) 2018-09-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash