Problem H. Hotel in Ves Lagos

Input le: hotel.in

Output le: hotel.out

Time limit: 1 second

Memory limit: 256 megabytes

A new hotel is being built in the city of Ves Lagos. The hotel will have an innite number of rooms (it is out of fashion to build hotels with nite numbers of rooms). The new hotel also tries to cater for superstitious guests. The most common superstition in Ves Lagos is that the number 13 brings bad luck. Accordingly, only numbers whose decimal forms do not contain the substring 13" will be used to label the rooms in the new hotel. For example, the hotel will have rooms numbered 1, 3, 14, 31, 123, but will not have the rooms 13, 132, 913, 1308, 1313. Let's consider the list of all room numbers, ordered increasingly. Find the N-th number in this list (members of the list are indexed from 1). Input The input le contains several test cases. The rst line of the le contains T (1 ≤ T ≤ 100), the number of test cases. Each of the following T lines describes one test case and contains the integer N (1 ≤ N ≤ 1018). Output The output le should contain exactly T lines, with the i-th line containing exactly one integer, the answer for the i-th test case from the input le.

Example hotel.in hotel.out

150

162

//题意，原来 1-n 标号的房间，现在，不想出现数字中有13 数字，问，原来的第 n 个们应标号为多少？

题解：由于数据特别大，所以要数位DP，套好模板后，还需要二分搜索标号为多少，注意的是，要尽量小，不然有一些重叠的

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <stdlib.h>
 6 #include <map>
 7 #include <queue>
 8 #include <set>
 9 #include <vector>
10 using namespace std;
11 #define LL unsigned long long
12 #define MX 100005
13 
14 LL n;
15 LL dp[30][3];
16 
17 void Init()
18 {
19     dp[0][2]=1;
20     for (int i=1;i<=25;i++)
21     {
22         dp[i][0]=dp[i-1][0]*10+dp[i-1][1];
23         dp[i][1]=dp[i-1][2];
24         dp[i][2]=dp[i-1][2]*10-dp[i-1][1];
25     }
26 }
27 
28 LL slove(LL x)
29 {
30     LL a[30],len=0;
31     while (x)
32     {
33         a[++len]=x%10;
34         x/=10;
35     }
36     a[len+1]=0;
37 
38     LL ans =0;
39     int flag=0;
40     for (int i=len;i>0;i--)
41     {
42         ans+=dp[i-1][0]*a[i];
43         if (flag)
44             ans+=dp[i-1][2]*a[i];
45         if (!flag&&((a[i]==1&&a[i-1]>3)||(a[i]>1)))
46             ans+=dp[i-1][1];
47         if (a[i]==3&&a[i+1]==1)
48             flag=1;
49     }
50     return ans;
51 }
52 
53 int main()
54 {
55     freopen("hotel.in","r",stdin);
56     freopen("hotel.out","w",stdout);
57     Init();
58     int t;
59     cin>>t;
60     while (t--)
61     {
62          cin>>n;
63          LL l=1,r=1e19;
64          LL ans;
65          while (l<=r)
66          {
67              LL mid = (l+r)>>1;
68              LL tp = mid-slove(mid+1);
69              if (tp>=n)
70              {
71                  ans = mid;
72                  r=mid-1;
73              }
74              else if (tp<n)
75                  l=mid+1;
76          }
77          cout<<ans<<endl;
78     }
79     return 0;
80 }

View Code