-
背包问题刷题
整数划分一个正整数 n 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。 我们将这样的一种表示称为正整数 n 的一种划分。 现在给定一个正整数 n，请你求出 n 共有多少种不同的划分方法。 输入格式共一行，包含一个整数 n。 输出格式共一行，包含一个整数，表示总划分数量。 由于答案可能很大，输出结果请对 109+7 取模。 分析：用f... -
背包问题
01背包问题有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 分析：由于刚入门dp,所以我们从头到尾尽可能分析得详细（不会一来就写出优化的解法）。 动态规划问题有两个关键，一是状态表示，二是状态转移 就这道题而言，有两个变量，分别是v和w,所以... -
差分和前缀和刷题
中位数图好题指数：四星 给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 输入：第一行为两个正整数n和b 输出：输出中位数为b的连续子序列的个数 分析：这道题关键点是在于如何快速判断一个子序列中的中位数为b，对每一个子序列进行排序肯定不是最好的做法。假如一个连续子序列中的中位数为b，由于子序列的长度一定是奇数(2n... -
Vue基础学习笔记(一)
整体认识Vue3项目1、创建Vue3工程前置:NodeJS版本在18.0以上 使用官方脚手架创建Vue工程: 12npm create vue@latest#然后根据提示选择相关的组件 启动项目: 12npm install #安装相关依赖npmm run dev #运行项目 Tips: 所有的功能组件都可以在后续手动添加 npm install之前可以尝试配置国内镜像，拉取会快一点n... -
差分和前缀和算法
首先声明，差分和前缀和都的下标都建议从1开始，本文中将采取这种方式。 前缀和所谓前缀和算法，其实就是预处理从开头到某个下标为止的和，进而可以在O(1)的时间复杂度内快速求出[l,r]的和。 一维前缀和12S[i] = a[1] + a[2] + ... a[i]a[l] + ... + a[r] = S[r] - S[l - 1] 二维前缀和123S[i, j] = 第i行j列格子左上部分... -
算竞中常用的无穷大--0x3f3f3f3f
在算法竞赛中，我们常常需要用到设置一个常量用来代表“无穷大”。 比如对于int类型的数，许多人会使用INT_MAX来表示无穷大，但同时也面临着一个问题，那就是只要加一就会溢出，特别是对于某些带有返回值用递归（特别是动态规划的一些题目）来求解的题目，那么意味着这个特殊值不能做任何的运算，必须采用特判，不仅代码复杂还容易出错。 所以在算法竞赛中，常常使用0x3f3f3f3f来作为无穷大，主要有以... -
Trie树
Trie树（又叫前缀树或字典树）是一种树形结构，专门用于高效地存储和查找字符串集合，特别适合处理前缀相关问题，如自动补全、字符串匹配、前缀计数等。 代码模板: 12345678910111213141516171819202122232425262728293031//以最经典的字符串为例//一般是要么全是大写要么全是小写，就可以轻松映射到26个数字之中int son[N][N],cnt[N...
1