maven
操作系统
云计算
Table API
测试工程师
rviz
unity
网络攻击模型
位置式PID
资源
字符串替换
gaussdb
exe
计算机毕业设计
科研绘图
区别
TFT图片提取
asio
多版本并发控制机制
webdav
数位dp
2024/4/12 10:27:29
第 111 场LeetCode 双周赛题解
A 统计和小于目标的下标对数目 数据量小，直接枚举数对 class Solution {
public:int countPairs(vector<int> &nums, int target) {int n nums.size();int res 0;for (int i 0; i < n; i)for (int j 0; j < i; j)if (nums[i] nums[j] < tar…
acwing 1083 Windy数
题面 题解(数位DP) 代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>using namespace std;
const int N 11;int f[N][N]; //i位数且最高位是j的Windy数void init()…
HDU4734，F(x)（数位DP+优化）
本题思路和DP状态不难求，比较难的是该怎么优化。 数位DP的优化可参考下面的博客： https://blog.csdn.net/wust_zzwh/article/details/52100392 简单的说，一般数位DP的优化有两种方法： ①将memset放置在多组数据外面，即…
洛谷P4317 花神的数论题（数位DP）
题意：给你一个数N，求出[1,N]中所有的数的二进制中1的个数的连乘。 刚开始看到这道题DP状态都不太好找，但因为之前做过洛谷的另一道“同类分布”的题，后来就有了点思路。 因为这道题DP状态不太好定义，不太好保存状态&am…
acwing 1081 度的数量
题面 题解 (数位DP) 题意有点难受，假设K2,B2 ,那么要想满足题中要求，在2进制下每一位只能填0或者1，比如 20 (10100)2,只有这样才能转化为 24 2 2 , 再比如K2，B8,那么9在8进制下就表示为11， 98081 ,但是17在8进制下表…
acwing 1085 不要62
题面 题解 代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>using namespace std;
const int N 10;int f[N][N]; //i位数,最高位是j的满足条件的方案数void init() {for (int i 0; i <…
acwing 1086 恨7不成妻
题面 题解 代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;
typedef long long ll;
const int N 20, P 1e9 7;struct F {int s0; //个数(0次方)int s1; //和(1次方)int s2; //平方和…
acwing 1082 数字游戏
题面 题解(数位DP) 代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>using namespace std;
const int N 15;int n;
int f[N][N]; //f[i][j]表示一共有i位，且最高位填j的数的个数…
B-number（ 数位 DP ）
B-number
A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string “13” and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wq…
hdu2089:不要62
Problem Description杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可…
动态规划初步-数位上的动态规划
简介
数位DP是一类常考的题，虽然现实意义不算很大（大家时间因为种种原因特别多，暴力即可；仅个人看法），但是分数是很重要的。这类题目一般都不会隐藏自己的尾巴，非超级无敌变态爆炸难的题应该一…
hdu 2089 不要62[数位dp入门]
又一次开始搞数位dp了，一直在拖，希望这次能够彻底学会
#include <bits/stdc.h>
using namespace std;
typedef long long ll;int a[20];
ll dp[20][2];//不同的题目状态不同
ll dfs(int pos,int pre,int sta,bool limit)
{if(pos-1)return 1;if(!…
【上分日记】第380场周赛（数位dp+ KMP + 位运算 + 二分 + 双指针 ）
文章目录 前言正文1.3005. 最大频率元素计数2.3007.价值和小于等于 K 的最大数字3.3008. 找出数组中的美丽下标 II 总结尾序 前言 本场周赛，博主也只写出两道题(前两道, hhh菜鸡勿喷)，第三道涉及位运算 ，数位dp，第四道涉及KMP。 下…
【leetcode】动态规划数位DP
这篇博客通过一道经典的题目来学习数位DP。
1. 题目描述
题目链接：902. 最大为 N 的数字组合 2. 思路分析
方法一：
由于题目给定的 digits 不包含 0，因此相当于只需要回答使用 digits 的数值能够覆盖 [1,x]范围内的多少个数字。
先将字符…
hdoj 3555(数位dp，详细注释)
数位dp可以解决类似这样一道给你上下界，求里面符合要求的数字，暴力肯定超时的.下面给出带注释的代码
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
ll dp[20][2];
ll dight[20];ll dfs(ll len,bool…
牛客寒假算法基础集训营3_G处女座和小姐姐（三）（数位dp）
题目链接：https://ac.nowcoder.com/acm/contest/329/G
题目大意：输入两个数l，r，求l到r之前所有不含6的数有几个。
代码：
#include <bits/stdc.h>
using namespace std;
typedef long long ll;int a[20];
ll d…
Bomb （ 数位 DP ）
Bomb
The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the bl…
不要62-HDU - 2089(数位dp板题)
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。 杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机…
【WC2015模拟2.6】Circle
Description
一开始有个n个在[0,2^m)区间内的数。 每一秒每一个数将会1，然后对2^m取模。 求在[1,T]秒内，有多少个时间，使得这n个数的异或值为S。 n<10^5,m<50,T<10^16
Solution
很显然的与位运算有关的题目。 首先我们就相当…
不要62（ 数位 DP ）
不要62
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。 杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别…
洛谷P2602 [ZJOI2010]数字计数（数位DP）
题意：给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。 状态：dp[i,j,k]:枚举到第j位数时，数字i出现的次数为k次的所有数字中i出现的总次数。 边界：dp[0~9,0,k]k。 状态转移&am…
牛客小白月赛7，D（数位DP+暴力）
题意：给定一个m,n，求出m以后第n个是7的倍数或者数字包含7的数。 这是刷数位DP时刷到的，有点懵一开始，这个怎么数位DP。。。思索了一下，弄了个比较曲线的做法：用数位DP夹逼。。。。 代码如下：
#…
![数位dp，蓝桥杯2021国赛 [二进制问题]](https://img-blog.csdnimg.cn/direct/afc73a324a2e42ed93d483849e9299b0.png)
数位dp，蓝桥杯2021国赛 [二进制问题]
一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
3.二进制问题 - 蓝桥云课 (lanqiao.cn) 二、解题报告
1、思路分析
数位dp板子题
定义状态f[i][j]为剩余i位，前缀有j个1的状态下，二进制位有k个1的数字个数
那么nxtstate cur (pr…
HDU4507，吉哥系列故事——恨7不成妻（数位DP）
推荐博客： https://www.cnblogs.com/bxd123/p/10974247.html
关键点：( i j )2i2 2 * i * j j2, 1231 * 102 2 * 101 3. 根据上面两个式子，我们可以推出，我们需要维护两个值，一个是已经枚举出来的所有数的总和&am…
HDU3652，B-number（数位DP）
用数位DP。 状态：dp[i,j,k,state]表示枚举到第i位时，前一位数字为j，前面各个数字组成的数mod13k，当前是否包含“13”串（state0否state1是），符合条件的数字的总个数 边界：return (sta…
GDKOI2016 Day2 T2 QT与泰剧
T2 QT与泰剧 给出上界S和下界T，求在T1~S中，模3与S同余并且不全由质数组成的数的个数。 典型数位DP，答案即为⌊S−T23⌋−ans。ans为不合法的数的个数。注意细节。
#include<cstdio>
#include<cstring>
#include<algorithm>…
2019牛客暑期多校训练营（第七场）H（数位DP）
满足要求的<x,y>有两种情况： 1.x&y >C; 2.x^y < C; 其中1<x<A, 1<y<B. 涉及到位运算，我们首先把A,B,C写成二进制，其次，要明确的一点就是，我们任找某个x,y，假设我们现在在进行&…
HDU3709，Balanced Number（数位DP）
题意：一个数是balanced number当且仅当它跟4139（位置编号3210）一样，当我们将pivot（不知是啥）的位置取在3的位置1时，左边4,1到3的距离和为4 * 2 1 * 1 9，右边9到3的距离9 * 1 9&am…
洛谷P2657 [SCOI2009]windy数（数位DP）
数位DP入门题，关于数位DP，可以参考下面几个博客： https://walesexcitedmei.github.io/2018/10/30/浅浅浅谈-数位-DP/ https://www.luogu.org/blog/virus2017/shuweidp https://blog.csdn.net/wust_zzwh/article/details/52100392 个人觉得第一…
acwing 1084 数字游戏II
题面 题解(数位DP)
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>using namespace std;
const int N 11, M 100;int P;
int f[N][N][M]; // i位数,最高位是j,…
HDU2089，不要62（数位DP）
可以用数位DP，也可以暴力打表，两种都可以。 状态：dp[i,j]表示枚举到第i位时，前一位（即i1位）的数字为j时的方案数。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include…
洛谷P3413 SAC#1 - 萌数（数位DP）
题目是说回文子串长度>2就是一个萌数，那么只要判断两种情况就好：aa,aba。 状态：dp[i,j,k,state0~1]表示枚举到第i位数，前一位（即i1）数字为j，前两位（即i2）为k时&#x…
2019牛客暑期多校训练营（第七场） H Pair（数位dp）
链接：https://ac.nowcoder.com/acm/contest/887/H
题意：T组样例。每组样例给出A、B、C三个数，从[1,A]选出一个数x、从[1,B]选出一个数y，使得x&y>C或x^y<C。问这样的数对有多少个？
思路：纯暴力的…
bzoj 4521: [Cqoi2016]手机号码
Description 人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自…
Codeforces 288E Polo the Penguin and Lucky Numbers
题目大意：
我们定义只含有4或者7的数为“幸运数”
现在给你L,R，问你L到R之间的幸运数的和
答案对10^97取模
(1<l<r<10^100000) 看到数字第一个想到的就是数位DP。
我们用sx[i][4]表示长度为i且开头为4的幸运数的和
用sx[i][7]表示长度为…
牛客OI周赛2-提高组，好朋友（数位DP+逆向思维）
题意：有t次询问，每次询问[l,r]区间内子序列含007的数的个数，最终输出所有询问的答案的异或和。 分析： 数位DP很明显，但子序列含007的情况比较复杂，想了挺久都没想到怎么做，于是正难则反…
数位DP 详解及其案例实战Ⅱ
零. 案例引入
1.案例引入 leetcode233. 数字 1 的个数
2.暴力解
3.引出数位DP
一. 数位DP简单介绍
1.数位DP的本质
2.数位DP适合处的问题
3.数位DP在实际使用面临什么难点
二. 数位DP典型模板和技巧
1.模板
2.模板解读
3.相关技巧总结
三. 数位DP案例
1.leetcode…
【数位dp】【C++算法】600. 不含连续1的非负整数
作者推荐
【矩阵快速幂】封装类及测试用例及样例
涉及知识点
数位dp
LeetCode600. 不含连续1的非负整数
给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。 示例 1: 输入: n 5 输出: 5 解释: 下…
【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字
作者推荐
视频算法专题
本文涉及知识点
动态规划汇总
LeetCode:1012. 至少有 1 位重复的数字
给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。 示例 1： 输入：n 20 输出：1 解释：具有至…
数位小孩＜每日一题＞(数位dp)
题目： 题目链接：登录—专业IT笔试面试备考平台_牛客网https://ac.nowcoder.com/acm/contest/23480/D 思路：
数位dp的题目一般都是套模板
在原模板的基础上
根据题目条件进行改变
从而达到题目要求
下面对三个题目要求进行分析 要满足题目…
bzoj 1833: [ZJOI2010]count 数字计数
Description 给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。Input 输入文件中仅包含一行两个整数a、b，含义如上所述。Output 输出文件中包含一行10个整数，分别表示0-9在[a,b]中出现了多少次。Sampl…
【数位dp】P4999 烦人的数学作业
数位dp的基础题，复习模板用！！ 代码
#include<bits/stdc.h>
using namespace std;
typedef long long ll;
const ll mod1e97;
ll f[20][200],a[20];
ll dfs(int x,int sum,int top)
{if(!x) return sum;if(!top && f[x][sum]&g…