这是一类判断矩形的形状或者矩形的个数的问题，因为曾是NOIP2022真题，我们不得不重视这一类问题。同时，这个问题有非常多的解法，对其进行优化是一件很有意思的事情。 T1: P1191 矩形 题目描述 给出 $n\times n$ 的矩阵，由 $\texttt{W}$和$\texttt{B}$ 组成，判断其中有多少个 $\texttt{W}$ 构成…

此笔记并不会囊括所有等差数列、等比数列的高考知识点。只是随意写写自己觉得高妙的地方。 等差数列（Arithmetic Sequence) 定义 数列中，任何两项的差相等，这个差被称为公差，用 $d$ 表示。 定义式：$a_n=a_1+(n-1)d$ 我们发现可以表达成一次函数形式：$a_n=dn+b$ 等差中项 对于任何 $a_n, n \geq …

数论分块也称整除分块，是一个竞赛中的常用小技巧。 来看一个题目： 已知 $f(n) = \sum_{i = 1}^{n} \left \lfloor \frac{n}{i} \right \rfloor$，给定一个 n，求 $f(n)$ 的值。 如果 $1 \leq n \leq 10^6$，直接枚举，时间 5ms。 但是如果 $1 \leq n …

最长上升子序列(LIS) 1. $\mathcal{O}(n^2)$ 做法 设 $dp_{i}$ 表示以i 结尾的答案。所以先枚举一个 $i$ ，再从$1$ 开始枚举 $j$ ，每次看到小于 $a_{j}$ 的数，取一个最大的更新 $dp_{i}$ 。 2. $\mathcal{O}(nlog_n)$ 做法 状态设计： $dp_i$ 表示长度为 $…

颜色限制（restriction） 时间限制: 1000ms 空间限制: 524288kB 输入文件名: restriction.in 输出文件名: restriction.out 题目描述 有一个 $n$ 点 $m$ 边的无向图，有 $k$ 种颜色编号为 $0∼k−1$，每条边有一种颜色。对于每种颜色，请判断假如删去所有这种颜色的边，得到的图是否…

2. 摘 Galo(OvO) 1s/512M [XOJ]仅评测链接 2.1 题目描述： 0v0 在野外看到了一棵 Galo 树，看到食物的 0v0 瞪大了眼睛，变成了 OvO 。 这棵 Galo 树可以看做是一棵以 $1$ 号点为根的$n$个点的有根树，除了根节点 以外，每个节点i都有一个 Galo ，美味度为$w[i]$。 OvO…