## 能够解决的问题 一些满足凸性的东西。 ## 算法 ### wqs 二分 #### 能解决的问题 让你求恰好用 $k$ 步解决问题的最小代价，而且最小代价关于步数的函数有凸性。 如：求恰有 $k$ 条白边的最小生成树，求把序列恰好分成 $k$ 段的最小权值。 其实就是求一个凸函数 $f(x)$ 的某一项。 ####…

在讨论《把代码全部放在namespace》回复：

匿名 namespace啥意思

在讨论《把代码全部放在namespace》回复：

@[oyoham](luogu://user/957618) 好久没遇到你了

在讨论《把代码全部放在namespace》回复：

那有没有一些还是不能用的？

在讨论《把代码全部放在namespace》回复：

ok,tks

是不是就可以为所欲为了？（比如 `int y1,max;`）

在讨论《一般NOIWC需要CSP多少分才能去》回复：

大概 S 100+100+100+60或100+100+80+80

在讨论《一般NOIWC需要CSP多少分才能去》回复：

你就奔着全省前十就行了

请在 `clear` 后再 `shrink_to_fit` 释放空间。

在讨论《RE了，求助》回复：

@[litjohn](luogu://user/537934) 刚放假（从空港校区），机房不开，来不了，明天去长春

https://codeforces.com/problemset/submission/375/329267178

这就是 P4391 稍微加强一下啊，感觉绿都可以

[题目传送门](https://www.luogu.com.cn/problem/P4721) 前置知识：FFT / NTT。 > 给定序列 $g_{1\dots n - 1}$，求序列 $f_{0\dots n - 1}$。\ > 其中 $f_i=\sum_{j=1}^if_{i-j}g_j$，边界为 $f_0=1$…

## 能够解决的问题 有不好刻画/转移的~~勾石~~限制的一些问题。 ## 优缺点 优点：代码简单，且这一类基本上都是区分度高的题。 缺点：适用性不广泛。 ## 思路 既然有~~勾石~~限制，那我们就**宽限**！ 1. 我们可以尝试将限制变简单，然后就可以考虑能否反演。 **注：此时一定不要想着这个新限制能否转移，否…

在文章《数学 Trick 之：双线 Catalan / 反射容斥》发表评论：

是的呢

## 能够解决的问题 形如这一类问题：从 $(0, 0)$ 到 $(n, m)$，每次往上或右走，不能走到给定的两条直线。 ## 优缺点 无 ## 思路 首先，如果你不会单线做法，可以先看看 Catalan 的内容。 我们先回顾一下一条直线。 ![](https://cdn.luogu.com.cn/upload/im…

# [CF1009F Dominant Indices](https://www.luogu.com.cn/problem/CF1009F) 题解 ## 题目大意 给一棵 $n$ 个点的以 $1$ 为根的树，对每个点求最小的 $k$ 使得其子树中到它距离为 $k$（边权为 $1$）的点最多。 $1 \leqslant…

# [P1600 [NOIP 2016 提高组] 天天爱跑步](https://www.luogu.com.cn/problem/P1600) 题解 ## 题目大意 给定 $n$ 个节点的树，$m$ 个人分别走 $m$ 个路径，从时刻 $0$ 开始走，$1\text{s}$ 走一条边，询问对于每个点 $i$，在时刻 $…

# [P3177 [HAOI2015] 树上染色](https://www.luogu.com.cn/problem/P3177) 题解 ## 题目大意 将 $n$ 个点的树染 $K$ 个黑点，其余为白点，使黑点两两距离和加白点两两距离和最大。 $1 \le K \le n \le 2000$。 ## 思路 这个“两两…

在讨论《请求撤下题解》回复：

666

## 能够解决的问题 区间前缀最大值计数，单点修，可强制在线。 ## 优缺点 代码好写，但是正常情况下没有吉司机线段树快。 ## 思路 首先，这是一个区间问题，所以我们考虑线段树求解。 我们令一个节点表示他所统辖的区间的答案。 那么问题就变成了：如何合并两个区间（也就是说如何写 pushup）？ 我们让每个端点再维护一…

## 能解决的问题类型 需要将两个值域有交可重集合并的问题。 ## 优缺点 无 ## 思路 这个 Trick 基于 FHQ。 首先，让我们回顾一下 FHQ 的 merge： ```cpp int merge(int l, int r) { if (node[l].randd <= node[r].randd) { pu…

## 能够解决的题目类型 这个 Trick 能解决的题目形如： - 给定 $n$ 个节点的**有根无边权有点权**树。 - 有 $m$ 个询问，每个询问形如点 $x$ 的**子树内**与 $x$ **深度差**不超过 $k$ 的点的极值/排名/和。 - $O(n\,log\,n)$ 可过。 ## 优缺点 优点：可以强制…

## 前言 lxl 的课属实让我受益匪浅，这篇博客就来谈一谈他自创的算法：插入-标记-查找。 ## 算法概述 这是一个离线算法，用到了扫描线思想和数据结构，它可以**秒掉**这样一类问题： - 给定 $n$ 个映射 $f_i(x)\;(i \in [1,n])$ 和 $m$ 个询问 - 每个询问**形如**给定 $x,…

在讨论《【1.3 更新】洛谷题解补充计划》回复：

hp

在讨论《建议升蓝》回复：

你好

# AT_abc017_4 [ABC017D] サプリメント 题解 ## 题目大意 给定长度为 $n\,(1\le n\le 10^5)$ 的数组，要从位置 $1$ 跳若干次到位置 $n + 1$。每次至少跳一格，而且每次跳的区间（包含起终点）不能有重复数字。求方案数。（**请理解此段，否则后面可能比较难懂**） ##…

# P11311 漫长的小纸带 题解 ## 题意 给定一个长为 $n$ 数组 $a$，将他分成若干段，每段的代价为这一段数字个数的平方，求最小代价。 ## 思路 看到分段、最小代价这些字眼，于是考虑 dp： 设 $dp_i$ 表示 $1$ 到 $i$ 的最小代价，$s_{i,\,j}$ 为 $i$ 到 $j$ 的不同数…

# CF822D My pretty girl Noora 题解 个人认为题意翻译已经足够清晰，于是我就不再赘述了。 ## 思路 首先，看到筛选方法，感到很奇怪，于是我便觉得这是到找规律题，于是开始推式子。 假设按照 $x$ 人一组淘汰，那么： - 这一组淘汰 $x$ 个人； - 这一组有 $\frac{x\times…