题目

给出一个正整数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和字符串t，要我们判断t是否为s(n,k)的子串。
最直接的思路便是依次枚举出s(n,k)的所有可能的情况，并逐个进行判断。
程序整体思路清晰，但考虑到实现操作比较繁琐，宜分多个函数实现各个细节。

代码

#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
char a[1000001] = {0};//a字符数组用于临时接收字符串输入
char const *dir = "0123456789ABCDEF";
string t,s;
void calc(int n,int k);//生成s(n,k)
string oneChar(int i,int k);//返回k进制下数字i对应的字符串
bool check(int n);//判断是否能够找到符合条件的s(n,k)
int main()
{
    int n;
    scanf("%d\n%s",&n,a);
    t = a;
    printf("%s\n",check(n) ? "yes" : "no");
    return 0;
}
void calc(int n,int k)
{
    s.clear();
    string temp;
    for(int i = 1;i <= n;i++)
    {
        temp = oneChar(i,k);
        s.append(temp);
    }
}
bool check(int n)
{
    for(int k = 2;k <= 16;k++)
    {
        calc(n,k);//check函数内部，对s（n,k）做枚举
        if(s.find(t) != -1)
            return true;
    }
    return false;
}
string oneChar(int i,int k)
{
    string temp;
    do
    {
        temp.append(1, dir[i % k]);//考虑到10进制以上会以字母代表数字的情况，借助一个dir字符串实现
        i /= k;
    }while(i != 0);
    reverse(temp.begin(),temp.end());
    return temp;
}