wxyww

精品

未归档(12) 题解(65)

/ 注册

全部文章 / 精品（共28篇）

luogu6584 重拳出击

solution 提供一种贪心+序+线段树的做法。为了方便，我们以小的初始位置为根。大概理解完题意，可以发现有一个比较显然的性质：每一回合结束，每个与小之间的距离不会变大。然后考虑小移动所产生的影响。考虑当小开始移动时，如果小从移动到了的一个儿子。那么这一回合结束，子树中的每个Youyou与...

贪心

2020-05-30

3 708

BSGS与扩展BSGS

BSGS 算法又称大步小步算法算法主要用于解以下同余方程其中,即与互质前置知识根据欧拉定理，所以的循环节为.也就是说如果上面的方程有解，那么肯定有，所以我们可以枚举一下求解推导上面是暴力的做法，而就是利用分块的思想将上面的算法复杂度优化为(哈希表做法)或者(map)做法我们令,那么任何一...

2020-05-29

1 750

Treap

平衡树平衡树就是一种可以在log的时间复杂度内完成数据的插入，删除，查找第k大，查询排名，查询前驱后继以及其他许多操作的数据结构。 Treap treap是一种比较好写，常数比较小，可以实现平衡树基本操作的一种平衡树。treap的平衡是基于随机化。是将堆与二叉查找树结合起来所得到...

2020-05-29

1 692

Min_25筛小结

简介 Min_25筛据说可以在处理出含有以下性质的函数f的前缀和:1.，即f是一个积性函数2.可以快速计算。 PS:本文没有关于复杂度的证明。。。预处理首先要预处理两个东西，一个是(n为询问的值域)内的质数。直接线性筛就好了。用表示第i个质数。设共有个质数另一个是，表示所有中满足x最小质因子大...

2020-05-29

1 688

Splay

胡扯因为先学习的treap，而splay与treap中有许多共性，所以会有很多地方不会讲的很细致。关于treap和平衡树可以参考这篇博客关于splaysplay,又叫伸展树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarj...

2020-05-29

1 505

后缀数组

定义——来自百度百科子串一个字符串中连续的一段成为这个字符串的子串。后缀后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 r 的从第 i 个字符开始的后缀表示为 Suffix(i) ，也就是Suffix(i)=r[i,len(r)] 。子串的大小大小比较：关于字符串的大小比较，...

2020-05-29

1 807

概率期望从入门到入坟

基础知识期望的线性性质证明: 前缀和技巧有 n 个随机变量X[1…n]，每个随机变量都是从 1…S 中随机一个整数，求 Max(X[1…n]) 的期望 solution 小结论概率为的事件期望后发生。如抛硬币，抛出正面的概率为期望抛两次后发生。取球游戏取球游戏1 箱子里有个...

2020-05-29

1 1018

简单几步搭建一个自己的个人博客

换博客比更博还勤的我终于决定写一篇博客搭建教程了。。 FAQ Q：需要本地编译。虽然可以直接上传。。但是如果在github上直接编辑也太难受了叭，毕竟不能在线预览。。。 A：对于，博主目前也没有什么很好的办法233。(有个叫似乎可以做到)。所以这篇文章仅适用于主题的博客哦。其实也有些蛮好的主题的。 ...

2020-05-29

2 772

2-sat问题

问题简介在计算机科学中，布尔可满足性问题（有时称为命题可满足性问题，缩写为SATISFIABILITY或SAT）是确定是否存在满足给定布尔公式的解释的问题。换句话说，它询问给定布尔公式的变量是否可以一致地用值TRUE或FALSE替换，公式计算结果为TRUE。如果是这种情况，公式称为可满足。另一方...

2020-05-29

1 1878

快速傅里叶变换简记

多项式一个次数界为的多项式次数界为说明这个多项式最高次项的指数小于系数表示法我们可以只保留多项式每项的系数来描述这个多项式。即表示指数为的项的系数运算多项式之间的加运算，只要将对应项的系数相加即可。即若那么有多项式之间的乘法。若那么其中叫做卷积可以看出暴力计算卷积的复杂度为点值表示法我...

2020-05-29

1 758