文章

本文所包含的思路来自于 NCC79601 * 算法剖析 简单来讲，背包退火就是用模拟退火的思路解决某些类型的背包问题，继承了模拟退火的玄学复杂度，也继承了它的不稳定性，所以能够有效地解决大背包问题的 TLE 问题。这个算法能够把数十行的代码优化部分转移为 洗把脸 调参的问题。 例题 ：LuoGuP1 阅读更多…

题目分析 不难发现需要枚举 D 和 A，然后鱼头鱼尾分别处理。 对于鱼尾，其实就是对着 A 的半平面内两条到 D 距离相等的线段组成的，枚举 D 后，将其他点极角排序，然后扫描线即可解决。 对于鱼头，也就是 BC 这条线段要垂直于 AD，且 BC 的中点在 AD 上。则预处理枚举每个 BC，将这个点 阅读更多…

在我的不断探索发现下，我意识到 DFS 似乎可以用来做数独…… 于是乎就上手操作了一下，然后就做出来了？ 其实思路很简单，就是简单的 DFS (废话，本蒟蒻都想出来了能不简单吗) 就是模仿人填数独的过程，只是更加无脑。 一个个试起走，放不了就回溯，直到解出答案，输出 真的就只有那么简单了，秒杀人脑啊 阅读更多…

题目分析 30 分做法：初始，所有 $(x,x)$和所有满足 $x,y$同色且中间有边的 $(x,y)$之间都有回文路径。将所有点对放入队列中，从两个端点开始往周围各找一个同色的点，就可以扩展出新点对，满足存在回文路径。复杂度 $O(m^2)$。 优化建图是这样的，首先只连上那些连接同色点的边，原图 阅读更多…

题目分析 性质： 所有积水高度小于等于 1 号点的点可以直接丢掉。 所以，将留下来的水的高度都改成其原本的高度-1 号点高度，最后答案再加上 1 号点的高度。 假如被要求进行两次合并，有两杯水 $h _ 1<h _ 2$，则一定先合并低的，再合并高的。 证明：先合并低的：$\frac{1}{2 阅读更多…

看懂了后发现 $\texttt{DDP}$ 其实不难呢…… 其实主要思想就是将 $\texttt{DP}$ 转移式搞到矩阵上，然后如果是树形 $\texttt{DP}$ 的话就可以直接上树剖或者是 $LCT$ 进行维护，当然还可以用全局平衡二叉树 (不费) 。如果只是线性的话 阅读更多…

传送门 没错题目名字一模一样（： 然而这是我在搜上一题的时候偶然遇到的一道题，觉得蛮好玩的就做了做 题目大意 给一棵节点全白的树，你要把它一些点涂黑，需要满足若干个形如在子树 $u_i$内有不少于 $y_i$个黑点，在子树 $u_i$外有不少于 $y_i$个黑点的限制，求最少黑点数 题解 注意到子树外的 阅读更多…

门 题解 刚开始想了半天以为是什么简单的性质比如说子树权值和的关系，但是这个等差数列加权就很恶心呀根本不知道怎么搞。 首先我们需要贪心考虑一些东西，发现如果一个非根节点的权值如果是当前整棵树里最大的，那么当它的父亲被选的时候下一个选的肯定就是它，否则通过调整法显然能得到更小的权值和。这个调整就不仔细 阅读更多…

传送门 感觉自己树上贪心太差 (NOIP 血的教训)，所以来练几道。 为了方便叙述，我们将 $m$个点称为放火点，有炸药的点叫做炸药点。 首先考虑一下能不能 $dp$ 记 $dp[i][j]$表示第 $i$个点时间为 $j$所需要的最小放火点数，所求即为第一个 $dp[1][j]\leq m$。 这 阅读更多…

喵门 序列自动机好简单啊 首先我们有一个字符串 $S$，记 $nxt[i][j]$表示 $S$的第 $i$位之后第一个字符 $j$的位置。 然后介绍构造算法，其实。。。按照定义来说，这样写就行了 inline void build () { fd (i, n, 1) { memcpy(nxt[i – 阅读更多…