本文共 1812 字，大约阅读时间需要 6 分钟。

一道很诡异的题，但很有推理的必要。

数列（数论）

题目描述

有一个数列，满足两个性质：

1.     数列中任意两端相邻且长度相等的部分不完全相同，比如3 6 3 6 是不合法的。

2.     该数列是左右满足条件1的数列中字典序最小的。

3.     此为正数数列（原题中没说）

给出一个整数N，求数列的第N项。

输入

一个整数N

N<= 

输出

一个数，表示数列的第N项。

样例输入

20

样例输出

3

 题解

对于N<=  的超大数据，我们用高精度数就可以了，但这也表明，再加上高精运算后，剩下的步骤必须降到此数的 log 级。

题目乍一看好像很难想，但当我们看到“字典序最小”时，就可以从1 开始推起了。

当 N = 1 时，数列为——  1

当 N = 2 时，数列就有可能出现重复了，得加上一个不为零的最小数。数列为——  1  2

当 N = 3 时，在上一个的基础上，只要不为 1 就行。数列为——  1  2  1

。。。。。。

最终数列为： 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 ......

我们可以发现，这个数列很有规律，（而且没理由认为它会打破规律）。

即当 N = （乘一个任意奇数2n+1，n为任意非负整数）时，A[N] = x + 1 。

把N，也就是这个式子可以一直除以 2 ，最后当除到 x 次时会出现这个式子：，此时判断N的个位会发现其模 2 等于一（小学知识）。

记录N /= 2 的次数，此数 + 1就是最终的答案，不难发现，这是 log 级的。

#include
   
    #include
    
     #include
     
      #define max(x,y) ((x) > (y) ? (x) : (y))#define min(x,y) ((x) < (y) ? (x) : (y))#define LL long longusing namespace std;int read() {    int f = 1,x = 0;char s = getchar();    while(s < '0' || s > '9') {if(s == '-')f = -1;s = getchar();}    while(s >='0' && s <= '9'){x = x * 10 + s - '0';s = getchar();}    return x * f;}struct bi{    int s[1005],len;    bi(){len = 1;memset(s,0,sizeof(s));}    bi(int on) {len = 1;memset(s,0,sizeof(s));s[1] = on % 10;}    void read() {        char ss = getchar();len = 0;        while(ss < '0' || ss > '9') {ss = getchar();}        while(ss >='0' && ss <= '9'){s[++len] = ss - '0';ss = getchar();}        for(int i = 1;i <= (len >> 1);i ++)swap(s[i],s[len - i + 1]);    }}n,j(1);LL c;bi operator / (bi x,int y) {    bi z;    int m = 0;    for(int i = x.len;i > 0;i --) {        z.s[i] = x.s[i] + m * 10;        m = z.s[i] % y;        z.s[i] /= y;        if(z.s[i]) z.len = max(z.len,i);    }    return z;}bool f;int main() {    n.read();    while(n.len > 1 || n.s[1]) {        f = n.s[1] & 1;        n = n / 2;        if(f) break;        c ++;    }    printf("%lld\n",c);    return 0;}
     
    
   

转载地址：https://blog.csdn.net/weixin_43960414/article/details/89086521 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！