Catalan 数

Catalan 数表示为 $C_n$，有通项 $C_n=\dfrac{\binom{2n}{n}}{n+1}$ 和递推式 $C_n=\sum_{i=1}^nC_{i-1}C_{n-i}$，定义应该使用的是递推式。

Read More

Description

在 $T\times T$ 的正方形网格上（左下角格点坐标为 $(0,0)$，右上角为 $(T,T)$，共 $(T+1)^2$ 个格点），给定 $n$ 个关键点，保证横纵坐标都互不相同。要求选出尽可能多的关键点，使其按横坐标从小到大排序后，纵坐标也单调增。在此基础上，最小化以相邻两点为对角线的长方形面积总和。

$1\le n\le 2\times 10^5,1\le T\le 10^6$

Read More

Description

给定一个大小为 $n$ 的 multiset $\{a_1,a_2,\dots,a_n\}$，每次取出两个数 $x,y$ 将其删去然后插入 $\dfrac{x+y}{2}$，最终剩下两个数 $A,B$，试最大化 $|A-B|$。

$2\le n\le 10^6,0\le a\le 10^9$

Read More

Description

维护一个二进制数 $x$，支持两种操作：

• $x\gets x + a \cdot 2 ^ b$
• 询问 $x$ 第 $k$ 位的值

共 $n$ 次操作。

$1\le n\le 10^6,|a|\le10^9,0\le b,k\le30n$

Read More

准备倒序的把这个月做过的有意思的题都写一写简要题解，当然也可能有些稍微古早一些的题目。

Read More

CF1784D Wooden Spoon

这类问题通常可以按两种顺序 dp，本题中我们需要限制每组中最小的数依次递减，一种显然的想法是从大到小 dp，对于每个数考虑该数是与之前的某些数构成一组还是不做任何操作，类似于 ARC093F，当然由于我们需要对第一个数的每种取值计算方案数，所以 dp 需要反向，转移过程中的组合系数可能会很反常。另一种是从后向前，从小到大 dp，在填数的过程中留下一些空位，在后期对每个数决策是去填上之前的空位还是新开一组。两种方法都是 $O(n2^n)$ 的。

Read More