首页 > 其他分享 >牛客竞赛动态规划专题班数位dp例题

牛客竞赛动态规划专题班数位dp例题

时间：2024-03-29 14:56:59浏览次数：29  
标签：int pos 牛客 flag vector using 例题 dp mod

题单

A - 0的个数

这题算是一个思维题。

我的做法是就是统计每一位的 0 有多少个。

例如\(4032\)

  • 个位的零有\(403\)种
  • 十位的零有\(40*10\)种
  • 百位的零有\(3*100 + 33\)种，即千位去\([1,3]\)个位低两位取\([00,99]\)，或者千位取\(4\)低两位取\([00,33]\)
  • 千位不能取零
#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;

#define int i64

using vi = vector<i64>;
using pii = pair<i64, i64>;

const i64 mod = 1e9 + 7;
const i64 inf = 1e18;

int calc(int x) {
    if (x < 0) return 0;
    int ans = 1;
    for (int p = 1, y = 0; x > 0; p *= 10) {
        ans += (x / 10 - 1) * p;
        if (x % 10 > 0) ans += p;
        else ans += y + 1;
        y += (x % 10) * p, x /= 10;
    }
    return ans;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int l, r;
    while (true) {
        cin >> l >> r;
        if (l < 0 and r < 0) break;
        cout << calc(r) - calc(l - 1) << "\n";
    }
    return 0;
}

B - 送分了QAQ

首先我们们要把数字分成若干位。

然后我们设计状态\(f[i][st]\)从最高位到第\(i\)位数对应情况为\(st\)，且剩下\(i-1\)位任取，符合条件的数（包含\(38\)或包含\(4\)）的个数。

  • \(st=0\)表示前\(i\)位即没有\(4\)也没有\(38\)

  • \(st=1\)表示前\(i\)位即没有\(4\)也没有\(38\)，但第\(i\)是\(3\)

  • \(st=2\)表示前\(i\)位包含\(4\)或\(38\)

然后我们在维护一个变量\(flag\)表示前\(i-1\)位是否和原数相同，为什么要有这个呢？如果前\(i-1\)位都相同，则当前位的取值只能为\([0,a[i]]\)，如果不是则可以取到\([0,9]\)

#include<bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;

#define int i64

using vi = vector<int>;

vi a(20);

vector f( 20 , vi(3 , -1));


int dp(int pos, int st, bool flag) {
    if (pos == 0) return st == 2;
    if (flag and f[pos][st] != -1) return f[pos][st];
    int x = flag ? 9 : a[pos];
    int ans = 0;
    for (int i = 0; i <= x; i++) {
        if (i == 4 or st == 2 or (st == 1 and i == 8))
            ans += dp(pos - 1, 2, flag or i < x);
        else if (i == 3)
            ans += dp(pos - 1, 1, flag or i < x);
        else
            ans += dp(pos - 1, 0, flag or i < x);
    }
    if (flag) f[pos][st] = ans;
    return ans;
}

int calc(int x) {
    if( x <= 0 ) return 0;
    fill(a.begin(), a.end(), 0);
    int pos = 0;
    while (x) a[++pos] = x % 10, x /= 10;
    return dp(pos, 0, 0);
}

i32 main() {
    int l, r;
    while (true) {
        cin >> l >> r;
        if (l == 0 and r == 0) break;
        cout << calc(r) - calc(l - 1) << "\n";
    }
    return 0;
}

C - 诡异数字

状态\(f[pos][x][num]\)表示从最高位到第\(pos\)位，且第\(pos\)位是\(x\)，并且\(x\)已经出现了\(num\)次有多少种数字。

然后计算出当前位可以枚举的最大值，然后枚举当前位。

如果枚举的当前位为\(x\)就检查是是否超出相关的限制。

然后递归求解就好。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;


using vi = vector<i64>;
using pii = pair<i64, i64>;
#define int i64

const i64 inf = 1e18;
const i64 mod = 20020219;

vi limit, a(20);
vector f(20, vector(10, vi(20, -1)));

int dp(int pos, int x, int num, bool flag) {
    if (pos == 0) return 1;
    if (flag and f[pos][x][num] != -1) return f[pos][x][num];
    int n = flag ? 9 : a[pos];
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        if (i == x) {
            if (num + 1 > limit[x]) continue;
            ans = (ans + dp(pos - 1, x, num + 1, flag or i < n)) % mod;
        } else {
            ans = (ans + dp(pos - 1, i, 1, flag or i < n)) % mod;
        }
    }
    if (flag) f[pos][x][num] = ans;
    return ans;
}

int calc(int x) {
    if (x < 0) return 0;

    a.clear();
    int pos = 0;
    while (x) a[++pos] = x % 10, x /= 10;
    return dp(pos, 0, 0, false);
}

void solve() {
    f = vector(20, vector(10, vi(20, -1)));
    int l, r, n;
    cin >> l >> r >> n;
    limit = vi(10, inf);
    for (int x, len; n; n--)
        cin >> x >> len, limit[x] = min(limit[x], len);
    cout << (calc(r) - calc(l - 1) + mod ) % mod<< "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    for (cin >> T; T; T--)
        solve();

    return 0;
}

D - 7的意志

首先序列中所有的数一定都是\(7\)的倍数，所以题目要求实际上就是求多少个数是七的倍数且数位之和也是七的倍数。

所以设状态为\(dp[pos][x][y]\)前\(pos\)位摸\(7\)余\(x\)，且数位和模\(7\)余\(y\)复合条件的数有多少个。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;


using vi = vector<i64>;
using pii = pair<i64, i64>;

#define int i64

vi a(20);
vector f(20, vector(7, vi(7, -1)));

int dp(int pos, int x, int y, bool flag) {
    if (pos == 0) return x == 0 and y == 0;
    if (flag and f[pos][x][y] != -1) return f[pos][x][y];
    int ans = 0;
    int n = flag ? 9 : a[pos];
    for (int i = 0; i <= n; i++)
        ans += dp(pos - 1, (x * 10 + i) % 7, (y + i) % 7, flag or i < n);
    if (flag) f[pos][x][y] = ans;
    return ans;
}

int calc(int x) {
    int pos = 0;
    while (x) a[++pos] = x % 10, x /= 10;
    return dp(pos, 0, 0, false);
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    for (int l, r; true;) {
        cin >> l >> r;
        if (l == 0 and r == 0) break;
        cout << calc(r) - calc(l - 1) << "\n";
    }
    return 0;
}

E - Beautiful Numbers

设状态为\(f[pos][x][mod][sum]\)表示前\(pos\)位模数为\(x\)且位数模\(x\)的值为\(mod\)，位数之和为\(sum\)

然后只要枚举\(x\)从\(1\)到\(12\times 9\)即可。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;

using vi = vector<i64>;
using pii = pair<i64, i64>;

#define int i64

vi a(15);
vector f(15, vector(120, vector(120, vi(120, -1))));

int dp(int pos, int x, int mod, int sum, bool flag) {
    if (pos == 0) return x == sum and mod % x == 0;
    if( flag and f[pos][x][mod][sum] != -1 ) return f[pos][x][mod][sum];
    int ans = 0;
    int n = flag ? 9 : a[pos];
    for (int i = 0, tmp; i <= n; i++) {
        tmp = (mod * 10 + i) % x;
        ans += dp(pos - 1, x, tmp, sum + i, flag or i < n);
    }
    if (flag) f[pos][x][mod][sum] = ans;
    return ans;
}

int calc(int x) {
    int pos = 0;
    while (x) a[++pos] = x % 10, x /= 10;
    int ans = 0;
    for (int i = 1; i <= pos * 9; i++)
        ans += dp(pos, i, 0, 0, false);
    return ans;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    cin >> TC;
    for (int n, i = 1; i <= TC; i++) {
        cin >> n;
        cout << "Case " << i << ": " << calc(n) << "\n";
    }
    return 0;
}


#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;
using vi = vector<i64>;

#define int i64

const int T = 2520;
vi a(20), p, q(T + 1);
vector<vector<vi>> f;

int dp(int pos, int mod, int d, bool flag) {
    if (pos == 0) return mod % p[d] == 0;
    if (flag and f[pos][mod][d] != -1) return f[pos][mod][d];
    int ans = 0, pd = p[d];
    int n = flag ? 9 : a[pos];
    for (int i = 0; i <= n; i++)
        ans += dp(pos - 1, (mod * 10 + i) % T, i ? q[lcm(pd, i)] : d, flag or i < n);
    if (flag) f[pos][mod][d] = ans;
    return ans;
}

int calc(int x) {
    int pos = 0;
    while (x) a[++pos] = x % 10, x /= 10;
    return dp(pos, 0, 0, false);
}


void init() {
    for (int i = 1; i <= T; i++)
        if (T % i == 0) q[i] = p.size(), p.push_back(i);
    f = vector(20, vector(2600, vi(50, -1)));
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    init();
    int TC;
    cin >> TC;
    for (int l, r; TC; TC--) {
        cin >> l >> r;
        cout << calc(r) - calc(l - 1) << "\n";
    }
    return 0;
}

F - 美丽数

\(f[pos][mod][d]\)表示前\(pos\)位的数模\(2520\)，且前\(pos\)位的数的\(lcm\)为\(d\)。

为什么是\(2520\)，因为这是\([0,9]\)任取的\(lcm\)的最大值。

看起来值域很大，但是实际上的数只有不到 50 个，离散化一下就好了。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = int64_t;
using vi = vector<i64>;

#define int i64

const int T = 2520;
vi a(20), p, q(T + 1);
vector<vector<vi>> f;

int dp(int pos, int mod, int d, bool flag) {
    if (pos == 0) return mod % p[d] == 0;
    if (flag and f[pos][mod][d] != -1) return f[pos][mod][d];
    int ans = 0, pd = p[d];
    int n = flag ? 9 : a[pos];
    for (int i = 0; i <= n; i++)
        ans += dp(pos - 1, (mod * 10 + i) % T, i ? q[lcm(pd, i)] : d, flag or i < n);
    if (flag) f[pos][mod][d] = ans;
    return ans;
}

int calc(int x) {
    int pos = 0;
    while (x) a[++pos] = x % 10, x /= 10;
    return dp(pos, 0, 0, false);
}


void init() {
    for (int i = 1; i <= T; i++)
        if (T % i == 0) q[i] = p.size(), p.push_back(i);
    f = vector(20, vector(2600, vi(50, -1)));
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    init();
    int TC;
    cin >> TC;
    for (int l, r; TC; TC--) {
        cin >> l >> r;
        cout << calc(r) - calc(l - 1) << "\n";
    }
    return 0;
}

标签：int,pos,牛客,flag,vector,using,例题,dp,mod
From： https://www.cnblogs.com/PHarr/p/18103850

相关文章

  • 动态规划 选择dp：多重背包+多重背包puls----中专生刷算法
    不了解动态规划和选择dp的同学先看一下这两篇文章动态规划:选择dp及优化01背包问题-CSDN博客动态规划：完全背包问题----中专生刷算法-CSDN博客然后我们来做题普通题+进阶题，图文详解，化零为整的解决多重背包puls问题!!!多重背包输入格式输出格式输出一个整数，表示最......
  • c语言例题，判断闰年
    首先，我们要判断闰年，去写判断闰年的函数，那我们要先知道闰年是如何判断的。普通闰年的判断，一般是公历年份是4的倍数，且不是100的倍数的，以及公历年份是整百数的且必须是400的倍数的才是闰年。根据这些闰年的信息，我们可以构想，那闰年的判断方法就是：闰年必须是能被4整除，并且不能被100......
  • c语言例题，逐个打印数字
    今天来分享个比较简单的程序例题，也是比较经典的一个新手例题，逐个打印输入的数字。我们直接从主函数看起，先定义一个num变量，同时变量的类型是unsignedint，这个类型的意思是无符号的整型变量，unsigned（无符号）是用来修饰int的，说明了num这个变量只能是正数，然后我们用scanf输入想要的数......
  • CAN转PROFIBUS DP网关助力和利时PLC连接潍柴发电机组
    潍柴，作为柴油机行业的翘楚，其产品被广泛地应用于通信、石油、医疗、铁路以及农牧业等多个领域。 南通某项目有多台即将发往国外的潍柴发电机组，客户新需发电机组增加PROFIBUSDP接口以达到与上位系统和利时PLC实时通信。 该项目中，上位机系统需实时监控柴油机的转速，机油压力和......
  • 数位dp
    数位dphttps://leetcode.cn/problems/reverse-bits-lcci/description/publicintreverseBits(intnum){intmax=0;intdp1=0;intdp2=0;for(inti=0;i<32;i++){if((num&1)==1){......
  • 02-基于STM32F407MAC与DP83848实现以太网通讯六（IPerf网络速度测试）
    一、IPerf2网络测试工具Iperf2是一个用于测试网络带宽的工具。它是Iperf的旧版本，专注于提供基本的带宽测量功能。通过在客户端和服务器之间发送测试数据流并测量其性能，用户可以评估网络连接的速度和稳定性。Iperf2提供了一种简单而有效的方式来评估网络性能。IPerf3已经发布了，但......
  • 状压 dp
    引入先看一道例题：（可能r18）有\(N\)个男生和\(N\)个女生。小A喜欢磕CP，现在小A想要磕\(N\)对CP。不过每一个人都有自己的npy，也不是随随便便就能磕成一对。现在小A找到了你，要你求出有多少种磕CP的方式。我们显然可以暴力枚举每一个男生跟谁组CP然后判断是否合法......
  • 状压DP
    状压就是把几个维度压成一个维度,通常是按\(k\)进制来压缩如dp[(1<<1145141919810)]这样相当于开了\(1145141919810\)个只有\(0/1\)的维度,二进制下每一位表示这个维度运行逝世查询一个集合\(s\)的所有子集合扩散行for(inti=s;i<MAXN;i=(i+1)|s......
  • 设计模式DP-外观模式
    #include<stdio.h>#include<string.h>#include<stdlib.h>//定义子系统AtypedefstructsubsystemA{ void(*operationA)(structsubsystemA*subsystem);}SubsystemA;//定义子系统BtypedefstructsubsystemB{ void(*operationB)(structsubsystem......
  • 设计模式DP-责任链模式
    #include<stdio.h>#include<string.h>#include<stdlib.h>//定义业务处理者抽象类typedefstructHandler{ structHandler*nextHandler; void(*handleRequest)(structHandler*handler,intrequest); void(*setNextHandler)(structHandler*CurHan......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99