1.题目一个整数总可以拆分为2的幂的和。例如：7可以拆分成7=1+2+4,7=1+2+2+2,7=1+1+1+4,7=1+1+1+2+2,7=1+1+1+1+1+2,7=1+1+1+1+1+1+1共计6种不同拆分方式。再比如：4可以拆分成：4=4,4=1+1+1+1,4=2+2,4=1+1+2。用f(n)表示nn的不同拆分的种数，例如f(7)=6。要求编写程序，读入n，输出f(n)mod10的9次。输入格式一个整数n。输出格式一个整数，表示f(n)mod10的9次。数据范围1≤N≤106输入样例：9输出样例：6AcWing3382.整数拆分2.思路这个题目也可以用背包dp求，2的n次幂就是每一

文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴区间DPUnique函数一、题目1、原题链接3996.涂色2、题目描述有n个砖块排成一排，从左到右编号为1∼n。其中，第i个砖块的初始颜色为ci。我们规定，如果编号范围[i,j]内的所有砖块的颜色都相同，且当第i−1和第j+1个砖块存在时，这两个砖块的颜色和区间[i,j]的颜色均不同,则砖块i和j属于同一个连通块。例如，[3,3,3]有1个连通块，[5,2,4,4]有3个连通块。现在，要对砖块进行涂色操作。开始所有操作之前，你需要任选一个砖块作为起始砖块。每次操作：任选一种颜色。将最开始选定的

Poweredby:NEFUAB-INB站直播录像！Link文章目录Acwing第91场周赛AAcWing4861.构造数列题意思路代码BAcWing4862.浇花题意思路代码CAcWing4863.构造新矩阵题意思路代码Acwing第91场周赛AAcWing4861.构造数列题意略思路将每个数的每一位全部拆出来即可代码/**@Author:NEFUAB-IN*@Date:2023-02-1818:59:30*@FilePath:\Acwing\91cp\a\a.cpp*@LastEditTime:2023-02-1819:03:25*/#includeusingnamespacestd;#d

文章目录算法总结-----到处搜集整理的，大多数来自acwingy总一、基础算法1、快速排序2、归并排序3、二分整数二分浮点数二分4、高精度算法高精度加法高精度减法高精度乘法高精度除法5、前缀与差分一维前缀和二维前缀和一维差分二维差分6、双指针算法最长连续不重复子序列子序列的目标和7、位运算8、离散化9、区间合并二、数据结构单链表双链表栈队列普通队列循环队列单调栈单调队列KMP算法Trie树Trie字符串统计求最大异或对并查集连通块中点的数量堆一般哈希字符串哈希STL简介三、搜索与图论树与图的存储树与图的遍历拓扑排序朴素dijkstra算法堆优化版dijkstra算法Bellman-Ford算

166.数独-AcWing题库题意数独是一种传统益智游戏，你需要把一个9×9的数独补充完整，使得数独中每行、每列、每个3×3的九宫格内数字1∼9均恰好出现一次。请编写一个程序填写数独。思路搜索+剪枝(优化搜索顺序、位运算)优化搜索顺序:很明显,我们肯定是从当前能填合法数字最少的位置开始填数字位运算:很明显这里面check判定很多,我们必须优化这个check,所以我们可以对于,每一行,每一列,每一个九宫格,都利用一个九位二进制数保存,当前还有哪些数字可以填写.lowbit:我们这道题目当前得需要用lowbit运算取出当前可以能填的数字.code+详细注释#include#definelowbit

差分矩阵1.题目2.基本思想3.代码实现1.题目输入一个nnn行mmm列的整数矩阵，再输入qqq个操作，每个操作包含五个整数x1,y1,x2,y2,cx1,y1,x2,y2,cx1,y1,x2,y2,c，其中(x1,y1)(x1,y1)(x1,y1)和(x2,y2)(x2,y2)(x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上ccc。请你将进行完所有操作后的矩阵输出。输入格式第一行包含两个整数nnn和mmm。第二行包含nnn个整数，表示整数序列。接下来mmm行，每行包含三个整数l，r，cl，r，cl，r，c，表示一个操作。输出格式共n行，每行

Acwing-基础算法课笔记之搜索与图论（spfa算法）一、spfa算法1、概述2、模拟过程3、spfa算法模板（队列优化的Bellman-Ford算法）4、spfa算法模板（判断图中是否存在负环）一、spfa算法1、概述单源最短路径算法，处理负权边的spfa算法，一般时间复杂度为O(m)O(m)O(m)，最坏为O(nm)O(nm)O(nm)。1、建立一个队列，初始化队列里只有起始点（源点）；2、在建立一个表格（dist）记录起始点到所有点的最短路径（该表格的初始值要赋为无穷大，该点到他本身的路径赋为0）；3、然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷

动态规划时间复杂度：状态数量*转移计算量线性DP一.数字三角形动态规划：  1.状态表示：    集合：f[i,j]表示所有从起点走到(i,j)的路径    属性：所有路径上的数字之和的最大值  2.状态计算：    如何得到f[i,j]?      从左边路径走到和从右边路径走到      从左边路径走到该点：f[i-1,j-1]+a[i,j]      从右边路径走到该点：f[i-1,j]+a[i,j];for(inti=0;i  for(intj=0;j    f[i][j]=-INF;赋初值的时候由于状态转移方程中会使用f[i-1]，为了避免f[-1]非法数据，三角形存储在1-n中考虑

目录前言Prime算法--加点法acwing-858 代码如下一些解释 Kruskal算法--加边法acwing-859并查集与克鲁斯卡尔求最小生成树 代码如下一些解释  前言之前学最短路的时候，我们都是以有向图为基础的，当时我们提到如果是无向图，只要记得两个顶点处都要加边就好了。而在最小生成树的问题中，我们所面临的大多都是无向图。这个姐姐👇对这两种算法的讲解非常清晰，没有代码部分，但是对于理解这两种算法的做法很有帮助，推荐看一下。 【数据结构图最小生成树Prime和Kruskal算法】截取自视频。感觉总结的很好，就搬过来啦(侵删) Prime算法--加点法prime算法也叫加点法，主要是通过

机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑高度为H(i)个单位。起初，机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E，下一步它将跳到第k+1个建筑。如果H(k+1)>E，那么机器人就失去H(k+1)−E的能量值，否则它将得到E−H(k+1)的能量值。游戏目标是到达第N个建筑，在这个过程中能量值不能为负数个单位。现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？输入格式第一行输入整数N。第二行是N个空格分隔的整数，H(1),H(