题目传送门 题解 题目理解与强调 首先读入$n$，表示一共进行$n$次操作，每次操作可能有三种形式： Add a b c：表明要往不等式组添加一条不等式$ax+b>c$。Del i：代表删除第$i$条添加的不等式（最先添加的是第$1$条）。Query k：代表一个询问，即当$x=k$时，在当前不等式组内成立的不等式的数量。 注意以下事项：（细…

整除 定义 设$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…

最小生成树的介绍 生成树的定义 在一个具有$ n $个点的无向连通图中，选出$ n-1 $条边将$ n $个点连接起来，构成一棵树。 注意：只有连通图才有生成树，非连通图只有生成森林。 最小生成树的定义 我们定义无向连通图的最小生成树为边权和最小的生成树。 最小生成树算法 Kruskal算法 实现 Kruskal算法是一种常见并且好写的最小生成树算…

传送门 题目理解与强调 精简一下题意：本题给出一个字符串，在无视非字母、字母大小写的情况下，字符串 helloword 出现的次数。 题解 读入问题 在无其他问题的情况下，依然过不了，可以尝试我这一套读入程序。 char c; while((c=getchar())!=EOF){ } 解决主体问题 问题很简单，从第一个数字枚举整个字符串，先除去非字…

前置知识 在此之前，你需要学习双端队列 简介 单调队列是用于解决滑动窗口类问题的数据结构，即在一个长度为 $n$ 的序列中求连续 $k$ 个数字中的最值问题，单调队列时间复杂度为 $O(n)$ ，这比「ST表」与「线段树」算法更优化。 更广泛地，在以下两种情况时，可以考虑使用单调队列优化。 状态转移方程形如 $dp_i=\min_{0\le j \…

二叉搜索树的插入、查找、删除等操作的效率与树高成正比，因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种，例如AVL树、Treap、伸展树（Splay）、SBT、红黑树等。 Treap Treap简介 特点与作用 Treap，即Tree+Heap，又叫做树堆，它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性，输入的序列不…

树链剖分简介 链剖分 指对树的边进行划分的一种操作，目的是减少在链上修改、查询等操作的复杂度。链剖分分三类：轻重链剖分、虚实链剖分和长链剖分。 树链剖分思想 通过轻重链剖分将树分为多条链，保证每个节点都属于且只属于一条链。树链剖分时轻重链剖分，节点到重儿子，也就是到子树节点最多的儿子之间的路径就是重链。每条重链都相当于一段区间，把所有重链首尾相接组…

题目传送门 题解 题目理解与强调 题目给出一个$m \times m$的一个棋盘，每个格子有三种颜色状态：红色、黄色、无色。每次从$(1,1)$开始走，可以走上下左右四个方向，最终走到$(m,m)$。 当从一个格子走向另一个格子时，如果两个格子的颜色相同，那么不需要花费金币；如果不同，则需要花费$1$个金币。另外， 可以花费$2$个金币让下一个无色…

题目传送门 题解 题目理解与强调 题目给出的是一个$n$个点$n$条边的无向连通图，$n$个点$n$条边可以看出这是一个基环树，树上每个点都有两种权值，分别表示美观度和长度，我们从一个点出发的时候，要找美观度最大的一条边走，如果那个点已经被走过了，就不走了，换向另一条边，过程类似于DFS。 思路分析 既然是在一棵基环树上遍历每个点，走过这$n$个点…

题目传送门 题解 题目理解与强调： 这道题目含有一条只包含小写字母的字符串。要求能够找到多少个 子序列 满足形式 $ a,b,\ldots,a,b $ 思路分析： 这道题是一道计数题。 很简单地，我们可以得出结论：题目的答案与字符串$ s $中的'$ a,b,\ldots,a,b $'的数量与位置有关，当我们读取到'$ a $'时，首先要…