BJOI2019做题笔记

奥术神杖(分数规划、AC自动机)

发现我们要求的东西很像一个平均数(实际上就是几何平均数),那么我们现在考虑一种运算,使得乘法能够变成加法、开根可以变成除法,不难想到取对数满足这个条件。我们对\(\sqrt[v]{\prod a_i}\)取\(ln\)之后得到\(\frac{1}{v} \sum ln\ a_i\),那么我们现在需要它最大。

这显然是一个分数规划,二分之后考虑check。发现check类似于字符串匹配,在AC自动机上DP求解即可。复杂度\(O(nslog\frac{ln 10^9}{eps})\)

注意一个细节。输出方案的时候可能存在:模板串当前位置为'.'时有多种方案满足最优解,但是当前位置字符确定。在输出的时候需要额外的判断。

代码

勘破神机(递推、二项式定理)

强行二合一最为致命……

\(f_i\)是\(f_0 = f_1 = 1\)的斐波那契数列,设\(g_i\)表示\(3 \times 2i\)的棋盘的方案数,可以得到\(g_i\)的递推式为\(g_i = 2\sum\limits_{j=0}^{i-1} g_j + g_{i-1}\),即\(g_i = 4g_{i-1} - g_{i-2},g_0 = 1 , g_1 = 3\)。

\(f_i\)的通项公式为\(\frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{i+1} - (\frac{1 - \sqrt{5}}{2})^{i+1})\),\(g_i\)大力解一下特征方程或者丢到OEIS上找一下可以得到通项公式\(g_i = \frac{\sqrt{3}}{6} ((1 + \sqrt{3})(2 + \sqrt{3}) ^ i - (1 - \sqrt{3})(2 - \sqrt{3})^i)\)。

然后因为\(\binom{x}{k} = \frac{x^{\underline{k}}}{k!}\)是一个多项式,把多项式的系数求出来问题就等价于求\(\sum\limits_{i=l}^r f_i^k\)和\(\sum\limits_{i=l}^r g_i^k\),方法跟这里的一样。

关于特征方程一篇还不错的Blog

代码

送别(???)

不会留坑

排兵布阵(背包)

BJOI出PJ题……

考虑暴力DP:设\(f_{i,j}\)表示考虑前\(i\)个城市共用\(j\)个士兵的最大分数,然后不难发现每一个城市中的驻扎人数在恰好为\(2x+1\)时才有可能达到最优,其中\(x\)是第\(i\)个城市的其中一个人的驻扎兵力,那么有效的驻扎兵力数只有\(S\)个,\(O(NMS)\)地DP即可。

代码

光线(???)

考虑将两个玻璃合并。那么枚举在两块玻璃之间反射了多少次,就是一个无穷等比数列求和。

不难得到光线从\((a_i , b_i)\)和\((a_j , b_j)(j=i+1)\)两块玻璃之间穿过的概率是\(a_ia_j \frac{1}{1-b_ib_j}\),从\(j\)层穿入、再从\(j\)层穿出或者从\(j\)层反射的概率是\(b_j + a_j^2b_i \frac{1}{1-b_ib_j}\),这就是将两个玻璃合并之后从下表面反射的概率,从上表面反射的概率同理。那么我们就可以把两个玻璃合并起来。从上往下依次合并,就可以避免记录从上表面反射的概率。

代码

删数(线段树)

一个很巧妙的转化:考虑序列中的一个数\(x(x \leq N)\)如果它出现了\(p\)次,则覆盖区间\([x-p+1,x]\),那么答案相当于求\([1,N]\)内没有被覆盖的整点个数。

那么我们需要动态维护这个东西,支持单点修改、区间平移,直接用线段树维护。值得注意的一点是:当\(x>N\)的时候不能够产生贡献,区间平移的时候需要注意这一点。

代码

上一篇:在Ubuntu14.04 64bit上搭建单机Spark环境,IDE为Intelli IDEA


下一篇:【Leetcode】Triangle