ST表（Sparse Table，稀疏表）是一种简单的数据结构，主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。它主要应用倍增的思想，可以实现 O(nlogn) 预处理、 O(1) 查询。所谓RMQ问题，以最大值为例，是假如有一个数列 A ，给你一个区间 [l,r] ，要求 maxi∈[l,…
离散化本质上可以看成是一种 哈希 ，其保证数据在哈希以后仍然保持原来的全/偏序关系。通俗地讲，就是当我们只关心数据的大小关系时，用排名代替原数据进行处理的一种预处理方法。离散化本质上是一种哈希，它在保持原序列大小关系的前提下把其映射成正整数。当原数据很大或含有负数、小数时，难以表示为数组下标，一些算法和数据结构（如BIT）无法运作，这时我们就可以考…
P1197 [JSOI2008] 星球大战：题目大意：首先给出一系列边，统计连通块的数量，然后删除某一个点，继续统计连通块的数量，显然统计连通块的话用并查集来做，但是并查集并没有删点的操作，只好逆向思考，采用离线做法，先统计删除的点，将坏点所在的边排除在外，统计连通块的数量，也就是删除所有点后连通块的数量，然后从最后开始加点，合并点所在的边，依次统…
并查集算法：在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。 主要有两个操作：合并，寻找父节点，通过判断父节点是本身的个数获取有多少个连通块。代码如下： int find(int x) { if(fa[x] == x) r…
代码如下： typedef unsigned long long ll; typedef long long l; #define lll __int128; inline ll qp(ll x,ll p,ll mod)//快速幂 { ll ans=1; while(p) { if(p&1) ans=(lll)ans*x%mod; x=(l…
迭代加深的A*算法，所谓迭代加深就是每次限制搜索深度， 通过一个估价函数判断下一步是否有效，这样可以在整个搜索树深度很大而答案深度又很小的情况下大大提高效率，使k从1开始不断加深枚举， 作为最大步数进行迭代加深搜索判断。由于是棋盘问题，这里有一个剪枝就是不要回头，比如枚举下一层之后，在下一层需要判断不会返回到上一层，通过pre来控制。代码如下： #…
传送门 题意：首先给出砝码数量n和限定值C，求出在n个砝码中的组合内不超过C的最大砝码组合的总和，这里n的范围到了1000，如果真的是这个数铁定爆了，但是题目给了一个条件：并且，这一行中从第3个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。一眼斐波那契数列，而且比斐波那契数列的总和还更大，对于斐波…
传送门 题意：首先给出油滴数量n，然后给定一个矩形的两个对角确定矩阵范围，每个油滴成圆形扩散，求如何选择释放油滴的顺序使得所有油滴所占面积最大，也就是说求出n的全排列，这里用dfs来实现。我们可以知道每个油滴初始半径必定是离边界最小值（防止越界）mb，然后还得考虑当前所选的油滴跟已经放进去的油滴会不会重合，并要使得当前油滴到已放置油滴的距离d大于已…
经典八皇后问题：传送门 题目要求：在n*n的矩阵内，皇后所在位置应该满足当前行，当前所在平行主对角线上有且只有一个皇后。这里可以现在第一行放置一个皇后，接下来递归下一行，通过check函数判断当前放置皇后的位置是否合法。这里只需要判断垂直方向，左上角方向，右上角方向（因为是从上面开始放置，不需要考虑下面的方位和同一行）代码如下： #include …
我愿称之为大杂烩合集！！！！传送门 题目大意：总共有n位大臣，一位国王。首先单独记录国王的左右手，接下来n行记录大臣的左右手，获得金币：当前大臣前面所以人左手整数的乘积除以当前大臣右手的乘数即为得到的金币数国王的目的：使得获得最多金币的大臣中使得这个最多金币最小。 前期错误思路：暴力，还是暴力，首先贪心部分，为了使得最大金币数最小，只需要按左手整数…