solution 以为根进行。 设表示以为根的子树中，是()否()选择了这个点，这个点是()否()被游览过的方案数。 答案就是 考虑如何转移。 对于，既然这个点没被游览过，那么他的儿子就肯定不能选择，而且因为没选这个点，所以他的儿子就不能通过选择来被游览，所以就只能从转移过来。 对于，可以覆盖他的儿子，那么他的儿子是否被浏览过都可以，但是他的儿子不能被选择过，因为不可能有相邻的两个点被选择。所以就从转移过来。 对于，这个状态说明要被他的儿子覆盖，而他的儿子至少有一个要被选择，所以我们先从。转移，如果每个儿子都是从转移过来的，就再枚举一下让哪个儿子从转移。取最大的答案即可。 PS：看完别人写的题...

solution 提供一种贪心+序+线段树的做法。 为了方便，我们以小的初始位置为根。 大概理解完题意，可以发现有一个比较显然的性质：每一回合结束，每个与小之间的距离不会变大。 然后考虑小移动所产生的影响。 考虑当小开始移动时，如果小从移动到了的一个儿子。那么这一回合结束，子树中的每个Youyou与小z之间的距离就会减小2。其他的与小之间的距离不变。 如果小从移动到了他的父亲，那么除了这个子树内的外，其他的与小之间的距离都会减小。 然后我们考虑贪心，初始的时候每个与小之间的距离就是所在节点的深度。我们每次让小走向离他最远的那个。 这样显然是对的，因为如果小不走向这个最远的，这个与小之间的距离将...

BSGS 算法又称大步小步算法 算法主要用于解以下同余方程 其中,即与互质 前置知识 根据欧拉定理，所以的循环节为.也就是说如果上面的方程有解，那么肯定有，所以我们可以枚举一下求解 推导 上面是暴力的做法，而就是利用分块的思想将上面的算法复杂度优化为(哈希表做法)或者(map)做法我们令,那么任何一个都可以被表示成的形式则原式可表示为$$ 实现 所以先将右边预处理出来，存到表中。然后枚举左边的计算出，并在表中查询。枚举的复杂度都是，常数取决于表有个细节的地方，一般我们都是要求最小的，所以我们希望更大，更小。所以在往表中存的时候，保留更大的那个。从小到大枚举，遇到可行答案直接输出即可。 例题 l...

平衡树 平衡树就是一种可以在log的时间复杂度内完成数据的插入，删除，查找第k大，查询排名，查询前驱后继以及其他许多操作的数据结构。 Treap treap是一种比较好写，常数比较小，可以实现平衡树基本操作的一种平衡树。treap的平衡是基于随机化。是将堆与二叉查找树结合起来所得到的数据结构。 treap在插入数时，给每个数赋了一个新的随机的值id。在以后的操作中，必须始终使得treap中的id构成一个堆的形态才可以。这样就达到了平衡的目的。 定义 struct node { int ch[2],val,id,cnt,siz; }TR[N]; ch[0/1]...

简介 Min_25筛据说可以在处理出含有以下性质的函数f的前缀和:1.，即f是一个积性函数2.可以快速计算。 PS:本文没有关于复杂度的证明。。。 预处理 首先要预处理两个东西，一个是(n为询问的值域)内的质数。直接线性筛就好了。用表示第i个质数。设共有个质数 另一个是，表示所有中满足x最小质因子大于或者x是质数的之和。 这样一来，表示的就是中所有质数的f值之和。这个东西后面会用到。 那么来看一下这个值该如何求。 显然，如果那么。因为这时的已经只表示中所有质数的f之和。并不会比多删除掉任何东西。 如果呢？我们可以理解为埃氏筛法的过程，与的差别就是筛掉了的倍数。那么就好像可以转移了。问题就在于如...

胡扯因为先学习的treap，而splay与treap中有许多共性，所以会有很多地方不会讲的很细致。关于treap和平衡树可以参考这篇博客 关于splaysplay,又叫伸展树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。splay与其他平衡树相比功能更加强大，可以处理区间问题。可以说其他平衡树可以做的splay几乎都能做。所以很多大佬都说平衡树会写splay就好了。唯一的缺点可能就是常数要比tr...

定义——来自百度百科 子串一个字符串中连续的一段成为这个字符串的子串。后缀后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 r 的从 第 i 个字符开始的后缀表示为 Suffix(i) ，也就是Suffix(i)=r[i,len(r)] 。子串的大小大小比较：关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i 从1 开始顺次比较u[i]和v[i]，如果u[i]=v[i]则令 i 加1，否则若u[i]<v[i]则认为u<v，u[i]>v[i]则认为u>v（也就是v<u），比较结束。如果i>len(u)或者i...

基础知识 期望的线性性质 证明: 前缀和技巧 有 n 个随机变量X[1…n]，每个随机变量都是从 1…S 中 随机一个整数，求 Max(X[1…n]) 的期望 solution 小结论 概率为的事件期望后发生。如抛硬币，抛出正面的概率为期望抛两次后发生。 取球游戏 取球游戏1 箱子里有个球，你要从中拿次球，拿了后不放回，求取出的数字之和的期望。 solution 取球游戏2 箱子里有个球，你要从中拿次球，拿了后放回，求取出的数字之和的期望。 solution 取到每个球的概率均为,故答案仍为 取球游戏3 箱⼦子⾥有 n 个球 1…n，你要从⾥面拿 m 次球，拿了后以 p1 的概率...

换博客比更博还勤的我终于决定写一篇博客搭建教程了。。 FAQ Q：需要本地编译。虽然可以直接上传。。但是如果在github上直接编辑也太难受了叭，毕竟不能在线预览。。。 A：对于，博主目前也没有什么很好的办法233。(有个叫似乎可以做到)。所以这篇文章仅适用于主题的博客哦。其实也有些蛮好的主题的。 Q：那我知道了，找个在线编辑器编辑好，然后直接去上传不就行了么？？ A：你真的能忍受国内的访问速度？？这里讲的方法可以在线更新哦。。。 Q：那我需要用到什么呢？？ A：一个账号(申请只需要邮箱)。一个浏览器。(最好有个国内代码托管平台(如码云)的账号)。 搭建博客 首先来讲如何在上搭建一个博客。网上...

问题简介 在计算机科学中，布尔可满足性问题（有时称为命题可满足性问题，缩写为SATISFIABILITY或SAT）是确定是否存在满足给定布尔公式的解释的问题。换句话说，它询问给定布尔公式的变量是否可以一致地用值TRUE或FALSE替换，公式计算结果为TRUE。如果是这种情况，公式称为可满足。另一方面，如果不存在这样的赋值，则对于所有可能的变量赋值，公式表示的函数为FALSE，并且公式不可满足。例如，公式“a AND NOT b”是可以满足的，因为可以找到值a = TRUE且b = FALSE，这使得（a AND NOT b）= TRUE。相反，“a AND NOT a”是不可满足的。——百度...

多项式 一个次数界为的多项式次数界为说明这个多项式最高次项的指数小于 系数表示法 我们可以只保留多项式每项的系数来描述这个多项式。即表示指数为的项的系数 运算 多项式之间的加运算，只要将对应项的系数相加即可。即若那么有多项式之间的乘法。若那么其中叫做卷积可以看出暴力计算卷积的复杂度为 点值表示法 我们可以选个值代入多项式从而得出个二元组。可以证明，通过这个点对可以确定这个多项式。还原这个多项式用高斯消元即可。点值表示法的优点是进行多项式的加法和乘法只要将相加或者相乘即可。 求值与插值 考虑如何可以比较快速的计算卷积。因为点值表示计算乘法比较方便。所以我们可以把系数表示法转换为点值表示法。然后进...

重新学习了一遍莫比乌斯反演，整理一下。 莫比乌斯函数 莫比乌斯函数是一个积性函数。$x1.x=1\mu(x)=12.x\mu(x)=(-1)^kkx3.\mu(x)=0$莫比乌斯函数是个积性函数，所以可以线性筛。 性质 $2.$ 线性筛莫比乌斯函数代码 for(int i = 2;i <= END;++i) { if(!vis[i]) { mu[i] = -1; dis[++js] = i; } for(int j = 1;j <= js && dis[j] *...

牛客可不可以开发一个学校分类的功能。 可以根据选择学校然后查看这个学校内的所有用户，这样就可以很方便的找到校友了（方便交友）。

solution 先从三个排名中选择两个，假设是，就是要找对于每个队伍，满足a比他大并且b比他小的队伍有多少个。这就是一个二维偏序的问题，先按照a从大到小排序，这时每个位置左边都满足a比他大，所以从左向右扫的过程中维护一个权值树状数组，每次将一个元素的b***去，并且在树状数组上查询小于当前这个b的元素有多少个。 对于另外的两种组合同理。 显然这样肯定会有一些队伍组合被考虑了多次。只要找到每对队伍多被考虑了几次即可。 考虑对于两个队伍，其中一个的排名是，另外一个的排名是。因为每个元素表示的都是排名，所以肯定不会有相同的两个元素。如果同时满足，肯定不会被计算到，所以不用考虑。那么剩下的一种情况就...