MENU

Liuxizai's blog

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

HBOI 2022 游记

省选前自己在家训练了大概 20 天,每天做做题,没学太多新东西,打了 3 场 cf div.2(fst 了两场,已经要自闭了),打了 3 场 public round,这个体验应该说还不错。

Read More

Solution. Codeforces Round #781

现在是 12:35,只做了 ABC,简单记一下关于 DE 的想法。

D,给了 30 次询问,从信息论的角度看,$\left\lceil\log_2 10^9\right\rceil$ 恰好等于 30,那是否要求了每一次询问都将可能的答案减半,或者每次询问确定一个二进制位这样。

能够想到的就是可以通过 $\gcd(x,x+prime)$ 来判断 $x$ 是否拥有 $prime$ 这个质因子。

Read More

决策单调性优化 dp 学习笔记

dp 这块的东西又多又杂,本来想把斜率优化或者 wqs 二分一起总结一下,但是难度实在有点大,所以还是按照专题慢慢来。

首先对决策单调性有一个整体的认识。

对于最优化 dp 而言,每个状态从若干个状态转移而来,其中存在一个最优转移点。dp 拥有决策单调性指的就是这个最优转移点按照某种顺序单调变化,例如从左到右等等。

Read More

Solution. Codeforces Round #779

Div.2 only,打得烂到飞起,简直像是一年前的自己。

上来先 D 开,一看发现 D 大概很简单,写了一发过了 D1 的 pretests,D2 看了看没啥思路就先放着,A 和 B 打完之后(B 上浪费了不少时间)跑去看 C,结果想了一辈子也不会,实际上我那个 -1 的 submission 已经无限接近正解了。

Read More