[置顶] 2023 笔记
Catalan 数
Catalan 数表示为 $C_n$，有通项 $C_n=\dfrac{\binom{2n}{n}}{n+1}$ 和递推式 $C_n=\sum_{i=1}^nC_{i-1}C_{n-i}$，定义应该使用的是递推式。
Solution. CF1817E Half-sum
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$
Solution. LG3822 [NOI2017] 整数 / Trygub Numbers
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$
THUSC 2023 游记
看 THUSC 和 PKUSC 的公告，我本来觉得初审要求挺严格，但是今年居然两边都过了，不过湖北几个初中生好像基本上也是两边都过或者至少过了 PKUSC，说明对初中生还是很宽松的。