以前刷过的数位dp

The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone' (also known as 'Rock, Paper, Scissors', 'Ro, Sham, Bo', and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can't even flip a coin because it's so hard to toss using hooves.

They have thus resorted to "round number" matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both "round numbers", the first cow wins,
otherwise the second cow wins.

A positive integer N is said to be a "round number" if the binary representation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.

Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many "round numbers" are in a given range.

Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).

Line 1: Two space-separated integers, respectively Start and Finish .

Line 1: A single integer that is the count of round numbers in the inclusive range Start .. Finish

#include<bits/stdc++.h>

using namespace std;

int dp[][],a[],l,r;

int dfs(int pos,int st,int pre,int lim)

{

    if(pos<)return st<=;

    if(!lim&&!pre&&dp[pos][st]!=-)return dp[pos][st];

    int mi=lim?a[pos]:,ans=;

    for(int i=;i<=mi;i++)

        if(pre&&!i)ans+=dfs(pos-,st,,lim&&i==a[pos]);

        else ans+=dfs(pos-,i?st+:st-,,lim&&i==a[pos]);

    if(!lim&&!pre)dp[pos][st]=ans;

    return ans;

}

int la(int x)

{

    int tot=;

    while(x)a[tot++]=x&,x>>=;

    return dfs(tot-,,,);

}

int main()

{

    memset(dp,-,sizeof dp);

    scanf("%d%d",&l,&r);

    printf("%d\n",la(r)-la(l-));

    return ;

}

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

1 100

0 0

80

#include<stdio.h>

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define lson l,(l+r)/2,rt<<1

#define rson (l+r)/2+1,r,rt<<1|1

#define dbg(x) cout<<#x<<" = "<< (x)<< endl

#define pb push_back

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define pll pair<long long,long long>

#define pii pair<int,int>

#define pq priority_queue

const int N=,MD=1e9+,INF=0x3f3f3f3f;

const ll LL_INF=0x3f3f3f3f3f3f3f3f;

const double eps=1e-,e=exp(),PI=acos(-.);

int c[N],dp[N][];

int dfs(int pos,int st,int pre,int lim)

{

    if(pos<)return ;

    if(!lim&&dp[pos][st]!=-)return dp[pos][st];

    int last=lim?c[pos]:,ans=;

    for(int i=; i<=last; i++)

        if(pre==&&i==||i==)continue;

        else ans+=dfs(pos-,i==,i,lim&&(i==last));

    if(!lim)dp[pos][st]=ans;

    return ans;

}

int slove(int q)

{

    int cnt=;

    while(q)c[cnt++]=q%,q/=;

    return dfs(cnt-,,-,);

}

int main()

{

    ios::sync_with_stdio(false),cin.tie(),cout.tie();

    int x,y;

    while(cin>>x>>y,x+y)

    {

        memset(dp,-,sizeof dp);

        cout<<slove(y)-slove(x-)<<"\n";

    }

    return ;

}

15 20

2

2

3

#include<stdio.h>

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define lson l,(l+r)/2,rt<<1

#define rson (l+r)/2+1,r,rt<<1|1

#define dbg(x) cout<<#x<<" = "<< (x)<< endl

#define pb push_back

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define pll pair<long long,long long>

#define pii pair<int,int>

#define pq priority_queue

const int N=,MD=1e9+,INF=0x3f3f3f3f;

const ll LL_INF=0x3f3f3f3f3f3f3f3f;

const double eps=1e-,e=exp(),PI=acos(-.);

int c[N],dp[N][N];

int x,y,k,b;

int dfs(int pos,int st,int lim)

{

    if(st>k||st+pos+<k)return ;

    if(pos<)return st==k;

    if(!lim&&dp[pos][st]!=-)return dp[pos][st];

    int last=lim?c[pos]:b-,ans=,mi=min(last,);

    for(int i=;i<=mi;i++)ans+=dfs(pos-,st+i,lim&&(i==last));

    if(!lim)dp[pos][st]=ans;

    return ans;

}

int slove(int q)

{

    int cnt=;

    while(q)c[cnt++]=q%b,q/=b;

    return dfs(cnt-,,);

}

int main()

{

    ios::sync_with_stdio(false),cin.tie(),cout.tie();

    cin>>x>>y>>k>>b;

    memset(dp,-,sizeof dp);

    cout<<slove(y)-slove(x-);

    return ;

}

题目描述

NIBGNAUK is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by the sum of its digits.

We will not argue with this and just count the quantity of beautiful numbers from 1 to N.

输入描述:

The first line of the input is T(1≤ T ≤ 100), which stands for the number of test cases you need to solve.
Each test case contains a line with a positive integer N (1 ≤ N ≤ 10

¹²

).

输出描述:

For each test case, print the case number and the quantity of beautiful numbers in [1, N].

输入例子:

2

10

18

输出例子:

Case 1: 10

Case 2: 12

-->

示例1

输入

复制

2

10

18

输出

复制

Case 1: 10

Case 2: 12

---

很难想到从数位和出发

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int a[];

ll dp[][][][],n;

ll dfs(int pos,int st,int sum,int mod,bool lim)

{

    if(pos<) return mod==&&st==sum;

    if(sum>st||sum+*(pos+)<st)return ;

    if(!lim&&dp[st][pos][sum][mod]>=) return dp[st][pos][sum][mod];

    ll ans=;

    int mi=lim?a[pos]:;

    for(int i=;i<=mi;i++)ans+=dfs(pos-,st,sum+i,(mod*+i)%st,lim&&i==mi);

    if(!lim) dp[st][pos][sum][mod]=ans;

    return ans;

}

ll cal(ll n)

{

    int pos=;

    while(n) a[pos++]=n%,n/=;

    ll ans=;

    for(int i=;i<=;i++)ans+=dfs(pos-,i,,,);

    return ans;

}

int main()

{

    int T,ca=;

    memset(dp,-,sizeof(dp));

    scanf("%d",&T);

    while(T--)scanf("%lld",&n),printf("Case %d: %lld\n",++ca,cal(n));

    return ;

}