1031 Hungar的得分问题（二）-白红宇

1031 Hungar的得分问题（二）

阅读量：7067 次

发布时间：2019-06-28

本文共 1113 字，大约阅读时间需要 3 分钟。

[题目传送门]

[题意]

从小到大排列只有 4 和 7存在的数，4 ， 7 ，44 ，47 ........ 这样，然后给你一个数n，n保证只有4和7组成，问你这个数是第几个。

看了一下HSS用了杨辉三角和进制转化，不禁先跪一下 Orz 。

这题打表，弱弱的水过了，BFS的赶脚，我们做一个数组 a[] , a[0] = 4 , a[1] = 7;

然后对每一个 a[i] 进行操作将 a[i] * 10 + 4 , a[i] * 10 + 7 放到数组后面。

结果发现就是顺序呀～。 4 ， 7 ， 4 * 10 + 4 , 4 * 10 + 7 , 7 * 10 + 4 , 7 * 10 + 7 .........

最后因为是递增的，所以二分一下。

[代码]

1 #include 
     
       2 #include 
      
        3 #include 
       
         4   5 using namespace std; 6   7 vector
        
          VV; 8   9 void init()10 {11     VV.clear();12     VV.push_back(4); VV.push_back(7);13     for(int i = 0 ; i < VV.size() ; i++)14     {15         if(VV[i] > 1000000000) break;16         else {VV.push_back(VV[i] * 10 + 4); VV.push_back(VV[i] * 10 + 7);} 17     }18     return ;19 }20  21 int main()22 {23     init();24     int T;25     while(cin >> T) for(int i = 0 ; i < T ; i++)26     {27         long long n;28         cin >> n;29         int rank = lower_bound(VV.begin() , VV.end() , n) - VV.begin();30         cout << rank + 1 << endl;31     }32     return 0;33 }