BJOI 2019 解题报告

P5319 [BJOI2019] 奥术神杖

数学题。搞掉几何平均数的方法是左右取对数，然后变成一个经典的 \(0/1\) 分数规划问题。解决方法是二分答案后 AC 自动机 + DP。

P5322 [BJOI2019] 排兵布阵

简单题。随便 DP 即可，五分钟之内没想出这道题的赶快去加训。

P5320 [BJOI2019] 勘破神机

科技题。此题涉及到的知识点较多，请谨慎选择做不做这个题。

首先肯定要组合数转下降幂，否则组合数很难处理掉。既然都转下降幂了，就直接搬出大杀器第一类斯特林数，转为求 \(\frac{1}{k!}\sum\sum\operatorname{Stiring}(k, j)f_i^j\)。对于 \(2, 3\) 分别求出 \(f\) 的通项公式，似乎就可以做了。

事实上，第二问确实这样做就直接结束了，但是第一问有个麻烦的地方是 \(\sqrt{5}\) 在 \(\bmod 9982444353\) 意义下不存在，那我们只好对这个进行扩域，可以设 \(i^2=5\)，最后这一项的系数必为 \(0\)；或者根据 rqy 大佬所说，\(\sqrt{x}\) 不存在的话 \(\sqrt{-x}\) 必然存在，也可以做。

P5324 [BJOI2019] 删数

ds 题。有一个明显的结论，但不知道怎么说比较形式化；按照第一篇题解的说法，就是开桶以后向左推倒，未被覆盖的位置个数。

那么这个就可以线段树维护了。操作二相当于整体平移。

P5323 [BJOI2019] 光线

物理题。简单推个式子就能做了。小粉兔很强，采用了 \(O(n)\) 的优秀做法，技压群雄。

P5321 [BJOI2019] 送别

有趣题。这个题目描述正是走迷宫的时候的一个惯用方法，就是沿着一边走，而这么走肯定是沿着一个环走的，所以我们考虑怎么维护好多个环。

注意这里要内外分开维护。内外不一定是一起的。

观察它的操作。加边会连接两个环或把一个环断成两个，断边会销毁两个本来连接在一起的环产生一个新环，反之亦然。而查询相当于在环上查询相对位置的差。这告诉我们我们要有一个支持快速分裂，快速合并，快速单点查询的数据结构——你想到了什么？是平衡树。

剩下的问题就是一些细枝末节了，然后这个题理论上就做完了。但是仔细一想，这个题有一大堆很恶心的细节问题，可能是这个题评黑的原因。有时间写了他。