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

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

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

文本编辑器：VisualStudio Code 这是一个强大的调试工具，不仅能快速正确地读取下发的样例，系统式管理代码目录，还能有更自由的编译选项，更加灵活的调试。但是它需要配置C++环境才能使用，这导致赛场上很多人都是使用dev的。 一. 检查插件 由于赛场上是断网环境，我们需要检查一下自己的机器是否安装了C++插件，如果没有插件，那么无法使用代…

一.背景 其实要不是当时一时兴起，也不会有今天这个博客，不会有从那时开始发展到今天的点点滴滴往事。如果不是那时的决定，我现在肯定在边学习边摸鱼，没有很努力地去做一件事。期中考试虽然没考好，但是我还是为我努力做了一些事情而感到开心。 开始是八月份，有人提议我说为什么不搞一搞CSP，我说：那好啊，我报个普及组玩玩咯。第二天学校教练打电话过来，说普及组没…

【原链接】 这篇太叼了！ pb_ds，比 STL 更强大的模板库。 upd. on 10.27 更新了优先队列的常数分析，增加了“万能头文件”的内容。 前言 之前看到过一篇关于 pb_ds 写得很好的文章，但现在找不到了；OI-wiki 上的内容的不太完整。那不如自己动手，丰衣足食。 当然，pb_ds 库中有很多东西 算竞 …

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