这篇文章将NOIP2022前备考经历归集到一起发出来。 NOIP2022停课冲刺 – Day 0 总结 总结 这是来到济南的第一天！ 到了济南之后，我也不知道老师是怎么想的，在历下区一个车水马龙、人来人往并且遍地都是连锁酒店、高级宾馆的地方选了一个没有门头的，冷清的，没落的，看上去及其寒酸的，只有两个不专业的，刚刚踏入社会模样的汉子经营的宾馆，美团…

题目传送门 题目 题目描述 广义的斐波那契数列是指形如 $a_n=p\times a_{n-1}+q\times a_{n-2}$ 的数列。今给定数列的两系数 $p$ 和 $q$，以及数列的最前两项 $a_1$ 和$ a_2$，另给出两个整数 $n$ 和 $m$，试求数列的第 $n$ 项 $a_n \bmod m$。 输入格式 输入包含一行六个整数…

矩阵构建 一个$m$行$n$列（记为$m\times n$）的矩阵用二维数组$matrix$存储，$matrix_{i,j}$表示第$i$行第$j$列元素的值。 结构体式构建 struct matrix{ ll m[101][101]; int c,r; matrix(){ memset(m,0,sizeof(m)); c=0,…

简介 区间动态规划本质上是线性动态规划的一种，但是其独特的思想自称体系，所以被单独提出来成为区间动态规划。 区间动态规划是以区间长度作为DP的阶段，以区间的左右端点作为状态的维度，一个状态通常由被它包含且比它更小的区间状态转移而来。阶段长度、状态左右端点、决策三者按照由外到内的顺序构成三层循环。 区间动态规划的经典运用 例题：石子合并 题目内容 在…

学习高阶差分之前，你需要先学习差分 高阶差分简介 记 $\Delta f(x)=f(x+1)−f(x)$。称 $\Delta f(x)$ 为 $f(x)$ 的一阶差分。 同理：记 $\Delta^n f(x)=\Delta^{n−1}f(x+1)−\Delta^{n−1}f(x)$ 。称 $\Delta^nf(x)$ 为 $f(x)$ 的 $n$ …

学习差分算法之前，你需要先学习前缀和算法 差分性质 差分可以理解为前缀和的逆运算。这种策略的定义是令 $$b_i=\begin{cases}a_i-a_{i-1} &,i\in[2,n]\\a_1&,i=1 \end{cases}$$ 所以，我们可以推导出一下性质： $a_i$的值就是$b_i$的前缀和，即： $$\sum^n_{i…

学习三分法之前，你需要先学习**二分法** 导入 学习三分法之前，大家应该都学会了二分法，二分法就是求解一个单调函数的零点，通俗一点，就是求解单调递增或递减序列的一个值，常用于二分查找（当然，你可以使用lower_bound或者upper_bound求解）、二分答案。 三分法就是二分法的变种，每次将一个区间分成三份，用于求解单峰函数的最值？什么是单…

题目传送门 题目 题目背景 bh1234666正在学习乘法！ 题目描述 bh1234666有一定数量的数字 $0 \sim 9$，现在他想让你寻找一种分配方案，将它们分成两个整数，使得他们的乘积 $p$ 最大。 由于bh1234666不喜欢太大的数，所以你只需要输出两个非负整数，使它们的乘积等于最大乘积 $p$，但是这两个整数 $0 \sim 9$…

题目传送门 题目 题目描述 给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。 输入格式 第一行一个整数 $L$，表示给出字符串的长度。 第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。 输出格式 仅一行，表示 $s_2$ 的最短长度。 样例…

本文章是对过去文章《KMP算法》的进一步解释与补充，使其语言叙述更加通俗简单。 KMP算法简介 算法来源 Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合…