题目描述

好数，时间比较极限

补充：刚刚更新了数位DP写法。

输入样例1

24

输出样例1

7

暴力枚举

时间复杂度

$O(n)$

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

bool is_g(int n)
{
    int j = 1;
    while(n)
    {
        if(n % 10 % 2 && j % 2 == 0) return false;
        else if(n % 10 % 2 == 0 && j % 2) return false;
        n /= 10;
        j ++ ;
    }
    return true;
}

int main()
{
    int n;
    scanf("%d", &n);
    int ans = 0;
    for(int i = 1; i <= n; i ++ )       //时间复杂度大概是7 * 10^7
    {
        if(is_g(i)) ans ++ ;
    }
    printf("%d\n", ans);
    return 0;
}

数位DP求解

参考文献

《闫式DP分析法》

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

int f[N][10];

bool check(int i, int j)
{
    return ((j % 2 == 0) && (i % 2 == 0)) || ((j % 2) && (i % 2));
}

void init()
{
    for(int i = 0; i <= 9; i ++ ) f[1][i] = i % 2 == 1;
    for(int i = 2; i <= N; i ++ )
        for(int j = 0; j <= 9; j ++ )
            for(int k = 0; k <= 9; k ++ )
                if(check(i, j) && check(i - 1, k))
                        f[i][j] += f[i - 1][k];
}

int dp(int n)
{
    if(!n) return 0;

    vector<int> nums;

    while(n) nums.push_back(n % 10), n /= 10;

    int res = 0;
    int last = nums.size();
    for(int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for(int j = i == nums.size() - 1; j < x; j ++ )
        {
            res += f[i + 1][j];
        }
        if(check(last, x)) last -- ;
        else break;

        if(!i) res ++ ;
    }

    for(int i = 1; i < nums.size(); i ++ )
        for(int j = 1; j <= 9; j ++ )
            res += f[i][j];

    return res;
}

int main()
{
    init();
    int r;
    cin >> r;
    cout << dp(r) - dp(0) << endl;
    return 0;
}