2016 网易校招内推C/C++第二场8.6

选择题20个，每个1.5，编程题3个，每个20，简答题1个10分。

解：

第二题，一开始喵了一眼，好开心，这不是水题么，第一反应想到的是递归，然后马上就写了，结果case10%，一脸蒙蔽，数据值很大，考虑边界条件也比较困难。

递归：

 1 #include "iostream"
 2 #define MAX 100000
 3 #define tag 1000000007
 4 
 5 typedef long long LL;
 6 
 7 using namespace std;
 8 
 9 LL x;
10 int n = 1;
11 
12 LL solve(LL x, int n)
13 {
14     if (n > MAX)
15         return -1;
16     if ((4 * x + 3) % tag == 0 || ((8 * x + 7) % tag == 0))
17         return n;
18     else
19     {
20         solve(4 * x + 3, n + 1);
21         solve(8 * x + 7, n + 1);
22     }
23     return 0;
24 }
25 
26 int main()
27 {
28 
29     cin >> x;
30     cout << solve(x, 1);
31 
32 }

结束后和学弟讨论了下，学弟教我可以反向打表，时间换空间，把符合条件的位置都算出来，然后检索输入的在不再里面。然后我试着写了下，用STL的map，映射i次数和位置num。QWQ又学到了一招。满满的套路。

反向打表，map映射：

 1 #include "iostream"
 2 #include "map"
 3 #define MAX 100000
 4 #define tag 1000000007
 5 
 6 typedef long long LL;
 7 
 8 using namespace std;
 9 
10 LL x;
11 int n = 1;
12 
13 map<int,int> a,b;
14 
15 //125000000
16 void fun()
17 {
18     for (int i = 1; i < MAX; i++)
19     {
20         for (int num = tag*i,j=1; ;j++ )
21         {
22             a.insert(pair<int,int>(num,j*i-1 ));
23             if ((num - 7) % 8 == 0)
24                 num = (num - 7) / 8;
25             else
26                 break;
27         }
28 
29         for (int num = tag*i, j = 1; ; j++)
30         {
31             b.insert(pair<int, int>(num, j*i));
32             if ((num - 3) % 4 == 0)
33                 num = (num - 3) / 4;
34             else
35                 break;
36         }
37     }
38 }
39 
40 
41 int main()
42 {
43     cin >> x;
44 
45     fun();
46 
47     map<int, int>::iterator iter;
48     iter=a.find(x);
49     if (iter != a.end())
50         cout << iter->second;
51 
52     iter = b.find(x);
53     if (iter != b.end())
54         cout << iter->second;
55 }

真是尴尬我还不会Map里面怎么find value的值，只能把key和value的位置换了下。