题解 | #曹老师的请教#

题目链接：https://ac.nowcoder.com/acm/contest/94570/C

设正整数 ( N )，于 1 至 ( N ) 间，得数若干，数之条件如下：凡数自其末位至首位读之，必奇位（如个位、百位、万位等）皆奇，偶位（如十位、千位、十万位等）皆偶，斯数方称“善数”。若数中位列奇偶而不合此道者，则不谓之善数，弃之无疑。

今有数 ( N ) ，意在求自 1 至 ( N ) 所有“善数”之数，冀能尽得此类，以识奇偶之异妙，亦见“善数”之珍稀也。

解析：

“善数”指奇数位都是奇数，偶数位都是偶数。

因此，我们可以构造出范围内的所有善数

对于一位数，善数有： 1 3 5 7 9

对于两位数，善数有： 21 23 25 27 29 41 43 45 47 49...

我们可以发现， n 位的善数可以看作由 n-1 位的善数在最前面增加一个符合条件的数字。

因此，我们可以得到以下代码：

对于奇数位

int m = 1,temp = 1;
int l = 0,r = 0;
for(int j = 0;j<5;j++)
{
    for(int k = l;k<=r;k++)
        q[m++] = (j*2+1) * temp;
}
l = r+1,r = m-1;

对于偶数位

for(int j = 1;j<5;j++)
{
    for(int k = l;k<=r;k++)
        q[m++] = q[k] + (j*2) * temp;
}
l = r+1,r = m-1;

在实际调试中，我们可以发现，对于偶数位为0的情况，我们并没有进行计算在内，因此，修改奇数位的代码为：

for(int j = 0;j<5;j++)
{
    if(i > 2) //当且仅当长度大于2时，存在偶数位为0的情况
    {
        for(int k = ll;k<=rr;k++)
        {
            q[m++] = q[k] + (j*2+1) * temp;
            }
    }
    for(int k = l;k<=r;k++)
        q[m++] = q[k] + (j*2+1) * temp;
}
ll = r + 1,l = r+1,r = m-1,rr = m - 1;

因此，最终代码为：

#include <iostream>
using namespace std;
const int N = 1e7+10;
int q[N];

int main(){
    int n;
    cin>>n;
    int m = 1,temp = 1;
    int l = 0,r = 0;
    int ll,rr;
    for(int i = 1;i<8;i++)
    {
        if(i%2==1)
        {
            
            for(int j = 0;j<5;j++)
            {
                if(i > 2)
                {
                    for(int k = ll;k<=rr;k++)
                    {
                        q[m++] = q[k] + (j*2+1) * temp;
                        //cout<<q[m-1]<<endl;
                        }
                    
                }
                for(int k = l;k<=r;k++)
                    q[m++] = q[k] + (j*2+1) * temp;
            }
            ll = r + 1,l = r+1,r = m-1,rr = m - 1;
             
        }
        else{
            for(int j = 1;j<5;j++)
            {
                for(int k = l;k<=r;k++)
                    q[m++] = q[k] + (j*2) * temp;
            }
            l = r+1,r = m-1;
        }
        temp = temp * 10;
    }
    long long res = 1;
    while(q[res] <= n) 
    {    
        //cout<<q[res]<<" ";
        res++;
    }
    //cout<<endl;
    cout<<res-1<<endl;
    return 0;
}