省流：100+88+8+100+24+8=328。

Read More

还是写一下游记吧。今年的 THUWC 在人大附中本部举行，于是有幸来到了这所很可能是全国最好的中学。今年 Day 1 下午还增加了学科嘉年华环节，在清华大学内进行，展示了一些清华大学在 AI 领域的前沿研究成果，感觉还是挺牛的。所以这就是为啥我不去北大营。等待时有两个小游戏分别是 AI 生成图片猜成语和读代码猜诗词，对我这种语文基础只有婴儿水平的人极不友好，不过最终还是靠场外协助通关了。

Read More

开 T1，感觉随便贪就对了？简单证明了一下，每次考虑第一个被 ban 掉的点之前的贡献，看起来确实是对的。首先照着这个证明的思路写了一个类似双指针的东西，实现起来有点繁琐，写了一半弃了，最后按照最开始的思路写了一个逐位贪心，半个小时的时候过了大样例。

Read More

$n$ 个在 $[0,1)$ 上均匀分布的随机变量 $\{x_i\}$，考虑它们的和 $s=\sum x_i$，则 $s$ 服从 Irwin-Hall Distribution，其累计分布函数
$$F_s(x)=\frac{1}{n!}\sum _{k=0}^{\lfloor x\rfloor }(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(x-k{)}^n.$$
考虑单个变量的概率密度函数 $f(x)=[0\le x<1]$，则 $F$ 是 $n$ 个 $f$ 的卷积。

Read More

Schwartz–Zippel 引理指出，如果我们有非零 $n$ 元 $d$ 次多项式 $p(x_1,\dots ,x_n)$，对每个 $x_i$ 在有限集合 $S\subset \mathbb{R}$ 内独立均匀随机赋值，则
$$\mathbb{P}[p(x_1,\dots ,x_n)=0]\le \frac{d}{|S|}.$$
证明考虑对 $n$ 进行归纳。

Read More