定义 SAT 维基百科——Boolean_satisfiability_problem 2-SAT SAT 的简化版本：每个等式中只有两个变量参与。有 个 变量和 个等式，每个等式形如 ，其中 是一个位运算。你要求出一组可行解。 求解 将每个 拆成两个点 和 表示 取值情况。每个限制都能被转化为形如 如果 为 那么 必须为 这样的限制。对于这样的限制，我们建立一条 到 的单向边，表示选了 必须选 。然后跑强连通分量，每个强连通分量内的点代表了这整个分量要一起选。显然如果一个点的两个状态都在一个强连通分量里那么就无解。考虑如何构造方案：我们按照逆拓扑序依次考虑每个点...

主要是为了学习一波 wqs 二分。 首先发现这个题目等价于把树切成 k+1 块 每块内选个直径加起来，也就等价于在树上找 条不相交的链使得收益最大。 考虑树上每一条链都可以拆成两条深度单调的链，所以我们可以设 表示现在在 点 已经选择了 个链 当前 点的状态是（没有链经过/有一条单链待匹配/有链经过），转移一下就可以了，复杂度 对于这一类“恰好选 个” 的问题，如果优化不掉 这一维，就可以考虑 wqs 二分。 我们设 表示选 个的最优值，首先发现 是凸的（导函数单调），也就是平面上若干个点 构成了一个凸壳。上面的暴力 dp 就是求出凸包上所有点的过程，但我们实际上只想求...

作为菜鸡 OIer，本文尽量用通俗的语言去讲解后缀自动机。当然学习后缀自动机前是有一点点前置知识的，我一块给说了。 有限状态自动机（DFA） 定义 确定优先状态自动机 是由： 一个非空有限的状态集合 一个输入字母表 （非空有限的字符集合） 一个转移函数 （例如：） 一个开始状态 一个接受状态的集合所组成的5-元组，可写成形式 工作方式 确定有限状态自动机从起始状态开始，一个字符接一个字符地读入一个字符串 （这里的指示Kleene星号算子。），并根据给定的转移函数一步一步地转移至下一个状态。在读完该字符串后，如果该自动机停在一个属于F的接受状态，那么它就接受该字符串，反之则拒绝该字符串。(...

退役了 给个卫衣安慰一下🤔

自闭了 初赛真的退役了... 本来还以为能进复赛的结果直接自闭了.. 被全场吊打

我是菜鸡

题目链接 题目大意 现在有一个 的矩阵，给定的起始点上有个钢琴，矩阵上有些方格是障碍物，用连续的区间 和一个参数 表示在时间 时会向 方向滑动（上下左右），当然每个时间点可以选择让钢琴不动，不允许钢琴超出边界或者碰到障碍，询问钢琴可能走的最远距离是多少。其中 ,区间个数 ，区间最大的右端点 题解 首先对于这个题目我们有一个很朴素的暴力，也就是记 表示在时间点 时自己在 能走到的最远距离，转移只需要考虑这个时间点是否让钢琴不动：$x',y'O(Tn^2)kf_{i,x,y}i(x,y)dis(x,y)(x',y')(x',y')nO(n^3k)g = f_{i-1}xyxf_x...

DDP（动态 dp），是通过将状态改写成矩阵，然后定义具有结合律的与转移等价的运算，用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。NOIP2018 Day2T3 - 保卫王国考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡，现在回来学一学。我们来找一道简单的题目入手：给定一棵树，点有点权，每次可以修改一个点的权值，每次修改后求这棵树的最大独立集。如果这个问题是静态的，我们可以设出状态 ，表示以 为根的子树内， 这个点是否选择时的最大权值和。转移显然： 我们观察在 dfs 中该 dp 的转移方式：我们发现这类 dp 对儿子的转移顺序 没有要求，...

记录各种我这种数论菜鸡不会的式子。。。可能有很 zz 的式子大佬不要嘲笑 整除与不定方程 证明： 存在整数解。 证明：从右往左推：令 ,则有 从左往右推：考虑构造 ，这样就可以构造出 所有 的解了。令,证明 现在我们尝试解 显然 ,考虑设 。如果 有解即可。递归出口是 ,显然有解。现在考虑如何从递归结果得到解： 所以 。递归下去求解的方法 叫做扩展欧几里得。递归过程中可以顺便处理出 gcd。 inline int exgcd(int a,int b,int &x,int &y){ if(!b){ x = 1,y = 0; ...

定义 维基百科 - 后缀数组让我们来看一下 wiki 上的定义：在计算机科学里, 后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。令字符串 ， 表示 的子字符串，下标从 到 。 的后缀数组 被定义为一个数组，内容是 的所有后缀经过字典排序后的起始下标。 满足 ,有 。 求法 大体思想 这玩意可以使用倍增来求，当然也有常数比较大的 算法。中心思想就是假设我们求出了考虑每个后缀前 个的字典序，现在我们需要扩展到 的情形。首先 的时候十分简单，就是对应的 ASCII 码。考虑每次...

介绍 我们在 OI 题目中，不难会遇到给定一个积性函数 ，求 的题目。虽然对于积性函数我们已经有成熟的线性筛方法来说可以做到 ，可是有的出题人就是毒瘤，可是有的题目的数据范围要求给出一个复杂度小于线性的做法，这时候神仙就搞出了杜教筛这一东西。 前置芝士 芝士1：线性筛 首先我们知道，基本上所有的积性函数都可以线性筛。积性函数的特点： 如果我们想线性筛积性函数，首先这个过程一定是建立在欧拉筛素数上的，然后我们考虑一些性质： 当 为质数时， 的取值 当这个数不是第一次被筛到的时候，取值的特性 我们拿 举例：什么你还不知道 是什么？快去看看莫比乌斯反演吧。首先发现 ，。然后发现当 能不...

因为上次小白月赛被喷毒瘤，这次我被迫放了更多的水题。CDF 出题人 @_Qingyu A.School 简单的枚举题。 直接 枚举每对人判断是否成立即可。 注意到输出的字符串为 YE5 和 N0 即可通过此题。通过代码 B.Probability 简单的模拟题。 题目等价于求分数 的小数点后 到 位的所有数字。 直接暴力模拟除法过程是肯定会 T 的，但是我们发现我们不用从头开始模拟，只需要从 位开始模拟就可以了。 直接通过快速幂+取模算出第 位的数字。然后我们发现 ，所以暴力枚举除法过程就可以。 时间复杂度 。通过代码前两题太良心了吧，题解这么短。 C. Review 简单的图论题...

看来牛客网练习赛的难度是该提高了 QAQAQ 另外，出题人进队稳了！！！Orz

A.签到题 仔细阅读代码，发现题目需要你维护一个线段集合，***插入线段，删除线段和求线段并长度。 我们考虑一种非常暴力的做法：对于这个数轴建出线段树，然后插入删除对应了区间加值操作。 我们来考虑一下询问操作：最朴素的方法是查询每个点是否有值然后统计答案。我们可以考虑对每一个线段树上的节点维护一个 min 值，这样遍历到一个节点的时候如果当前节点的 min > 0 那么说明这个线段树节点对应的区间是所有线段并的一部分。 当然这样的话还是不一定能过的，但是注意到数据随机生成，所以查询操作仅为总操作的 ，且删除操作大概率不会触发。 时间复杂度最差是的，但是由于数据随机生成，所以可...