年度归档: 2021年

19 篇文章

thumbnail
P5482 [JLOI2011]不等式组 题解
题目传送门 题解 题目理解与强调 首先读入$n$,表示一共进行$n$次操作,每次操作可能有三种形式: Add a b c:表明要往不等式组添加一条不等式$ax+b>c$。Del i:代表删除第$i$条添加的不等式(最先添加的是第$1$条)。Query k:代表一个询问,即当$x=k$时,在当前不等式组内成立的不等式的数量。 注意以下事项:(细…
thumbnail
数论
整除 定义 设$a,b \in \mathbb{Z}$,如果存在$q \in \mathbb{Z}$,使得$b=aq$,那么就可以说$b$可以被$a$整除,记作$a \mid b$,且称$b$是$a$的倍数,$a$是$b$的约数(因数、除数) 性质 $a \mid b \Longleftrightarrow -a \mid b \Longleftr…
thumbnail
最小生成树
最小生成树的介绍 生成树的定义 在一个具有$ n $个点的无向连通图中,选出$ n-1 $条边将$ n $个点连接起来,构成一棵树。 注意:只有连通图才有生成树,非连通图只有生成森林。 最小生成树的定义 我们定义无向连通图的最小生成树为边权和最小的生成树。 最小生成树算法 Kruskal算法 实现 Kruskal算法是一种常见并且好写的最小生成树算…
thumbnail
P2246 SAC#1 – Hello World(升级版)题解
传送门 题目理解与强调 精简一下题意:本题给出一个字符串,在无视非字母、字母大小写的情况下,字符串 helloword 出现的次数。 题解 读入问题 在无其他问题的情况下,依然过不了,可以尝试我这一套读入程序。 char c; while((c=getchar())!=EOF){ } 解决主体问题 问题很简单,从第一个数字枚举整个字符串,先除去非字…
thumbnail
单调队列
前置知识 在此之前,你需要学习双端队列 简介 单调队列是用于解决滑动窗口类问题的数据结构,即在一个长度为 $n$ 的序列中求连续 $k$ 个数字中的最值问题,单调队列时间复杂度为 $O(n)$ ,这比「ST表」与「线段树」算法更优化。 更广泛地,在以下两种情况时,可以考虑使用单调队列优化。 状态转移方程形如 $dp_i=\min_{0\le j \…
thumbnail
平衡二叉树
二叉搜索树的插入、查找、删除等操作的效率与树高成正比,因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种,例如AVL树、Treap、伸展树(Splay)、SBT、红黑树等。 Treap Treap简介 特点与作用 Treap,即Tree+Heap,又叫做树堆,它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性,输入的序列不…
thumbnail
树链剖分
树链剖分简介 链剖分 指对树的边进行划分的一种操作,目的是减少在链上修改、查询等操作的复杂度。链剖分分三类:轻重链剖分、虚实链剖分和长链剖分。 树链剖分思想 通过轻重链剖分将树分为多条链,保证每个节点都属于且只属于一条链。树链剖分时轻重链剖分,节点到重儿子,也就是到子树节点最多的儿子之间的路径就是重链。每条重链都相当于一段区间,把所有重链首尾相接组…
thumbnail
P3956 [NOIP2017 普及组] 棋盘 题解
题目传送门 题解 题目理解与强调 题目给出一个$m \times m$的一个棋盘,每个格子有三种颜色状态:红色、黄色、无色。每次从$(1,1)$开始走,可以走上下左右四个方向,最终走到$(m,m)$。 当从一个格子走向另一个格子时,如果两个格子的颜色相同,那么不需要花费金币;如果不同,则需要花费$1$个金币。另外, 可以花费$2$个金币让下一个无色…
thumbnail
P6037 Ryoku 的探索 题解
题目传送门 题解 题目理解与强调 题目给出的是一个$n$个点$n$条边的无向连通图,$n$个点$n$条边可以看出这是一个基环树,树上每个点都有两种权值,分别表示美观度和长度,我们从一个点出发的时候,要找美观度最大的一条边走,如果那个点已经被走过了,就不走了,换向另一条边,过程类似于DFS。 思路分析 既然是在一棵基环树上遍历每个点,走过这$n$个点…
thumbnail
CF1084C The Fair Nut and String 题解
题目传送门 题解 题目理解与强调: 这道题目含有一条只包含小写字母的字符串。要求能够找到多少个 子序列 满足形式 $ a,b,\ldots,a,b $ 思路分析: 这道题是一道计数题。 很简单地,我们可以得出结论:题目的答案与字符串$ s $中的'$ a,b,\ldots,a,b $'的数量与位置有关,当我们读取到'$ a $'时,首先要…