pein531
18分钟前

题目描述

难度分:$2024$

输入$N(1 \leq N \leq 10^{18})$和$K(1 \leq K \leq 10^9)$。

问:有多少个不超过$N$的正整数,其数位乘积不超过$K$?

输入样例$1$

13 2

输出样例$1$

5

输入样例$2$

100 80

输出样例$2$

99

输入样例$3$

1000000000000000000 1000000000

输出样例$3$

841103275147365677

算法

数位DP

不知道是不是要放假了的原因,灵佬今天选的这道题虽然难度分不低,但是非常“模板”,只要分析清楚状态数量的上界,可以说就是一道数位DP的板子题。先将$N$转化为字符串$s$,其长度为$n$。

状态定义

$dp[i][mu][islimit][isnum]$表示从数位$i$开始填完最后一个数位$n-1$(数位从高到低用$0$起始标号),能够得到的数位积不超过$K$,且数字大小不超过$N$的数字个数。其中$mu$表示数位$[0,i)$的乘积,$islimit$表示前面的数位是否贴合上界,$isnum$表示前面的数位是否填过数字。

状态转移
$base$ $case$:

很显然,当$i \geq n$时,所有数位就全部填完了,如果$isnum=1$且$mu \leq K$,说明得到了一个符合题意的数字。

一般情况:

如果$isnum=0$,那么当前数位$i$可以继续不填数,状态转移方程为

$dp[i][mu][islimit][isnum]=dp[i+1][mu][0][isnum]$

否则,当前数位尝试填$d \in [1-isnum,ub]$。如果前面的数位$[0,i)$贴合上界,$ub=s[i]$;不贴合上界,则$ub=9$。状态转移方程为

$dp[i][mu][islimit][isnum]=\Sigma_{d=1-isnum}^{ub}dp[i+1][mu \times d][islimit \land digit=d][1]$

复杂度分析

在这个题的数据范围之下,通过打表,发现状态中$mu$的取值最多就是$A=36000$多,因此在最差情况下状态的个数也只有一百多万,而状态转移又是常数级别,因此时间复杂度为$O(An)$($n$就是题干中数字$N$的数位个数)。

空间消耗主要在于状态的存储,和时间复杂度是一个级别的。

C++ 代码

from functools import lru_cache

x, k = map(int, input().split())
s = str(x)
n = len(s)

@lru_cache(None)
def dfs(i: int, mu: int, islimit: int, isnum: int) -> int:
    if i >= n:
        return 1 if isnum and mu <= k else 0
    digit = int(s[i])
    cnt = dfs(i + 1, mu, 0, 0) if not isnum else 0
    ub = digit if islimit else 9
    for d in range(1 - isnum, ub + 1):
        cnt += dfs(i + 1, mu*d, islimit and digit == d, 1)
    return cnt

res = dfs(0, 1, 1, 0)
dfs.cache_clear()
print(res)


新鲜事 原文

zhouyishan
22分钟前
运动会错过检录



brainer
38分钟前

sublime 如何设置缺省源啊




人间清欢
39分钟前

题目描述

blablabla

样例

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

using namespace std;

int main()
{
    string s;
    getline(cin,s);
    for (int i = 0; i < s.size(); i ++ ){
    if((s[i]>='a'&&s[i]<'z')||(s[i]>='A'&&s[i]<'Z'))    
    s[i]=s[i]+1;
   else if(s[i]=='z') s[i]='a';
   else if(s[i]=='Z') s[i]='A';
    }
    cout << s;

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



hh_59
42分钟前
#include<bits/stdc++.h>

using namespace std;

vector<int>div(vector<int>&A,int b,int&r){
    vector<int>C;
    r=0;

    for(int i=A.size()-1;i>=0;i--){
        r=r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }

    return C;
}

int main(){
    string a;
    int b;
    cin>>a,b;

    vector<int>A;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');

    int r;
    auto C=div(A,b,r);

    int i=0;
    while(C[i]==0)i++;
    for(;i<C.size();i++)cout<<C[i];

    cout<<endl<<r<<endl;

    return 0;
}

# 


新鲜事 原文

么么
49分钟前
AcWing《Web应用课》拼团优惠!https://www.acwing.com/activity/content/introduction/1150/group_buy/169208/


新鲜事 原文

Lonely_5
53分钟前
AcWing《秋季每日一题2023》拼团优惠!https://www.acwing.com/activity/content/introduction/3434/group_buy/169174/



Felix_16
1小时前

题目描述

在这个问题中,你需要读取一个整数值并将其分解为多张钞票的和,每种面值的钞票可以使用多张,并要求所用的钞票数量尽可能少。

请你输出读取值和钞票清单。

钞票的可能面值有 100,50,20,10,5,2,1

经过实验证明:在本题中,优先使用面额大的钞票可以保证所用的钞票总数量最少。

输入格式
输入一个整数 N

输出格式
参照输出样例,输出读取数值以及每种面值的钞票的需求数量。

数据范围
0<N<1000000

样例

输入样例
576

输出样例
576
5 nota(s) de R$ 100,00
1 nota(s) de R$ 50,00
1 nota(s) de R$ 20,00
0 nota(s) de R$ 10,00
1 nota(s) de R$ 5,00
0 nota(s) de R$ 2,00
1 nota(s) de R$ 1,00

C++ 代码

#include <stdio.h>
int main()
{
    int num;
    scanf("%d",&num);
    int h,f,t,ten,five,two,one; // 定义每张面值人民币的数量

    // [注]优先使用面额大的钞票可以保证所用的钞票总数量最少
    if(num / 100 != 0) // 存在百位
    {
        h = num / 100;
    }

    int shiwei = num % 100 / 10;
    switch(shiwei)
    {
        // [注]不包含的纸币也要赋值为0!例如case 9中,尽管没有10元的纸币,但是也要将10元纸币的数量定义为0,否则ten最终会变成未初始化的变量
        case 9: f = 1,t = 2,ten = 0; break;
        case 8: f = 1,t = 1,ten = 1; break;
        case 7: f = 1,t = 1,ten = 0; break;
        case 6: f = 1,t = 0,ten = 1; break;
        case 5: f = 1,t = 0,ten = 0; break;
        case 4: f = 0,t = 2,ten = 0; break;
        case 3: f = 0,t = 1,ten = 1; break;
        case 2: f = 0,t = 1,ten = 0; break;
        case 1: f = 0,t = 0,ten = 1; break;
        case 0: f = 0,t = 0,ten = 0; break;
    }

    int gewei = num % 100 % 10;
    switch(gewei)
    {
        case 9: five = 1,two = 2,one = 0; break;
        case 8: five = 1,two = 1,one = 1; break;
        case 7: five = 1,two = 1,one = 0; break;
        case 6: five = 1,two = 0,one = 1; break;
        case 5: five = 1,two = 0,one = 0; break;
        case 4: five = 0,two = 2,one = 0; break;
        case 3: five = 0,two = 1,one = 1; break;
        case 2: five = 0,two = 1,one = 0; break;
        case 1: five = 0,two = 0,one = 1; break;
        case 0: five = 0,two = 0,one = 0;break;
    }

    printf("%d\n",num);
    printf("%d nota(s) de R$ 100,00\n",h);
    printf("%d nota(s) de R$ 50,00\n",f);
    printf("%d nota(s) de R$ 20,00\n",t);
    printf("%d nota(s) de R$ 10,00\n",ten);
    printf("%d nota(s) de R$ 5,00\n",five);
    printf("%d nota(s) de R$ 2,00\n",two);
    printf("%d nota(s) de R$ 1,00\n",one);

    return 0;
}



人间清欢
1小时前

题目描述

blablabla

样例

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

using namespace std;

int main()
{
    string a,b;
    getline(cin,a);//可以接收空格并输出
    getline(cin,b);
    for(auto &c:a) c=tolower(c);//把a的内容赋到c中,执行tolower操作后,再将c的内容赋给a
    for(auto &c:b) c=tolower(c);
    if(a>b) cout << ">";
    if(a<b) cout << "<";
    if(a==b) cout << "=";
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


分享 求拼团

acwing_gza
1小时前

AcWing《CSP-S 辅导课》拼团优惠!https://www.acwing.com/activity/content/introduction/3444/group_buy/169201/

三缺二