题解

cjdst

2026-02-08 22:45:24

发布于：广东

46阅读

0回复

0点赞

Difficulty：4.8 / Easy

考虑数位 DP。

显然需要记录当前遍历到第几位，上一位的值。然后随便写写就行了。

namespace cjdst{
    ll dfs(int cur, int n, int mx, bool lim, std::string &a, std::vector <std::vector <int>> &dp, std::string test){
		if(cur > n){
			return 1;
		}
		if(!lim && dp[cur][mx] != -1) return dp[cur][mx];
		if(lim && a[cur] - '0' < mx) return 0;
		ll ans = 0;
		if(!lim){
			for(int i = mx; i < 10; i++){
				ans += dfs(cur + 1, n, i, 0, a, dp, test + char(i + '0'));
			}
			return dp[cur][mx] = ans;
		}
		for(int i = mx; i < a[cur] - '0'; i++){
			ans += dfs(cur + 1, n, i, 0, a, dp, test + char(i + '0'));
		}
		ans += dfs(cur + 1, n, a[cur] - '0', lim, a, dp, test + a[cur]);
		return ans;
	}

	void solve(){
		std::string a;
		std::cin >> a;
		int n = a.size();
		a = " " + a + "     ";
		std::vector <std::vector <int>> dp(n + 5, std::vector <int>(11, -1));
		std::cout << dfs(1, n, 0, 1, a, dp, "") - 1 << '\n';
	}
}

时间复杂度： $O(\log n)$ 。

有帮助，赞一个

去预览

0/2000

全部评论 3

码龄不足1年的屑OIer
为啥都用数位dp啊，我这种虽然慢但也能过

#include <bits/stdc++.h> using namespace std; bool ok(int n){ string m = to_string(n); string k = m; sort(k.begin(),k.end()); return m == k; } int main(){ int a; cin >> a; int sumn = 0; for (int i = 1;i <= a;i++){ sumn+=ok(i); } cout << sumn; return 0; }
1周前来自黑龙江
1
- 🥥
  回复
  码龄不足1年的屑OIer
  人家的虽然难写，但比你运行快啊（这题数据量扩到10的12次方就老实了）
  
  1周前来自上海
  0
- 码龄不足1年的屑OIer
  回复
  🥥
  关键这是欢乐赛啊，考试时真这么写，一辈子别想冲总榜了，即使AK，题目浪费的时间也非常多，我现在很感觉他这个不像自己写的，真的有人会这么写代码吗
  
  1周前来自黑龙江
  0
- 🥥
  回复
  码龄不足1年的屑OIer
  人家是想练习数位DP，有没想打比赛（dalao打欢乐赛基本浪费时间）
  
  1周前来自上海
  0

prediction

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a;
    cin>>a;
    int sum=0;
    for(int i = 1;i<=a;i++)
        {
            //数位分离，判断低位是否大于高位
            int b=i%10;//个
            int c=i/10%10;//十
            int d=i/100%10;//百
            int e=i/1000%10;//千
            int f=i/10000%10;//万
            int g=i/100000%10;//十万
            int h=i/1000000%10;//百万；
            if(a>=b&&b>=c&&c>=d&&d>=e&&e>=f&&f>=g&&g>=h)
            {
                sum++;
            }
        }
    cout<<sum;
    return 0;
}

暴力...

1周前来自浙江

prediction
回复
prediction
比赛数位分离忘记咋写了

1周前来自浙江
0
cjdst
回复
prediction
while循环就行了啊

1周前来自广东
0
prediction
回复
cjdst
你知道的，我是个蒟蒻

1周前来自浙江
0

oiia猫

自己的写法

#include<iostream>
using namespace std;
bool bujiang(int n){
    int i=0,a[7]={};//n最大为10^6，共7位，所以数组大小为7
    if(n>=1&&n<=9)return true;//1到9的数字只有1位，一定是不降数
    while(n!=0){
        a[i]=n%10;
        n/=10;
        i++;
    }
    for(int j=1;j<7;j++){
        if(a[j]>a[j-1])return false;
    }
    return true;
}
int main(){
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(bujiang(i))ans++;
    }
    cout<<ans;
    return 0;
}

cjdst的看不懂

1周前来自河北

闪电九尾狐
回复
oiia猫
其实边吃边拉也可以，直接省掉数组。

1周前来自广东
0