codeM美团编程大赛初赛B轮E题

 1 #include <iostream>
 2 #include <string>
 3 #include <cmath>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 //将任意字符转换为十进制
 9 long long convertToDec(char c)
10 {
11     long long decNum;
12     if(c>='a' && c<='z')
13         decNum=c-87;
14     else if(c>='A' && c<='Z')
15         decNum=c-29;
16     else if(c>='0' && c<='9')
17         decNum=c-48;
18 
19     return decNum;
20 }
21 
22 //将十进制转换为这些字符[0-9a-zA-Z],61个字符，最大表示62进制
23 char convertFromDec(long long c)
24 {
25     long long objchar;
26     if(c>=10 && c<=35)
27         objchar=c+87;
28     else if(c>=36 && c<=61)
29         objchar=c+29;
30     else if(c>=0 && c<=9)
31         objchar=c+48;
32 
33     return objchar;
34 }
35 
36 //从原进制转换为2~62的任意进制(src:源进制，obj:目标进制，num:源进制下的数)
37 string convert(int src,int obj,int num)
38 {
39 
40     string num_str=to_string(num);
41 
42     long long decNum=0;//十进制数（中间数）
43     for(long long i=0;i<num_str.size();++i)
44         decNum+=convertToDec(num_str[i])*pow(src,num_str.size()-1-i);
45 
46     string strTmp;
47     long long tmp;
48     while(decNum>0)
49     {
50         tmp=decNum % obj;
51         strTmp=convertFromDec(tmp)+strTmp;
52         decNum/=obj;
53     }
54     return strTmp;
55 }
56 
57 
58 int main()
59 {
60     int n;
61     string t;
62     while(cin>>n>>t)
63     {
64         transform(t.begin(),t.end(),t.begin(),::tolower);//将t转换为小写了（因为本次题目用大写表示16进制的数，而我们的程序中是用小写表示16进制的）
65         bool Isyes=false;
66         //保存转换后的字符串，2~16进制共15种
67         vector<string> str_converted2To16(15);
68 　　　　 //该题还可以进一步优化，先找出t中的最大值，然后从该进制往上数，数到16时结束(而不是从2往上数)。
69         for(int k=2;k<=16;++k)
70         {
71             //对1~n的每个数字进行转换
72             for(int i=1;i<=n;++i)
73             {
74                 str_converted2To16[k-2]+=convert(10,k,i);
75             }
76             if(str_converted2To16[k-2].find(t)!=string::npos)
77             {
78                 Isyes=true;
79                 cout<<"yes"<<endl;
80                 break;
81             }
82         }
83         if(!Isyes)
84             cout<<"no"<<endl;
85     }
86     return 0;
87 }