[今天颓死了]JLOI2015题解

其实是补昨天的坑。。。

今天颓死了。。。啥都没写 基本没学会多少东西 题也想不出来。。

成天看题解写代码 看题解调试。。。。。。。。

各种事。。还有CCPC。。

烦死了。。。。。

 

艹 我今天怎么也要做完三道题。

看题解对着写代码这毛病能把我送退役。。这毛病怎么也得改。。。

 

……[咕咕咕咕]挣扎两天半后的更新

 

行了,说正事


 

 

左偏树模板。

首先每个结点都来一颗左偏树。

然后你直接DFS,去合并左偏树并更新答案。

每个结点pop()完之后合并到父节点。

注意下放标记的顺序和时机。

就一树形DP裸题。

设计状态 f[i][j] 表示在点 i 上,子树前 j 层未覆盖的最小答案。

然后 g[i][j] 表示子树全部覆盖完毕,又多往上覆盖了 j 层的答案。

然后转移就是了。注意最后更新要扫两遍。

 

woc……记错题目了?尴尬。。。

这好像是另外一题的??

那么,我看一下题面

 

哦,这里我们首先可以发现对于每个叶子,他只对所在的链有影响

然后考虑爆搜,每次搜到底搜一条链,然后非叶结点可以:

枚举左边有多少参战。枚举右边。

记搜一下。

完了。。送分。。。

名字和题面毫无关系之 (1)

求某个式子 \lfloor ( \frac {b+\sqrt{d}} {2} ) ^{n} \rfloor \mod p

那你发现这玩意儿是无理数。。没法算

我们考虑这样

我们求这个:

\lfloor [ ( \frac{b+\sqrt{d}}{2} )^{n} + (\frac{b-\sqrt{d}}{2})^{n} ] - (\frac{b-\sqrt{d}}{2})^{n} \rfloor

然后去观察左边的柿子,发现:

我们可以构造一个方程: x^2-bx+\frac{b^2-d}{4}=0 。

为啥?这玩意儿两解是: x_1=\frac{b+\sqrt{d}}{2} \,,\, x_2=\frac{b-\sqrt{d}}{2}

然后呢?

(\frac{b+\sqrt{d}}{2} )^{n} + (\frac{b-\sqrt{d}}{2})^{n} = x_1^n + x_2^n

变形!

F(n) = x_1^n+x_2^n = (x_1+x_2)(x_1^{n-1}+x_2^{n-1}) - x_1x_2(x_1^{n-2}+x_2^{n-2})

然后用这个:

x_1+x_2 = -\frac{b}{c} \,,\, x_1x_2 = \frac{a}{c}

得出:

F(n)=-\frac{b}{c}F(n-1) - \frac{a}{c}F(n-2)

然后就可以快乐的矩乘啦!

后面的那个怎么搞?

我们有个结论!看:

\because b^2 \leqslant d < (b+1)^2

\therefore b \leqslant \sqrt{d} < b+1

\therefore \frac{b-\sqrt{d}}{2} \in (-1,0]

那么只有 n 为奇数并且 \sqrt{d} \ne b 的时候,这一部分对答案是有 -1 的贡献的。

注意快速乘 , ull 。

斯坦纳树问题:斯坦纳森林(子集DP套子集DP)

首先我们发现,如果去掉频道这个玩意,这就是个裸的最小斯坦纳树问题

(Minimal – Steiner – Tree Problem , MST)

那么我们对每个频道分别做斯坦纳树。这玩意就一个子集DP,不会的可以找找板子看一下。

SPFA更新状态真的绝了。

 

那么做完每个点的MST-Problem,我们做子集的。

先离散化一下频道编号。。这个无所谓的。。细节问题。

 

你就把频道作为集合直接暴力枚举子集。然后把子集内的频道的斯坦纳点都初始化一下(其他全给个 \infty )然后跑斯坦纳树。

 

然后最后合并答案。斯坦纳森林,第一次见,还挺好玩的。

线性基。求一个权值和最小的线性无关组,使得可以线性表出所有给定向量。

那么我们直接排序贪心+线性基就完事了。。

高消版线性基。

这套题让我至少学了三个板子。

看好,这道题能让我达成史上最长题解之一。。。。

首先转化问题:

打死我也想不到这么转化

你可以找一下关系,然后连一下边,然后你会发现,答案等价为:

就这个图,然后从原点走到菱形点,信息都标好了。

答案是不跨越这两条对角中任一条的情况。

那么我们做辅助线 A \,,\, B

然后就是变为全部方案减去触碰 AB 的情况。

那么我们假设不合法的方案记为类似 AAABABABBBAAB 这样的方式。这个表示方法就是记录了一下跨越顺序。

相同的字母可以缩成一个,这样不会算重复。

那么:

我们令初始点为那个方点,然后我们做这样的操作:

将当前点沿直线A翻转,然后把原点到当前点的方案数从答案中扣除;

将当前点(注意此时已经翻转过了)沿直线B翻转,然后把原点到当前点的方案数从答案中加回来;

反复如此直到某一坐标 <0

因为此时无论如何进行下去方案数都是 0 了 。

这样做相当于把以 AAB 为后缀的方案删除,然后把以 BABAB 为后缀的方案加回去,然后把以 ABAABAB 为后缀的方案删除……

好妙啊!

然后我们先沿 B 翻转再做一次,就删掉了以 B 为前缀的所有方案 。

好妙啊好妙啊!!!!!

呼,写完啦!去补2016的。

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据