leiyuanze

摘要： 模板 \(Problem：\) 多个模式串匹配文本串，求能合法匹配的个数 \(limit：1 \leq n \leq 10^6\) \(templete：\)\(Luogu P3808\) \(Code\) #include<cstdio> #include<cstring> using names 阅读全文

摘要： 题目大意 动态维护数列中大于等于某个数的极长连续段的个数。 思路 我们考虑每段的开头，记为 \(i\)，高度为 \(a_i\) 那么此时水淹的高度必然满足 \(a_{i-1} < x \leq a_i\) 这样的 \(x\) 在此处会给答案贡献加一 那么我们考虑所有的这种位置，开一棵权值线段树，对于 阅读全文

摘要： 题目大意 求形如 \(\sum_{i=1}^n |a_ix + b_i|\) 的最小值 思路 我们显然可以先把系数 \(a\) 提出来 于是就成了 \(\sum_{i=1}^n |a_i|·|x + \frac{b_i}{a_i}|\) 对于任意一个 \(i\)，它的零点在 \(-\frac{b_i 阅读全文

摘要： 解析 首先我们得明确：分割的顺序是无所谓的 不然我们很难列出转移方程 那为什么呢？ 假若当前我们把某段序列分成三段，依次记为 \(x,y,z\)，每段和记为 \(s_x , s_y , s_z\) 那么如果我们先分出 \(x,y\) ，那么 \(ans = s_x \times (s_y+s_z) 阅读全文

摘要： 解析 转移方程很容易推：\(f_i = \max(f_j + a * (s_i - s_j)^2 + b * (s_i - s_j) + c)\) 然后当 \(j>k\) 时，如果 \(j\) 更优 那么 \(f_j + a * (s_i - s_j)^2 + b * (s_i - s_j) + c 阅读全文

摘要： 解析 预算费用，和Luogu P2365 任务安排一样 得到了同样的式子 但是我们发现 \(sumt_i\) 可能小于零 也就是说我们需要的斜率可能不再具有单调性 所以我们要维护整个凸壳 那么怎么找到最佳的决策点呢？ 其实就是 \(slope(m,m-1) < sumt_i\) 且 \(slope( 阅读全文

摘要： 题目 思路 呵呵，正解并不是什么神奇的方法 而是最原始的最粗暴的最有用的最万能的————搜索 依题模拟即可 \(Code\) #include<cstdio> #include<cstring> using namespace std; const int N = 35; int n , m , m 阅读全文

摘要： 题目大意 判断给定 \(n\) 个矩形将平面分成了几个区域。 $1 \leq n \leq 50$ 坐标 \(x,y\) 均满足 $0 \leq x,y \leq 10^6$ 思路 注意到 \(n\) 很小 所以我们直接离散后暴力给坐标系加数表示矩阵的覆盖和重叠 答案就是连通块的个数 注意细节 \( 阅读全文

摘要： 题目大意 没什么，就是把原本汉诺塔的三根柱子改成四根，求最少步数 其中 $1 \leq n \leq 1000$ 思路 设 \(f_{i}\) 表示四根柱子中把其中一根 \(i\) 个移到另一根的最小步数 \(g_i\) 类似，改成三根柱子 那么 \(f_i = \min(g_j * 2 + f_{ 阅读全文

摘要： [SHOI2006]仙人掌 简要解析 其实很简单 只要普通树形 \(dp\) 就行了 \(f_x\) 表示 \(x\) 能向下延深的最大距离，\(v\) 是 \(x\) 的儿子 当一个点不属于任何环时 \(f_x = \max(f_v + 1)\) 这是更新 \(ans = \max(ans , f 阅读全文

摘要： 题面 思路 考场想到 \(tarjan\) 缩点 然而忘了缩点怎么打 于是甩了个暴力 改题时学了个圆方树 发现挺好用 于是······注意重边 \(Code\) #include<cstdio> #include<iostream> #include<cmath> #include<map> usi 阅读全文

摘要： 题目 解析 看到这题，没想到 \(dp\) 果断打了暴力 暴力理应只有 $30$ 左右的样子 然而我加上了些奇技淫巧竟然有 $80$ 分！ 惊到我了！ 我 $80$ 分的暴力： 很容易想到找到所有可找的路计算方差取最小值 然后发现计算方差的所有数中，最大最小差值越小越好 于是果断二分差值，然后枚举最 阅读全文

摘要： 解析 设 \(dp_i\) 表示处理完前 \(i\) 个时所花费的最小费用加上 \(i\) 因多分一组对后面产生的费用 \(dp_i = dp_j + sumt_i \times (sumf_i - sumf_j) + S \times (sumf_n - sumf_j)\) 然后斜率优化即可（\( 阅读全文

摘要： 不能算解析的解析 很神仙的题 知道做法后很容易实现 这里不写题解 推荐一个：4417. 【HNOI2016模拟4.1】神奇的字符串 感谢写此博文的神犇！ \(Code\) #include<cstdio> using namespace std; const int N = 1e5 + 5; int 阅读全文

摘要： 题目 解析 很容易想到的 \(dp\)： 设 \(f_i\) 表示已经处理完 $1..i$ 并且 \(i\) 是直接复制的需要的最小花费 那么 \(f_i=f_j+(i-j) \times (i-j-1)+c_i\) 这就是经典的斜率优化 \(dp\)，一般我们考虑两个决策谁会更优 考虑 \(j,k 阅读全文