发布于

BZOJ3895 取石子

这题思路不错。

首先考虑对于一个 >1 的堆，如果合并他对先手有利，那么这堆石子在取完之前一定会被先手合并。同理如果对后手有利也是。

既然合并这个动作要不就是对先手有利要么就是对后手有利，那肯定这堆石子最后会被合并。

并且在取完之前，合并这个动作无论在何时发生，都等同于在对这堆石子操作时的前两步内发生。

那么我们就可以把充裕堆 ( 大小 >1 的堆 ) 先提前合并了，然后在 DAG 游戏图上记搜 \mathrm{SG} 值。

操作分为几种：

  • 拿走一个孤单堆
  • 拿走充裕堆的一个石子
  • 把一个孤单堆合并到充裕堆内
  • 把两个孤单堆合并，成为充裕堆的一部分

然后就写个代码就好了。复杂度大概是 O(T \cdot \sum{a_i}) 的。

 

发布于

JZOJ | NOIP2018模拟10.27 百鸽笼

把序列倒过来建主席树

没了。

 

发布于

JLOI2016 毒瘤题解

[JLOI2016/SHOI2016]侦察守卫

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

我复制一下……

就一树形DP裸题。

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

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

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

为啥要倒着一遍啊？

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

[JLOI2016]圆的异或并 

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

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

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

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

还有注意比较的时候。

[JLOI2016]字符串覆盖 

贪心+KMP

先枚举覆盖顺序，然后讨论一下：

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

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

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

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

[JLOI2016]成绩比较 

组合数美滋滋。

首先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次多项式，取点插值就行了。

[JLOI2016]方 

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

总方案是

\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。。

烦死了。。。。。

 

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

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

 

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

 

行了，说正事

 

 

[JLOI2015]城池攻占 

左偏树模板。

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

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

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

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

[JLOI2015]战争调度 

就一树形DP裸题。

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

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

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

 

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

这好像是另外一题的？？

那么，我看一下题面

 

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

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

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

记搜一下。

完了。。送分。。。

[JLOI2015]有意义的字符串 

名字和题面毫无关系之 (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 。

[JLOI2015]管道连接 

斯坦纳树问题：斯坦纳森林（子集DP套子集DP）

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

(Minimal – Steiner – Tree Problem , MST)

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

SPFA更新状态真的绝了。

 

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

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

 

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

 

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

[JLOI2015]装备购买 

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

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

高消版线性基。

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

[JLOI2015]骗我呢 

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

首先转化问题：

打死我也想不到这么转化

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

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

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

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

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

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

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

那么：

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

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

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

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

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

这样做相当于把以 A 和 AB 为后缀的方案删除，然后把以 BA 和 BAB 为后缀的方案加回去，然后把以 ABA 和 ABAB 为后缀的方案删除……

好妙啊！

然后我们先沿 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如果想知道证明可以评论

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

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

 

简单计算几何+最小鸽

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

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