高度由习惯堆积

分类 OI题解 下的文章

NOIP2018 保卫王国

题目Z 国有 $n$ 座城市,$n−1$条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:一座城市可以驻扎一支军队,也可以不驻扎军队。由道路直接连接的两座城市中至少要有一座城市驻扎军队。在城市里驻扎军队会产生花费,在编号为 $i$ 的城市中驻扎军队的花费是 $p_i$。小 Z 很快就规划出...

CSP模拟赛 巨神兵

题目欧贝利斯克的巨神兵很喜欢有向图,有一天他找到了一张$n$个点$m$条边的有向图。欧贝利斯克认为一个没有环的有向图是优美的,请问这张图有多少个子图(即选定一个边集)是优美的?答案对$10^9+7$取模。对于40%的数据$n≤5,m≤20$对于60%的数据$n≤10$;对于80%的数据$n≤15$;对于100%的数据$n≤17$。思路考场上只会写枚举边集的纯暴力,后来发现自己蠢爆了。首先这题...
August 30, 2019

计蒜客The Fake Fake Friends

题目题目链接互膜作为一种机房活动,在增进友谊、锻炼表达能力的同时,也能给蒟蒻以充分表达自己对神犇景仰之情的机会,可谓一举多得。同时,它也是附中洗脑团队的日常。每一天,n 个 OIer 都会围成一圈,为方便起见,我们不妨按顺时针为他们编号 1~n。每个 OIer 都有一个 01 属性,这个属性代表着他们是蒟蒻还是神犇。在这里,为了简化问题,我们并不区分日常写挂的蒟蒻和什么都不会的蒟蒻,我们也不...
August 20, 2019

[国家集训队] Crash 的文明世界

题目题目链接Pre$$ m^n=\sum_{i=0}^{m}{\begin{Bmatrix}n\\i\end{Bmatrix}}C_m^i*i!\\ $$Part1$$ ans_x=\sum_{i=0}^{n}dis(i,x)^k\\ =\sum_{i=0}^{n}\sum_{j=0}^{dis(i,x)}{\begin{Bmatrix}k\\j\end{Bmatrix}} C_{dis(i...