thumbnail
CSP历届初赛知识点总结(1)
此文章只收纳了初赛/第一轮中需要背诵的内容,对于如何计算、解题方法少有涉及。 最后附有易错点整理。 计算机的基本构成 CPU高速缓存是用于减少处理器访问内存所需平均时间的部件。 仅次于CPU寄存器。 其容量远小于内存,但速度却可以接近处理器的频率。 当处理器发出内存访问请求时,会先查看缓存内是否有请求数据。 硬盘是电脑的主要存储媒介之一。 高速缓存…
thumbnail
表达式树——初赛
表达式类型 表达式类型定义示例 前缀表达式(波兰式)运算符位于操作数之前$-*+3456$中缀表达式操作符以中缀的形式处于操作数中间$(3+4)*5-6$后缀表达式(逆波兰式)运算符位于操作数之后$34+5*6-$ 对于前缀表达式和后缀表达式来说,表达式是不需要用括号确定优先级的。 表达式原理 网上的很多教程都没有同时提到这三种表达式转化与表达式树…
thumbnail
计算机及OI发展史
计算机简史 史前时代 1623年:德国科学家契克卡德(W. Schickard)制造了人类有史以来第一台机械计算机,这台机器能够进行六位数的加减乘除运算。 1642年:法国科学家帕斯卡(B.Pascal)发明了著名的帕斯卡机械计算机,首次确立了计算机器的概念。 1674年:莱布尼茨改进了帕斯卡的计算机,使之成为一种能够进行连续运算的机器,并且提出了…
thumbnail
P1613 跑路 题解
传送门 题目理解与强调 给定一个有向图,共有 $n$ 个点和 $m$ 条边,存在自环的情况,每条边的长度都为 $1$ 。与一般题目不同的是,每走一步会走过 $2^k$ 个单位长度( $k$ 为任意自然数),我们要找的是从点 $1$ 到点 $n$ 中所有路径中需要步数最少的一条。 题解 排除错误算法 第一个想到的方法一定是找到从 $1$ 到 $n$ …
thumbnail
OI常用数列
Catalan数(卡特兰数) 实际问题 有 $2n$ 个人排成一行进入剧场。入场费 $5$ 元。其中只有 $n$ 个人有一张 $5$ 元钞票,另外 $n$ 人只有 $10$ 元钞票,剧院无其它钞票,问有多少种方法使得只要有 $10$ 元的人买票,售票处就有 $5$ 元的钞票找零? 一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处…
thumbnail
CF1607D Blue-Red Permutation 题解
传送门 题目强调与分析 翻译本题:给出一串长度为 $n$ 的字符串,其中只包含 "$B$" , "$R$" 两种字符,分别表示蓝色和红色,每一个字符还附有一个值,对于每次操作,你可以选择其中一个字符,对它的值进行以下两种修改: 如果颜色是红色,可以通过一次操作将它的值 $+1$ ;如果颜色是蓝色,可以通过一次操作将它的值 $-1$ ; 求:是否存在…
thumbnail
CF425A Sereja and Swaps 题解
传送门 题目理解与强调 给定了一个长度为 $n$ 的序列,允许有 $k$ 次交换,每次可以在序列中交换任意两个数,输出其交换后子串可能的最大值。 题解 这道题是一个思维题,对算法要求低,只要你学会了语言,拥有思维能力就可以做出这道题。 首先分析一下,这题目是要求一个子串的最大值,数据范围又是 $1 \le n \le 200$ ,所以我们可以分别枚…
thumbnail
左偏树
左偏树简介 左偏树是一种可并堆,也叫左偏堆、左倾堆、左氏堆,是一种树,具有堆的性质,可以实现快速合并。左偏树不是二叉搜索树,不是平衡树,因为它不满足中序有序性,无法进行二分搜索,因此不可以快速查找或者删除特定值的节点。 左偏树的性质 堆序性 节点的值大于或者等于(或小于等于)其左右子节点的值。对最大堆,父节点大,子节点小,每个结点的值都大于或者等于…
thumbnail
线性动态规划
线性动态规划规划简介 在所有动态规划中,线性动态规划的难度最低,同时线性动态规划也是所有动态规划的基础。 顾名思义,线性动态规划就是说动态规划的过程在“一条线”上进行,状态转移只有一个方向。最常见的线性$\rm{DP}$有子集和问题,$\rm{LIS}$问题,$\rm{LCS}$问题,字段和问题等。其实,线性$\rm{DP}$的用处不只如此,很大一…
thumbnail
权值线段树
前言 先前博客中写过“线段树”这一篇文章,而这一次是一种具有新的含义的线段树:权值线段树。 权值线段树简介 定义 权值线段树和普通线段树的形态类似,但是含义不同。普通线段树的节点通常存储该区间的最值或者和值,其节点范围是一个区间:权值线段树的节点存储该值域内的元素个数,其节点范围是一个值域。 基本结构 如图,对于每个节点的位置表示的是元素的值,然后…