算法训练 K好数 （详解：题目理解+解题思路）-程序员宅基地
题目理解
1.题目要求的是“L位K进制数中的K好数 的数目”。怎么理解？
首先，要知道K进制数它的取值范围为[0，K-1]，如4进制只能取[0,3];16进制为[0,15]等。
其次，明白什么是“L位K进制数”。如：“2位4进制数”，它是指这个数是个两位数，其中个位数是4进制数（即从[0,3]中取一个数作为个位），十位数也是4进制数。同理，“3位7进制数”则指这个数是个3位数，其中个位、十位、百位都是7进制数。
最后，按K好数的要求（任意相邻的两位不是相邻的数字）统计就能得到结果。
2.题目中为啥给出“由于数很大……输出取模后的值”这一条件？
首先，要明白“取模运算只有对象是整数间时才等于取余运算”。
推荐：取模运算有什么用？https://wenwen.sogou.com/z/q795314708.htm
最后，在数据规范与约定中，我们知道1K
100，1
L
100。我们假设K取100，L也取100。那么在100位100进制数中不考虑100好数的情况下，粗略一算，它的数就有100的100次方。肯定超过了int，long long。这时题目告诉我们取模来减小我们的负担。（感谢啊）
到这里相信你应该理解题目的意思了，请自己思考看看。（如果你觉得我写的还算明白，请点个赞鼓励一下，不胜感激。）
3.这里以2位4进制数和3为4进制数为例。
满足条件的2位4进制数：
1 1、1 3 、2 0 、2 2 、 3 0、 3 1、 3 3
共7个
满足条件的3位4进制数：
1 1 1、1 1 3、
1 3 0、1 3 1 、1 3 3、
2 0 0、 2 0 2、 2 0 3、
2 2 0、 2 2 2、
3 0 0、 3 0 2、 3 0 3、
3 1 1、 3 1 3、
3 3 0、 3 3 1、 3 3 3
共18个。
解题思路
用dp[i][j]=dp[i][j]+dp[i-1][k]来做。解释一下：这里的i 代表所在的位数（i=0代表个位，i=1代表十位，以此类推）。j 代表取K进制数的一个数(如果是4进制数，那么j取[0,3]中的一个数)。k和j同一个意思。整个式子的意思是当前位置的数总数=当前位置的数的数目+前一个位置的数的总数。
以2位4进制数的4好数为例：
dp[1][0]=dp[1][0]+dp[0][k]; k取[0,3] // 十位为0时，添上个位所取得数，看是否满足K好数。结果：dp[1][0]存的是十位为0时的满足4好数的个数，即：1 1、1 3 两种情况。
dp[1][1]=dp[1][1]+dp[0][k]; //同上理解
dp[1][2]=dp[1][2]+dp[0][k];
dp[1][3]=dp[1][3]+dp[0][k];
题目
附上代码
#include<iostream>
#include<cmath>
using namespace std;
int dp[1000][1000];
const int MOD=1000000007;
int main()
{
int sum=0;
int CountK(int,int,int);
int K,L;
cin>>K>>L;
if(K==1&&L==1) //这里对1位1进制的个数为啥不是1表示不理解
cout<<0<<endl;
else if(K>1&&L==1)//1位的K进制的K好数总数就是K个
cout<<K<<endl;
else if(L>1)
cout<<CountK(L,K,sum)<<endl;
return 0;
}
int CountK(int length,int range,int sum)
{
for(int i=1;i<range;i++)
{
dp[0][i]=1;
}
for(int i=1;i<length;i++)
{
for(int j=0;j<range;j++)
{
for(int k=0;k<range;k++)
{
if(abs(j-k)!=1)
{
if((j-1)==0&&k==0)//排除首位为0的情况
continue;
dp[i][j]=dp[i][j]+dp[i-1][k];
dp[i][j]%=MOD;
}
}
}
}
for(int i=0;i<range;i++)
{
sum+=dp[length-1][i];
sum%=MOD;
}
return sum;
}
智能推荐
设置Socket的选项_socket nodely-程序员宅基地
文章浏览阅读4.6k次。Socket有以下几个选项。TCP_NODELY:表示立即发送数据SO_RESUSEADDR:表示是否允许重用Socket所绑定的本地地址SO_TIMEOUT:表示接收数据时的等待超时时间SO_LINGER:表示当执行Socket的close()方法时，是否立即关闭底层的SocketSO_SNFBUF:表示发送数据的缓冲区大小SO_RCVBUF:表示接受数据的缓冲区大小SO_KE_socket nodely
Snap7 西门子S7系列PLC的通信库 简介_snap7官网-程序员宅基地
文章浏览阅读3.2w次，点赞29次，收藏203次。目录简介参考Snap7 简介Snap7 用途适用系统支持语言西门子S7通信介绍Snap7 组件Sanp7 APISnap7 PythonSnap7 安装PLC设置连接PLC读取数据发送数据Sanp7 C/C++node.js简介最近在开发一个项目，作为技术帝，已经完成工艺、机械设计的设计，项目过多，也是为了让自己更加????叉，就开始尝试做电气制图和PLC编程。结合物联网的发展，有一种想法，将数据传..._snap7官网
HashMap和ConcurrentHashMap底层实现原理以及JDK1.7和1.8之间的区别_concurrent hash map,在jdk1.7和1.8的底层原理有什么区别,为什么1.8要做-程序员宅基地
文章浏览阅读554次，点赞2次，收藏6次。HashMap原理：HashMap主要由数组和链表组成，他不是线程安全的。核心的点就是put插入数据的过程，get查询数据以及扩容的方式。put元素： 在put插入的时候会根据key的hashcode去做hash运算得到一个index值（利用元素key的哈希值对数组长度-1按位与操作得到，为什么不用取模%运算呢？因为java的%比位运算慢10倍左右），根据index值放入数组的相应位置。每一个节点（Node）都会保存自身的hash、key、value、以及下个节点为什么要有链表： 因为不同的key可_concurrent hash map,在jdk1.7和1.8的底层原理有什么区别,为什么1.8要做出这
苹果开发者账号（公司级）和邓白氏编码（D-U-N-S）申请记录（2015.06）_legal entity name d-u-n-s庐 number-程序员宅基地
文章浏览阅读3.5w次。图文记录苹果开发者账号（公司级）和邓白氏编码（D-U-N-S）申请流水过程申请于2015.05-06份，算是较新的版本，有需要可以参考下_legal entity name d-u-n-s庐 number
【持续更新，后面带JavaWeb案例】IDEA2023创建JavaWeb项目的方法以及JavaWeb实现购物车案例_idea2023社区版提供web开发吗-程序员宅基地
文章浏览阅读1.1k次，点赞2次，收藏8次。哎呀我的妈妈咪呀，我来讲讲我为啥要写这篇文章。我tm之前用IDEA写Java 电脑项目习惯了，创建项目的时候就直接 新建项目，然后Java > Maven啥的，弄一大堆，然后写好页面和Servlet之后运行tomcat之后，用localhost:8080/项目名称/servlet名直接是找不到资源，搞我心态搞了现在tmb一个月，现在我总算明白了，那个初始模板可能有些插件/模块啥的自己不知道引用哪些，所以先开始总是报红，然后在web.xml里面写也tmd爆红，我真是服了！_idea2023社区版提供web开发吗
黑盒测试简介以及方法简介_一个循环条件为≤时,却错误写成<,用哪种测试方法能够找到这个错误-程序员宅基地
文章浏览阅读2w次，点赞9次，收藏49次。引言：黑盒测试是从软件的外部对软件实施测试，也常形容为闭着眼睛测试。在接下来的学习中将介绍几种常用的黑盒测试方法，其中包括等价类划分、边界值分析、决策表测试等。1. 等价类划分测试等价类划分是一种典型的黑盒测试方法，该方法完全不考虑程序的内部结构，只根据对软件的要求和说明，即需求规格说明，把程序输入域划分成若干个部分，然后从每个部分中选取少数有代表性的数据作_一个循环条件为≤时,却错误写成<,用哪种测试方法能够找到这个错误
随便推点
课设——学生成绩管理系统.exe_学生成绩统计系统exe-程序员宅基地
文章浏览阅读1k次，点赞3次，收藏7次。一、系统需求分析1、总需求设计一个实用的小型学生成绩管理程序，具有查询，检索和删除等功能。2、具体需求(1)学生基本信息、考试科目及成绩的信息录入。(2)已有学生信息的显示。(3)学生基本信息的读取和保存输入数据等功能(4)学生基本信息的查询与修改。可以对已有的学生信息进行修改。(5)学生基本信息的删除。(6)对该班各科成绩进行分析；对学生成绩进行统计（包括最高分，最低分，排序，平均成绩，及格率和需要补考的学生）具体源码详见（链接）二、总体设计1、定义四个类Student类、S_学生成绩统计系统exe
使用pdf.js不依赖任何activeX控件_pdfjs view.html怎么传入file文件参数-程序员宅基地
文章浏览阅读971次。使用pdf.js可以直接在浏览器上浏览PDF文件，而且不依赖任何activeX控件~ github上下载生成好的pdf.js工程本机项目：PDFPrintTest下demoviewer.js中要增加CORS跨域访问限制判断，否则不能跨域访问，或者在HOSTED_VIEWER_ORIGINS数组中增加viewer.html所在主机IP:PORT。作为不校验同源的ip_pdfjs view.html怎么传入file文件参数
Python 中 float 计算精度问题_python float 精度-程序员宅基地
文章浏览阅读7.5k次，点赞3次，收藏12次。浮点数不能精确的表示十进制数，并且即使是最简单的数学运算也会产生误差。该错误是由于浮点数的存储方式引起的。_python float 精度
HT合泰单片机入门教程（第一章 HT单片机环境搭建）-程序员宅基地
文章浏览阅读1.3w次，点赞21次，收藏115次。HT合泰单片机入门教程系列文章目录前言一、合泰单片机的优势二、HT-IDE3000安装1.HT-IDE3000下载2.HT-IDE3000安装总结系列文章目录# 第一章 HT单片机环境搭建目录系列文章目录前言一、合泰单片机的优势二、HT-IDE3000安装1.HT-IDE3000下载2.HT-IDE3000安装总结前言工作已经很长一段时间，虽然还是菜鸟一只。但还是有点心得体会。写合泰单片机系列教程的原因：一、是为了记录自己学习过程和学习经历（ps：当初毕业进公司接触到的第一个就是为一款已_合泰单片机入门教程
Android之如何获取手机中所有的传感器_导出智能手机中的传感器数据-程序员宅基地
文章浏览阅读7.1k次。传感器是第二代智能手机的重要标志之一。可以毫不客气地说，现在市面上的Android手机和平板电脑（TV除外）都内置了传感器。否则很多游戏和应用就无法使用了。Android SDK支持的传感器并不是每一部Android设备都支持所有的传感器。大多数Android设备只支持一部分传感器。例如，方向传感器（电子罗盘）、重力传感器（屏幕翻转、赛车游戏等）。动作（Motion）传感器环境（E_导出智能手机中的传感器数据
基于R的ggplot2包画KEGG富集通路气泡图_KEGGdot_ggplot 高低通路kegg-程序员宅基地
文章浏览阅读6.4k次，点赞2次，收藏16次。背景**基于公司已给出的结果上做出调整（公司只给出了top10），画KEGG富集通路的气泡图，初始文件如下图代码演示> getwd() #显示工作目录> setwd() #如果上述显示不是想要的路径，可以新建一个文件夹然后设置成工作目录，方便一些原始文件以及结果图片的存放> install.packages("ggplot2",destdir="D:/RData/R-win-4.0.2/R-4.0.2/R-packages",lib="D:/RData/R-win-4.0.2_ggplot 高低通路kegg