bon

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

poj 3340
给定两个字符串:s跟t,长度一样,均不超过10,但t只包含数字,而s除了数字还可能含有"?",问将问号变成数字后得到的数字中,有多少个数是大于t的。
很明显用搜索找出所有符合要求的数字即可。
搜索从s的第一个字符s[0]开始,每次向下递归都检查s的下一个字符s[level]。根据当前字符有一下几种搜索方向:

1. s[level]=='?', 设当前值为now,则下一个值可以是now*10+i, 0<=i<=9,只要这个值大于等于t[0~level]所表示的数字,则进入下一层递归:
     dfs(now*10+i, level+1)。
2. s[level]是一个数字要分两种情况讨论:若now*10+s[level]-'0'>=t[0~level]表示的数字,则dfs(now*10+s[level]-'0', level+1);否则就返回0,表示s跟t从0
      到level这一段不符合要求。

搜索的时候要注意优化,否则当s=“????????", t="00000000"时就要算很久。优化是当now*10+i > t[0~level]时,则j>i的情况都不用再递归计算了,因为dfs( now*10+{i+1 ,..., 9}, level+1)的结果跟dfs(now*10+i, level+1)的结果是一样的。只要乘上9-i就可以了。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 char s[11],t[11];
 6 int tt[11];
 7 int fact[11];
 8 int cnt;
 9 int len;
10 
11 __int64 dfs(int now,int level)
12 {
13     if(level==len){
14         if(now>tt[level-1]) return 1;//cnt+=(now%fact[level-1]-tt[level-1]%fact[level-1]);
15         return 0;
16     }
17     // 用0~9十个数字来代替?
18     if(s[level]=='?'){
19         int i=0;
20         while(i<10 && now*10+i<tt[level]) i++;
21         __int64 tmp=dfs(now*10+i,level+1);
22         if(i+1<10) tmp+=(9-i)*dfs(now*10+i+1,level+1);
23         return tmp;
24     }else if(now*10+s[level]-'0'>=tt[level]){
25         return dfs(now*10+s[level]-'0',level+1);
26     }else{
27         return 0;
28     }
29 }
30 
31 void solve()
32 {
33     int i,j,k;
34     len=strlen(s);
35     tt[0]=t[0]-'0';
36     for(i=1;i<len;i++) tt[i]=tt[i-1]*10+t[i]-'0';
37     cnt=0;
38     printf("%I64d\n",dfs(0,0));
39 }
40 
41 int main()
42 {
43     fact[0]=1;
44     for(int i=1;i<=10;i++) fact[i]=fact[i-1]*10;
45     while(true){
46         scanf("%s",s);
47         if(s[0]=='#'return 1;
48         scanf("%s",t);
49         solve();
50     }
51 }
52 
posted on 2008-05-12 00:59 bon 阅读(320) 评论(1)  编辑 收藏 引用 所属分类: Programming Contest

Feedback

# re: poj 3340 2009-02-18 16:07 czcomt
不用DFS的,直接有数学规律的,找出满足条件的最小的数就可以了  回复  更多评论
  


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


Google PageRank 
Checker - Page Rank Calculator