专栏首页奇妙的算法世界AcWing1081 度的数量(数位dp)

AcWing1081 度的数量(数位dp)

题目描述

思路

题目链接 关于数位dp有两个技巧:第一是可以使用前缀和的思想,对于求区间 [ L , R ] [L,R] [L,R]内符合要求的数,我们可以使用 f [ R ] − f [ L − 1 ] f[R]-f[L-1] f[R]−f[L−1]来获得答案。第二是使用树的形式来考虑。

对于这道题来说,从高位开始,依次考虑每一位。 对于第 n − 1 n-1 n−1位来说,我们可以分成两个分支: 0 − a n − 1 − 1 0 -a_{n-1}-1 0−an−1​−1和 a n − 1 a_{n-1} an−1​。对于左分支来说,有两种选择,如果放1,则其他各位放1的方案数为 C ( n − 1 , k − 1 ) C(n-1,k-1) C(n−1,k−1),如果不放1,则其他各位放1的方案数为 C ( n − 1 , k ) C(n-1,k) C(n−1,k)。

细节方面详看代码。

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "cassert"
#include "unordered_map"
using namespace std;
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define seteps(N) setprecision(N)
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define lson (ind<<1)
#define rson (ind<<1|1)
#define DEBUG(x)  cout<<"                 "<<x<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int,int> PII;
typedef pair<char,char> PCC;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int N=35;
const int M=10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
int c[N][N];
int k,b;
//预处理组合数
void init(){
    rep(i,0,N){
        rep(j,0,i+1){
            if(!j) c[i][j]=1;
            else c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }
}
int f(int n){
    if(!n) return 0;//如果为0,则无法满足题意
    vector<int> nums;
    while(n) nums.PB(n%b),n/=b;
    int res=0,last=0;
    rrep(i,sz(nums)-1,0){
        int x=nums[i];
        if(x){
            res+=c[i][k-last];
            //当x>1时,才会有放1的情况,由于放1,所以走不了右分支,直接break
            if(x>1){
                if(k-last-1>=0) res+=c[i][k-last-1];
                break;
            }else last++;
        }
        if(last>k) break;
        if(!i && last==k) res++;
    }

    return res;
}
void solve(){
    init();
    int l,r;
    cin>>l>>r>>k>>b;
    cout<<f(r)-f(l-1)<<endl;
}
int main(){
    IOS;
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    //int t;cin>>t;
    //while(t--)
        solve();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 2493 (map)

    给定有n个词的字典和m个句子,每个词语除首位和末位的字母可以任意移动,求能够构成m个句子的总共不同情况有多少

    dejavu1zz
  • codeforces 1429E(dp)

    很容易可以看出是一道dp题,题目中有两个状态:层数和方式,所以我们使用f[i][0]表示上第i层前走的是楼梯,使用f[i][1]表示上第i层前走的是电梯,得到状...

    dejavu1zz
  • I - Coins(dp)

    dejavu1zz
  • uva_1422 Processor

      有n个任务, 每个任务要在规定的时间[l, r]内完成, 工作量为 w, 每个任务可以分开完成。

    若羽
  • POJ - 1321 棋盘问题

    在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋...

    风骨散人Chiam
  • Codeforces Round #315 (Div. 2)

    这次可以说是最糟糕的一次比赛了吧, 心没有静下来好好的去思考, 导致没有做好能做的题。

    若羽
  • POJ2421 Constructing Roads 最小生成树

    有N个村庄,编号从1到N,您应该修建一些道路,使每两个村庄可以相互连接。我们说两个村庄A和B是连通的,当且仅当A和B之间有一条道路,或者存在一个村庄C使得A和C...

    风骨散人Chiam
  • LightOj_1321 Sending Packets

      给一个数据大小为S的数据包, 每一次发送需要K秒(单向),现在要从节点0 发送到节点 n-1。

    若羽
  • Codeforces Round #321 div2

    好像前几场的题解忘记写了, Orz 状态太差, 平均出两题   都不好意思写了 , 连掉4场, 都要哭晕了。

    若羽
  • AtCoderBeginnerContest109题解

    一开始读错题了,我以为移动几个都可以,事实上只能移动一个qwq,而且我以为0不统计入答案

    attack

扫码关注云+社区

领取腾讯云代金券