查看原题请戳这里 首先，这道题让求最大值最小，于是我们就很自然得想到了去二分这个最小值。 那么，怎么check呢？ 我们发现，如果直接暴力去check，即二分区间长度+暴力枚举字符串+暴力枚举区间左端点+暴力对比，那么时间复杂度是$O(n^2m^2\log_2n)$的。（引人深思的复杂度……） 很显 ...

图论图论部分转载于Shu_Yu_Mo の blog 2-SATSomeThing 又名2-SAT-2 判断有无解 确定变量 确定关系表达式 变量的取值有两种 %d - SAT 表达式有多少个变量 SAT - %d 每个变量的情况个数 加边规则 如果$x−−>yx –> yx−−> ...

查看原题请戳这里 一道五维DP的题目 首先，我们发现，当我们排完部分队形时，已经排好的队形对后续的方案数是有影响的，显然我们这样DP是非常困难的。所以，我们可以选择安装身高顺序插入，每次的决策是第i个人插入的位置。 我们可以发现，如果我们要向第i行的末尾插入一个人，那么第i行的状态必须满足以下两个 ...

作用高斯消元可以用来解线性方程组，也有一些别的用途。 算法流程我们来看这样的一个方程组： $ x+y+z=3$ $2x+3y+z= 6$ $4x+y+2z=7$ 然后我们把每一项的系数提取出来，就得到如下的矩形 ： $1 \ 1 \ 1 \ 3 $ $ 2 \ 3 \ 1 \ 6 $ $ ...

这里给出的两份代码都是关于洛谷P3383 【模板】线性筛素数的。两份代码不是一块敲的，码风可能稍有区别。 Eratosthenes筛法Eratosthenes筛法的核心思想是对于任何一个数，它的整倍数一定不是素数。时间复杂度：$O(n log log n)​$code: 1234567891 ...

查看原题请戳这里首先，题目告诉我们有以下两种操作： 行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色） 列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色 但是，实际上我们只需要进行其中的一种操作就可以了。即我们两种操作混着用其实是没有什么效果的，这一点 ...

查看原题请戳这里我们先来看一下这道题如果先转化成森林再处理的话，一共有如下几个操作： 删除一条边 加入一条边 查询两点间路径权值和 这不是一道LCT的题吗……然而LCT代码复杂度太高了，这里我们来讲一下如何用分块来解决这道题。首先，我们将这$n$个装置分成$\sqrt n$块，每块有 ...

查看原题请戳这里一道典型的区间dp。一共需要走两次，我们不妨同时处理这两条路径。这样，我们既可以方便地处理两条路径重合的情况，也可以减少代码的时间复杂度。最朴素的想法是开一个四维数组$f[x_1][y_1][x_2][y_2]$表示当两条路径分别处理到$(x_1,y_1)$和$(x_2,y_2)$时 ...

查看原题请戳这里 前言这道题我做了半年qwq一道非常典型的区间dp题目要求是从小渊到小轩再回到小渊，那么我们不妨从小渊开始求两条不重合的去小轩的路径。如图，当我们找到了一条路径后，那么这张图就被分成了两部分，我们的另一条路径只可能存在于其中的一部分中，像这样：我们可以用$f[x_1][y_1][ ...

题意简述给你$n$个物品，第$i$个物品的体积为$w_i$,价值为$v_i$,可以选$m_i$次。现在你可以选的物品总体积不超过$W$，求你能获得的最大的价值 解题思路感觉把多重背包的问题模型重温了一遍有没有……由于数据范围很大，所以我们直接将选$m$次拆成有$m$个物品可选这个暴力的方案是会超 ...