MENU

Liuxizai's blog

我们的心就像那天空一样 永不分离

[置顶] 2023 笔记

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

THUSC 2023 游记

看 THUSC 和 PKUSC 的公告,我本来觉得初审要求挺严格,但是今年居然两边都过了,不过湖北几个初中生好像基本上也是两边都过或者至少过了 PKUSC,说明对初中生还是很宽松的。

Read More

做题笔记 2023.2 Part 2

CF1784D Wooden Spoon

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

Read More