标签
暂无

模板题更新辣!

2020-03-26 18:54:22 By eeeeeericKKK

拖更一年的模板题又更新辣!

拖更一年的模板题又更新辣!

拖更一年的模板题又更新辣!

欢迎大家来切,也欢迎更多新模板题/kel

征集模板题

2018-12-15 23:29:13 By eeeeeericKKK

你也许已经注意到,最近 nflsoj 出现了一道新的模板题:多项式复合逆。如果你不知道这是啥没关系,你只要知道这是杨主力 @fizzydavid 的题就行啦!

杨主力拥有 $10$ 个模板题位置,现在已经在路上或确定好的 idea 有下面几个:(立个flag不会鸽

Lyndon分解,周期串拆分,回文串拆分,Trie上回文树,基本子串字典(Internal Pattern Matching),多项式复合逆

如果你有什么好的模板题,欢迎在这篇博客下评论或者私戳,可以占这 $10$ 个坑,也可以问OJ管理员 @TRCYX 和 @diamond_duke 要空题(既然要了就自己造吧)。占了空题位之后,造数据和写题面的过程可以找几个人一起分锅,标程最好能自己提供。

为了鼓励大家踊跃造题,每贡献一个被认可的idea并出成题目,将获得多项式板子一个。

当然,模板题有一些要求:

  1. 要符合模板题的身份。
  2. 常见oj( lojuoj洛谷等)上找不到相同的纯模板题,或者对应题目数据范围太小或数据太弱被大部分人用非 std 做法爆过去。(当然如果管理员滋磁且你有数据或愿意自己造可以忽略这条)

不过,如果你希望占杨主力的 $10$ 个坑(并强行让他帮你一起造这个题),请仔细考虑/xyx。

典型事例

A:最近刚刚学了个 *** 算法,能不能加到模板题里去啊/kel。

fizzydavid:不行,太简单了,出出来没有牌面。(说罢丢给你一篇论文)你看你/论文里的做法只能做到 $1000000$ ,我来给你加 $6$ 个零。

Hundred Thousand Volts 01 题解

2018-04-15 14:07:15 By eeeeeericKKK

棋赢

是不是很像个多项式题呢?

令果子总数为sum,最终答案显然是 $\binom{sum-1}{n-1}$ 。由于n很小,前者可以暴力展开成一个关于sum的n-1次多项式。这意味着如果我们算出向量 $V=(\sum sum^0 ,\sum sum^1 , \sum sum^2 ,\dots ,\sum sum^{n-1})$ ,就可以求得答案。

定义 $f(V,x)$ 表示对V所代表的的当前答案中所有需要统计的sum值变成sum+x会怎么样。利用二项式定理可以把 $(sum+x)^k$ 展开,最终写成一个下三角矩阵 $M_{ij}=\binom i j\cdot x^{i-j}$ 。容易得到 $f(V,x)= M\cdot V$ 。

接下来考虑一只动物的影响,相当于把x=1到x=b所对应的的矩阵相加,也就是 $M'_{ij}=\binom i j\sum_{x=1}^bx^{i-j}$ 。得到这个之后,可以使用矩阵快速幂得到最终的答案。不考虑计算M的时间,总的复杂度是 $O(mn^3\log S_a)$ 。

至于转移矩阵显然是一个自然数幂和的形式,有多种方法优化。

某黑红出题人要求我把这题出成一个彻头彻尾的多项式题,数据范围变成$10^5$,然而本出题人非常良心没有同意。这部分就当做bonus啦!

std(上面blog没有描述,用了第二类斯特林数和下降幂的性质)在这里


或负

甩锅啦!原题戳这里,题解戳这里

std在这里


必去之

为了方便,把p改变,使得最优答案一定包含第一个和最后一个数,详见std。

定义f(i)表示考虑前i个数,且必须选择第i个时的LIS。那么有下面的公式,可以证明这样一定不会丢失最优解。 $$f(i)=\max\{f(j)+1+\min\{j到i之间的空格个数,p_j到p_i之间未出现在原排列的数的个数\}\mid j< i,p_j>0,p_j< p_i\}$$

可以发现min里面的两项都是部分和的形式,可以用前缀和改写。公式自行脑补然后把min操作分成两部分加到max的条件里面去,这样所求的max值为一个三维的RMQ。首先按i从小到大可以去掉一维,剩下的随便写个二维数据结构即可,复杂度2个log。

std(cdq分治)在这里


后记

实际上我写了一个很详细的题解,包括多种算法和部分分。然后在最后写好保存的时候网络模糊,最终保存到oj上的变成了一堆乱码...

不过出题人还是很良心艰难地把正解做法告诉了你们!至于具体公式和细节就留给你们脑补啦!

杨主力:写题解还带std的都是sb出题人!
共 3 篇博客