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

题目链接 这是一道经典的树状数组题目，同时也是莫队、线段树算法很好的练习题。 题目描述 HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。 有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这…

题意 求序列 $a$ 中所有数 $\oplus p_i$ 后，逆序对的数量。 $ 1 \leq n,m \leq 10^5, 1 \leq a_i, p_i \leq 2^{32}$ 题解 本题本来写了朴素算法，期望得分$30pts$，结果挂了。直到现在还不知道为什么挂了。 现在来讲正解。 异或是按位来运算的，而数据范围又这么大，考虑一种按位处理的…

T1.简单树（easy.cpp） 题目描述 给定一棵 $n$ 个点的树，你需要给每条边赋值 $0$ 或 $1$，求树上所有点对之间的简单路径权值总和的最大值，并输出方案。 一条路径的权值定义为这条路径上所有边权的异或和。 题解 引理 可以知道， $ans(x,y) = ans(x, root) \oplus ans(y, root)$。将树想象成一…

题目链接 长度为 $m$ 的栅栏上，有 $n$ 头牛需要坐车前往别的地方，起点和终点分别为 $a_i$ 和$b_i$ 。现在一辆出租车从最左端 $0$ 出发，要运送完所有牛，最后到达最右端$m$ ，求最小路程。出租车只能一次载一只牛。 题解 超级无敌大水题思维题 首先，出租车要将每个牛都从出发点送到目的地，那么必须经过所有牛的路程。我们先将这个路程…

题目描述 给定一个长度为 $n$ 的数字串 $a$，和一个长度为 $m$ 的数字串 $b$，保证 $b$ 中出现的元素在 $a$ 中都出现过，且 $b$ 中任一元素只出现过一次。现求一个 $a$ 的长度尽可能短，且尽可能靠左的子串，使 $b$ 成为其子序列。 数据范围 多测 $1≤T≤1000$ $1≤m≤n≤10^6$ $1≤∑n≤5×10^6$…

[题目链接] 题目描述 Bessie喜欢在手机上下游戏玩（……），然而她蹄子太大，很难在小小的手机屏幕上面操作。 她被她最近玩的一款游戏迷住了，游戏一开始有$n$个正整数，$(2\leq n\leq262144)$，范围在$1-40$。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个$7$合并成一个$8$)，目标是使…

期望值（Expectation）是概率论和统计学中的一个重要概念，它表示在一个随机事件或随机变量的多次重复实验中，某个特定数值的平均或期望表现。通常用符号 "$E(X)$" 表示，其中 "$X$" 是随机变量。期望值提供了一个概率分布的数值特征，它可以帮助我们了解随机事件的中心趋势。 在离散随机变量的情况下，期望值的计算可以使用下面的公式： $$&…

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

[题目链接] - [NOI2001] 食物链 [NOI2001] 食物链 题目描述 动物王国中有三类动物 $A,B,C$，这三类动物的食物链构成了有趣的环形。$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。 现有 $N$ 个动物，以 $1 \sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一…