JLOI2016 毒瘤题解

这玩意就是我在上一篇里面记错的那个树形DP

我复制一下……

就一树形DP裸题。

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

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

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

为啥要倒着一遍啊?

不要脸的抄的学长的代码QAQ

把圆的左右端的点离散下来做扫描线。

用set维护。如果当前点的父亲是一个左半拉圆,那么当前层次要 +1

如果父亲是右半拉圆,就是和父亲是一样的。

注意要在正确的时机正确地删除元素。

还有注意比较的时候。

贪心+KMP

先枚举覆盖顺序,然后讨论一下:

当前的这一个子串放哪儿。

下一个和这一个相交不相交。

最大:第一个要尽量向前放。尽量不相交。相交最长。

最小:尽量相交,相交最短。不放这个位置去放下个位置就是个子问题,可以记搜。

组合数美滋滋。

首先DP。设 dp[i][j] 表示 前 i 门科目,有 j 个人被碾压的方案数。

然后 DP 的转移就是乘乘组合数。

\mathrm{dp[i][j]}= \sum_{k=j}^{n} \mathrm{dp[i-1][k]} \cdot C_k^{k-j} \cdot C_{n-k}^{rk-1-(k-j)}

最后每个 dp[i][k] 都要乘一个东西:成绩的合法分配方案。

那么就是乘这个:

d_i=\sum_{k=1}^{U_i}k^{n-rk} \cdot (U_i-k)^{rk-1}

(不超过)n次多项式,取点插值就行了。

容斥。别忘了正方形可以斜着放。

总方案是

\sum_{i=1}^{\min(n,m)}(i \times (n-i+1) \times (m-i+1)) \mod p

然后枚举两个点就可以算出 2, 3, 4 个点不可行的方案。

然后一个点不可行的方案很麻烦,

我们按照点把坐标系分三部分,然后有左面的宽 l ,右面的是 r ,高是 h

然后计算方案。

如果 h \leqslant \min (l,r) 那么比较好算。

如果不呢?减去 h-\min(l,r) 的部分!

公式见下,建议自己推导。

然后就基本上做完啦!

可以用 map 缩短代码。

到此为止就屠龙啦!

[今天颓死了]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的。

[Zzz]趁着不太清醒赶紧把题解补完 | JLOI2014

[JLOI2014]天天酷跑

某优雅的DP题。

dp[i][j][k]表示在位置 (i,j) 并且用了 k 次连跳的答案。

转移分三种:一是如果 j=0 也就是在地面那可以跑一格

或者 k<q 可以跳一下

或者如果可以的话,下落。

可以枚举跳跃高度和次数然后记搜。

[JLOI2014]松鼠的新家

年代久远了。如果我没记错应该是一个树上差分问题。

好像是什么树上差分的板子……随便写写。

这是我元旦那天做的第一题,或者也可以说18年第一道题。

[JLOI2014]路径规划

这题劲啊!这题可劲了

考虑对 k 也就是过红绿灯的次数分层。

然后还是不好搞,没有办法之后我们可以分第二层。

k 分层之后,对于每一层,枚举所有加油站,计算出这个加油站 i 分别到 所有层 的 所有加油站 的最短路。

然后这样建新图,直接在加油站-加油站之间连边。然后跑对于 k 的分层图最短路。

SPFA 不会被卡。

期望等待长度是 \frac{R^2}{2 \cdot (R+G)}

[JLOI2014]镜面通道

hhh如果想知道证明可以评论

可以证明如果透气就一定透光。

不会构造出虽然透气,但是光线一直循环地反射,从而出不去的情况。

 

简单计算几何+最小鸽

每个几何图形做一个点,连边双向边。

圆与正方形交的时候,如果解方程,注意精度。

首先对于一个数字 x 的唯一分解式设为 \prod _{i=1} ^{n} p_i^{a_i}

那么约数和就是 \prod _{i=1} ^{n} \sum _{j=0} ^{a_i} p_i^j , 这个非常显然 (?)

那么……我们可以猜出 xS 是同级的。

那么显然 p_i \leqslant \sqrt{S}

那么可以暴搜。枚举 p_ia_i

一个特判是如果当前的剩余数字 S_i 减去 1 之后为一个质数,并且不小于当前枚举到的最大质数,那么也要算进答案。

需要证明请在评论区留言。