专栏首页xiaoxi666的专栏codeM美团编程大赛初赛B轮E题

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • codeM美团编程大赛初赛B轮D题(考验你的数学思维!)

    [编程题] 模 时间限制:1秒 空间限制:32768K 给定四个正整数a,b,c,k,回答是否存在一个正整数n,使得a*n在k进制表示下的各位的数值之和模b...

    xiaoxi666
  • 二分查找变种

    该算法有很多版本,这里给出java中实现比较好的一种方式。其中,>>>为无符号右移。

    xiaoxi666
  • 【模板小程序】非负数2~62任意进制转换(普通版本+大数版本)

    再来一个针对大数的版本,而且直接在源进制和目标进制之间转换(不需要先转换为10进制),可以说是十分厉害。参考了http://blog.csdn.net/jast...

    xiaoxi666
  • JavaScriptSerializer 序列化json 时间格式

     利用JavaScriptSerializer 序列化json 时间格式,得到的DateTime值值显示为“/Date(700000+0500)/”形式的JS...

    欢醉
  • flask下载excel

    将 bootstrap.min.css 放到 static 文件夹下,在 templates 文件夹下新建 index.html,里面写入如下信息:

    机器学习和大数据挖掘
  • 开发 | Google发布自然语言处理解析器SLING,免除模块化分析级联效应产生的缺陷

    AI科技评论消息,日前,Google发布自然语言框架语义解析器SLING,它能以语义框架图(semantic frame graph)的形式,将自然语言文本直接...

    AI科技评论
  • 让你的.NET程序翻译语言

    今天没事干,再看Bing的SDK。全他妈是英文,不过总算有点成果,那就是翻译。以后自己也可以写个程序翻译了。。

    KurtNiu
  • 【案例】SVG卡通赛车加载动画特效

    点击上方[我分享我快乐]→[...]右上角→[设为星标⭐]即可第一时间获取最新设计资源

    用户1730674
  • strom架构和构建Topology

    1.Hadoop的MapReduce与Storm的topology有什么不一样的地方? 2.Nimbus与hadoop的jobtracer作用是否类似? ...

    汤高
  • CentOS 7如何设置uWSGI和Nginx提供Python应用服务

    在本指南中,我们将设置一个由uWSGI提供服务的简单WSGI应用程序。我们将使用Nginx Web服务器作为应用程序服务器的反向代理,以提供强大的连接处理。我们...

    陈树丶

扫码关注云+社区

领取腾讯云代金券