luogu5535 & luogu1414 题解
luogu5535 小道消息 分析 关于伯特兰·切比雪夫定理，我们只需要用百科里说的“较弱”的说法。 对于整数 \(n \ge 1\)，至少存在一个质数 \(p\)，满足 \(p \in (n,2n)\)。 有什么用？ 首先 \(k \in [1,n]\)，由于每个人衣服上的数是下标 +1，那么第 \(k\) 个人衣服上的数就满足 \(k+1 \ge 1\)。从而 \((k+1,2
CF482A Diverse Permutation 题解
分析 话说这题为啥要写题解啊？ 因为，我最最最最不擅长的构造题，我最最最最期望的「构造作战」，还是要从水题开始攻克吧。 如何构造 \(k\) 种差值呢？ \[ [1,k+1,2,k,3,k-1 \cdots] \] 这样构造的差值是 \(k,k-1,k-2 \cdots\)，那么就可以用 \(k+1\) 个数字构造出 \([1,k]\) 中所有的差值。 照这样，维护两个指针 \(
luogu2294 狡猾的商人 题解
solution1 带权并查集 给出的信息是区间和的形式，搞个前缀和数组 \(a_i\)，表示 \([1,i]\) 月的总收益。 假如知道 \([x,y]\) 月的收益与 \([y,z]\) 月的收益，那么就能推出 \([x,z]\) 月的收益。这时候如果后来的 \([x,z]\) 月的信息产生冲突，那么必定是假的。 由于不同区间的信息具有可合并性和传递性，考虑带权并查集。 首先明确 \
「图论学习笔记」#4 二分图相关
二分图最小点覆盖 给定一张二分图，求出一个最小的点集 \(S\)，使得图中任意一条边都至少有一个端点在 \(S\) 中。这个问题称为二分图的最小点覆盖，简称最小覆盖。 \(\text{k\"onig}\) 定理 二分图最小覆盖包含的点数等于此图最大匹配包含的边数。 看证明过程时，请牢记增广路，最大匹配，匹配点，匹配边的定义，不然像我这种不太聪明的可能会多想很多没用的东西。
CF1582E Pchelyonok and Segments 题解
分析 倒着选区间。 设 \(f(i,k)\) 表示从 \([i,n]\) 中选择 \(k\) 个区间，其中最后一个区间（也就是最长的，最靠近 \(i\) 的区间）的最大值。 当 \(k=1\) 时 \[ f(i,k) = \max{\{ f(i+1,k),a_i \}} \] 当 \(i+k-1 \le n\) 且 \(S(i,i+k-1) < f(i+k,k-1)\) 时 \[