codeM美團程式設計大賽初賽B輪E題

題目描述

給出一個正整數n，我們把1..n在k進制下的表示連起來記為s(n,k)，例如s(16,16)=123456789ABCDEF10, s(5,2)=11011100101。現在對于給定的n和字元串t，我們想知道是否存在一個k(2 ≤ k ≤ 16)，使得t是s(n,k)的子串。

輸入描述:

第一行一個整數n(1 ≤ n ≤ 50,000)。

第二行一個字元串t(長度 ≤ 1,000,000)

輸出描述:

"yes"表示存在滿足條件的k，否則輸出"no"

輸入例子:

8

01112

輸出例子:

yes

這裡我之前就寫了一套可以将任意進制轉換為2~62進制的代碼，可以直接套用（注意僅針對非負數）。

要注意判斷為yes時及時退出，避免無謂的後續計算，這裡的思想總體來說屬于暴力法，好像也隻有這樣了（攤手），不過還是要誇誇C++的stl庫，效率不錯。

有其他好方法記得留言交流哦！感謝！

該題還可以進一步優化，先找出t中的最大值，然後從該進制往上數，數到16時結束。

代碼如下：

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 }      

 補充：

　　大小寫轉換函數請用全局命名空間中的函數，這也是lower前面要加::全局作用符的原因。因為有多個不同的版本。

　　詳情可參見https://stackoverflow.com/questions/5539249/why-cant-transforms-begin-s-end-s-begin-tolower-be-complied-successfu

『注:本文來自部落格園“小溪的部落格”，若非聲明均為原創内容，請勿用于商業用途，轉載請注明出處http://www.cnblogs.com/xiaoxi666/』