NumLuck

摘要： 前置知识 Trie树(字典树),KMP(思想) AC自动机全名(这个不重要)，是用于字符串匹配的玩意。 我们知道，在一个文本串里匹配模式串可以用KMP,但如果是匹配多个文本串呢？ 假设有\(2\times 10^5\)个模式串，又该如何应对呢?这时就要用到AC自动机了。 先看一个题 文本串: abc 阅读全文

摘要： 三角函数 基本操作 \(\sin^2\alpha+\cos^2\alpha=1\) \(\tan\alpha=\Large\frac{\sin\alpha}{\cos\alpha}\) 诱导公式 角 \(\alpha+2k\pi\) \(\pi+\alpha\) \(-\alpha\) \(\pi- 阅读全文

摘要： 介绍 李超线段树是一个特别神奇的东西。TA可以把几何和线段树完美的融合起来。 题目中如果说给你一些一次函数(形如\(kx+b\))，也就是直线，或者给你一条线段(四个端点的坐标)就可以考虑用一下。 例题:洛谷P4254 题目概括:给你一些直线，同一个\(x\)坐标下\(y\)坐标的最大值。\(\co 阅读全文

摘要： 莫队 一种由莫涛提出的算法。 要求的是一个区间\((l,r)\)上的某个问题 如果一个函数\(f(l,r)\)可以轻易地转换为\(f(l+1,r)\),\(f(l-1,r)\),\(f(l,r+1)\),\(f(l,r-1)\)，那我们就可以用类似于滑动窗口，双指针的东西维护每个值。然后移动左右区间 阅读全文

摘要： 这篇文章是关于SAT做法的记录。 2-SAT是解决关于两个点之间的关系的问题 题目 link 庆功宴中一共邀请了N对夫妻，每对夫妻中最多只有其中一人出席。在总计2N个人中，某些人之间存在着不共戴天的矛盾（夫妻之间不存在矛盾QWQ），有矛盾的2个人不能同时出席。 现在，给定这2N个人的关系，请回答是否 阅读全文

摘要： 例题 P3387 【模板】缩点 遇到这种题，你们是不是都很懵。每个点都只能经过一次，而且图里面面还有环。 法1 暴力做法都会吧。既然没规定开头，那就枚举起点，跑单源最长路。然后枚举过的打上标记。 因为\(n<m\)，所以我们用\(\mathrm{spfa}\)。算法复杂度\(O(n^2\log n) 阅读全文

摘要： step1 首先我们设 \(mn_{i,j}\)为砝码 \(i\) -砝码 \(j\) 的最小值(下文以\(a_i\)和\(a_j\)代替)。 \(mx_{i,j}\)为\(a_i-a_j\)的最大值。 当设\(a_i\)和\(a_j\)的关系为\(g_{i,j}\)。 当\(g_{i,j}\)为\ 阅读全文

摘要： 题目链接 题目大意 给定一段长度为\(n\)的数组\(a\)和\(c\)，表示\(i\)的大小和将 \(a_i+1\) 的费用。如果最后剩\(k\)个不同的\(a_i\)就将费用加上 \(X\times k\)。 题目分析 首先该题想让我们的最后剩下的 \(a_i\) 个数最少，那我们就没必要创造新 阅读全文

摘要： 凸包简介 凸包就是把一些点的最外围那一圈的点围起来。 就像是桌上有一圈钉子，用一根橡皮筋套在最外围，然后收缩橡皮筋。形成的图形就是这一圈点的凸包。 常见的凸包算法有两种。\(\mathrm{Graham}\)算法和\(\mathrm{Andrew}\)算法。 Anderw 通过按照\(x\)坐标或\ 阅读全文