我们观察到,整个行为一定能被拆分为全买和全卖。 略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖, …
lp4768 NOI2018 归程
克鲁斯卡尔重构树模板题。 我们发现,这一题可以拆成两个步骤。第一个步骤,是找到所有u可以通过共享单车达到的点; …
lp2146 NOI2015 软件包管理器
简化题意: 存在一棵树,其上所有点的初始值为0。 存在两种操作,分别是,将一个点的所有父亲节点改为1,或者将一 …
lp2387 NOI2014 魔法森林
这一题据说是LCT维护边权的题目。但是我们观察一下感觉可以用动态加边SPFA来跑这道题。 具体来说,对于每一条 …
lp2044 NOI2012 随机数生成器
我们不妨将原式递归展开,可以得到形如此的式子: $$f_{n}=a^nf_{0}+\frac{(a^{n}-1 …
lp3980 NOI2008 志愿者招募
一开始YY了一种连边方式,就是源点向第一个点连边,第一个点向最后一个点连边,每个边的流量是1,希望能通过一些奇 …
lp2050 NOI2012 美食节
这一题是SCOI2007修车的威力加强版。 用常规的写法显然是无法通过的。 我们考虑动态加边。 这样就可以最小 …
lp2805 NOI2009 植物大战僵尸
仔细阅读题意,我们发现,这道题本质上就是一个约束类问题:对于每一株植物,都存在一些植物,需要消灭掉它们才能消灭 …
lp2150 NOI2015 寿司晚宴
将2~n的整数划分到两个集合,使得两个集合中任意两个元素互质,求方案数。 对于n<=30的情况是很容易想 …
lp1963 NOI2009 变换序列
如果知道这道题是一个二分图匹配,就显得非常简单了。 首先我们对原序列和变换序列各自建一个点。 然后,对于每一组 …
lp2042 NOI2005 维护数列
Splay裸题。 具体来说,维护两个延迟标记,翻转标记和改变标记。然后对于每一个标记考虑下传。 对于两种询问各 …
lp2052 NOI2011 道路修建
作为一道NOI的题,它一度令我以为它是2001的。 不曾想,NOI竟然有这么水的题。 我一开始以为自己的写法错 …
lp1486 NOI2004 郁闷的出纳员
(似乎很少看见权值线段树的做法的样子。但是权值线段树如果动态开点、大胆卡常的话,是可以跑得飞快的。) 首先看一 …