1 http://acm.hdu.edu.cn/showproblem.php?pid=1404 1 #include <iostream>
2 #include <sstream>
3 #include <string>
4
5 using namespace std;
6 const int N=1000000;
7 int dp[N];
8 int dfs(int n)
9 {
10 int hash[150];
11 memset(hash,0,sizeof(hash));
12 int tm,tp;
13 tm=tp=n;
14
15 tm=tp%10;
16 if(tm==0){
17 tp/=10;
18 if(dp[tp]==-1)
19 dp[tp]=dfs(tp);
20 hash[dp[tp]]=1;
21 }
22 while(tm>0){
23 --tp;
24 if(dp[tp]==-1)
25 dp[tp]=dfs(tp);
26 hash[dp[tp]]=1;
27 --tm;
28 }
29 tp=n;
30 tm=(tp/10)%10;
31 if(tm==0&&n>=100){
32 tp/=100;
33 if(dp[tp]==-1)
34 dp[tp]=dfs(tp);
35 hash[dp[tp]]=1;
36 }
37
38 while(tm>0){
39 tp-=10;
40 if(tp<10)break;
41 if(dp[tp]==-1)
42 dp[tp]=dfs(tp);
43 hash[dp[tp]]=1;
44 tm--;
45 }
46 tp=n;
47 tm=(tp/100)%10;
48 if(tm==0&&n>=1000){
49 tp/=1000;
50 if(dp[tp]==-1)
51 dp[tp]=dfs(tp);
52 hash[dp[tp]]=1;
53 }
54
55 while(tm>0){
56 tp-=100;
57 if(tp<100)break;
58 if(dp[tp]==-1)
59 dp[tp]=dfs(tp);
60 hash[dp[tp]]=1;
61 tm--;
62 }
63
64 tp=n;
65 tm=(tp/1000)%10;
66 if(tm==0&&n>=10000){
67 tp/=10000;
68 if(dp[tp]==-1)
69 dp[tp]=dfs(tp);
70 hash[dp[tp]]=1;
71 }
72 while(tm>0){
73 tp-=1000;
74 if(tp<1000)break;
75 if(dp[tp]==-1)
76 dp[tp]=dfs(tp);
77 hash[dp[tp]]=1;
78 tm--;
79 }
80
81 tp=n;
82 tm=(tp/10000)%10;
83 if(tm==0&&n>=100000){
84 tp/=100000;
85 if(dp[tp]==-1)
86 dp[tp]=dfs(tp);
87 hash[dp[tp]]=1;
88 }
89 while(tm>0){
90 tp-=10000;
91 if(tp<10000)break;
92 if(dp[tp]==-1)
93 dp[tp]=dfs(tp);
94 hash[dp[tp]]=1;
95 tm--;
96 }
97 tp=n;
98 tm=(tp/100000)%10;
99 while(tm>0){
100 tp-=100000;
101 if(tp<100000)break;
102 if(dp[tp]==-1)
103 dp[tp]=dfs(tp);
104 hash[dp[tp]]=1;
105 tm--;
106 }
107 for(int i=0;i<150;i++)
108 if(hash[i]==0)return i;
109 }
110
111 int main()
112 {
113 memset(dp,-1,sizeof(dp));
114 dp[0]=1;
115 char s[9];
116 while(gets(s)){
117 if(s[0]=='0'){
118 printf("Yes\n");
119 continue;
120 }
121 int len=strlen(s);
122 int nn=0;
123 for(int i=0;i<len;i++)
124 nn=nn*10+s[i]-48;
125 if(dp[nn]==-1)dp[nn]=dfs(nn);
126 if(dp[nn]==0){
127 printf("No\n");
128 }
129 else printf("Yes\n");
130 }
131 return 0;
132 }
讀入轉化為int用c++流處理比直接模擬轉化慢許多...一直TLE...以前沒怎么覺得慢...數據量大時估計就體現出來了...
posted on 2008-07-24 14:44
小果子 閱讀(432)
評論(0) 編輯 收藏 引用