2023/12/16 晚 (OTC+8)22:35 T1 Constructive Problems 题意描述： 问如图方式填充一个 $ntimes m$ 的矩阵要预先填充多少个格子。 分析： 观察发现，每一列至少填充一个，才能构成条件，答案为 $max(n,m)$。 T2 Begginer's Zelda 题意描述： 你可以把树的任意一条路径合并…

题目大意 丑数列是一个元素质因子仅包含 $2,3,5$ 的数列，特别地，$1$ 包含在内。 $$1,2,3,4,5,6,8,10,12,15,\ldots$$ 请输出第1500个丑数。 题目分析 由于质因数只包含 $2,3,5$ ，元素可以转化为 $2^i\cdot 3^j\cdot 5^k$，也就是说序列中的每个元素只要乘上 $2,3,5$ 都可…

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

最近在刷贪心水题，于是就看到有一些题都是基于一个数轴上完成最大贡献的任务的问题展开的，于是，就有了这篇题解，倒不如说是一个分类。 T1.[ABC137D] Summer Vacation 题目链接 这种题目的最常见的限制条件是每天只能做一个任务，这样我们可以采取枚举天数来解。 再来看看还有什么条件，做完工作之后要一定的天数才能拿到工资，也就是说那些…

题目链接 这是一道经典的树状数组题目，同时也是莫队、线段树算法很好的练习题。 题目描述 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$ ，求最小路程。出租车只能一次载一只牛。 题解 超级无敌大水题思维题 首先，出租车要将每个牛都从出发点送到目的地，那么必须经过所有牛的路程。我们先将这个路程…

题目描述 在 $xy-$ 直角坐标平面的天空中，有 $n$ 片四边平行于坐标轴的矩形云朵。每一片云由一个五元组 $(xi,yi,wi,hi,di)$ 表示，其中 $(xi,yi)$ 为云左下角顶点的坐标，$w_i$ 表示云在 $x$ 轴方向的宽度，$h_i$ 表示云在 $y$ 轴方向的长度，$di∈lbrace 0,1rbrace $ 为云的移动方…

问题描述 给定一个 $n$ 行 $m$ 列的网格图，每个格子的颜色是蓝色、白色中的一种。白色的格子是障碍点。对于 $2$ 个有公共边的蓝色格子，它们之间是连通的。保证任意 $2$ 个蓝色格子间最多只有 $1$ 条不经过白色格子的路径。现给出 $Q$ 个矩形区域，对每个矩形区域求出对蓝色格子来说的连通块个数（不能经过白色格子和矩形区域外的格子）。 数…