前置知识 确定两点后，如果另外两点的连线和这两点的连线的长度和中心点都相等。那么这四个点可以组成一个矩形，且前两点连的线段和后两点连的线段是矩形的对角线。 思路 $O(n ^ 4)$ 复杂度的暴力 最暴力的暴力，直接枚举四个点，然后看这四个点可以不可以组成矩形，如果可以就计算一下，最后统计最大值。 $O(n^4)$ 复杂度的暴力 这个方法虽然复杂度…

思路 首先，可以通过暴力看出来只有很少的数满足 $\frac{n \times (n + 1)}{2}$ 是完全平方数，所以我们可以先设定一个原始的排序方式，就是从 $1$ 到 $n$。 我们先判断，如果 $\frac{n \times (n + 1)}{2}$ 是完全平方数，那么直接判断为无解，因为没有任何方法的排序，能让这个排序的总和是完全平方…

Kosaraju 算法求强连通分量 原理 遍历两次 DFS，第一次遍历的时候按后序存储到数组里面，做记录。 第二次，从后往前按之前记录的数组，遍历所有这次没有被访问的点。 证明 云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这个算法求出的东西是强连通分量 在第二次遍历中，我们按照了==从后往前==的顺序来进行遍历，这样…

P8094 USACO22JAN Cow Frisbee S 题目概括 给定一个数组，求所有 $1 \leq i \leq j \leq n$，且对于所有 $i \leq k \leq j$，都满足 $a[i] \geq a[k] \cap a[j] \geq a[k]$ 的有序数对 $(i, j)$ 的长度（$j - i + 1$）。 算法 &a…

题目概括 在一个字符串前插入若干个指定字符：l、q、b，使得这个字符串成为一个回文字符串。 算法 & 数据结构 & 思想 洛谷标签：模拟 主要是了解回文串的特点，和题目中只能在字符串前面添加字符这个特点。 错误点 注意在 check 函数中，访问字符串中的位置的时候一定要判断有没有超出字符串长度或者小于 0。 思路 80 分（TLE…

CSP-S2 复习计划 知识点： DP 能力提升综合题单Part4 动态规划1 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 倍增 【算法2-3】分治与倍增 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 分治 【算法2-3】分治与倍增 - 题单 - 洛谷 | 计算机科学教育新生态 (luo…

AT_abc169_d [ABC169D] Div Game 看到题解里面好像没有用二分写的，我这个蒟蒻就写一个了。 题意 题目翻译写得很清楚了，我就不多写了。 思路 先把给定的 $N$ 分解质因数，得出： $$N = a_1^{p_1} \times a_2^{p_2} \times a_3^{p_3} \times \dots \times a…

线段树 II 之 懒惰标记 前置知识：线段树 I – ztr 的小窝 (ztrztr.top) 懒惰标志 Lazy Tag 懒惰标志，是维持线段树的区间修改查询的复杂度在 $O(\log n)$ 级别的一个方法。 正常的区间修改查询的复杂度可以说是 $O(n)$ 级别的，因为每次修改一个，需要一直传到叶子节点为止。 但是我们发现，如果这样的话，修改…

P10877 「KDOI-07」n1gr tS0i 个人认为这道题没有黄的难度。 思路 我先看了 $n=30$ 的样例，有一个猜想是答案是 $2^n$，然后用计算器算了一下 $n=30$ 的这个数据发现猜想是对的。 但是如果 $n=2$ 的情况发现不是这样的，所以又猜测只有当 $n$ 大于一个界限的时候才是 $2^n$。 首先，$n = 2$ 的情…

01-Trie ‍ 如果不理解 Trie 树的可以看我的之前的文章 Trie 树 – ztr 的小窝 (ztrztr.top)。 01 Trie 树，是运用 Trie 的思想储存一些数，从而实现省空间。 实现 01 Trie 树，是把原本是字符串中的都换成了一个数的二进制串。 对于添加数的操作，我们把数按二进制把二进制中的每一位拆分，然后按 Tri…