月度归档: 2022年11月

12 篇文章

thumbnail
NOIP停课日志总结
这篇文章将NOIP2022前备考经历归集到一起发出来。 NOIP2022停课冲刺 – Day 0 总结 总结 这是来到济南的第一天! 到了济南之后,我也不知道老师是怎么想的,在历下区一个车水马龙、人来人往并且遍地都是连锁酒店、高级宾馆的地方选了一个没有门头的,冷清的,没落的,看上去及其寒酸的,只有两个不专业的,刚刚踏入社会模样的汉子经营的宾馆,美团…
thumbnail
P1349 广义斐波那契数列 题解
题目传送门 题目 题目描述 广义的斐波那契数列是指形如 $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$。 输入格式 输入包含一行六个整数…
thumbnail
矩阵
矩阵构建 一个$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,…
thumbnail
区间动态规划
简介 区间动态规划本质上是线性动态规划的一种,但是其独特的思想自称体系,所以被单独提出来成为区间动态规划。 区间动态规划是以区间长度作为DP的阶段,以区间的左右端点作为状态的维度,一个状态通常由被它包含且比它更小的区间状态转移而来。阶段长度、状态左右端点、决策三者按照由外到内的顺序构成三层循环。 区间动态规划的经典运用 例题:石子合并 题目内容 在…
thumbnail
高阶差分
学习高阶差分之前,你需要先学习差分 高阶差分简介 记 $\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$ …
thumbnail
差分
学习差分算法之前,你需要先学习前缀和算法 差分性质 差分可以理解为前缀和的逆运算。这种策略的定义是令 $$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…
thumbnail
三分法
学习三分法之前,你需要先学习**二分法** 导入 学习三分法之前,大家应该都学会了二分法,二分法就是求解一个单调函数的零点,通俗一点,就是求解单调递增或递减序列的一个值,常用于二分查找(当然,你可以使用lower_bound或者upper_bound求解)、二分答案。 三分法就是二分法的变种,每次将一个区间分成三份,用于求解单峰函数的最值?什么是单…
thumbnail
P8482 「HGOI-1」Number 题解
题目传送门 题目 题目背景 bh1234666正在学习乘法! 题目描述 bh1234666有一定数量的数字 $0 \sim 9$,现在他想让你寻找一种分配方案,将它们分成两个整数,使得他们的乘积 $p$ 最大。 由于bh1234666不喜欢太大的数,所以你只需要输出两个非负整数,使它们的乘积等于最大乘积 $p$,但是这两个整数 $0 \sim 9$…
thumbnail
P4391 [BOI2009]Radio Transmission 无线传输 题解
题目传送门 题目 题目描述 给你一个字符串 $s_1$,它是由某个字符串 $s_2$ 不断自我连接形成的。但是字符串 $s_2$ 是不确定的,现在只想知道它的最短长度是多少。 输入格式 第一行一个整数 $L$,表示给出字符串的长度。 第二行给出字符串 $s_1$ 的一个子串,全由小写字母组成。 输出格式 仅一行,表示 $s_2$ 的最短长度。 样例…
thumbnail
重述:KMP算法
本文章是对过去文章《KMP算法》的进一步解释与补充,使其语言叙述更加通俗简单。 KMP算法简介 算法来源 Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合…