不好分类的好题Record

这里装的是一些不太好分类的。

problem 1

给你 \(n\) 个序列，第 \(i\) 个序列的长度为 \(m_i\)，要求在每个序列中选择一个数，每种选法的代价为选择的 \(n\) 个数之和，请求出代价前 \(k\) 小的方案的代价之和。
\(1\le n,k \le 10^5,1 \le m_i \le 10\)。

对于 \(k \le 500\) 的情况这是一个比较常见的贪心问题，我们使用堆合并 \(n\) 次即可。

于是我们尝试用堆来解决这个问题。

首先我们可以知道最小值，然后我们可以在一个一个去改变每一个堆选的值。

定义状态 \((val,x,y)\) 为当前合并出来的数为 \(val\)，现在在第 \(x\) 个堆，这个堆选择的是第 \(y\) 个数。

我们有以下三种情况进行转移：

1. \(y < len_x\)：此时我们可以选择这个堆的下一个数并且抛弃这个数。

2. \(x < n\)：此时我们可以选择下一个堆，并且将选择下一个堆的第二个数.

3. \(x < n\) 且 \(y = 1\)：我们在这个堆撤销次小的，选择最小的，然后选择下一个堆中次小的。也就是跳过第 \(x\) 个堆。

这样子就可以保证不重不漏，然后就可以求出前 \(k\) 小的方案之和了。

problem 2

先抛弃掉颜色只差大于 \(L\) 这个条件，先单独看第二个条件。

看到第二个条件我们可以想到对于原图建一棵 Kruskal 生成树。不知道这个东西是啥的戳这里。

现在我们加上那个条件。

我们枚举每一个新加出来的点，考虑他对答案的贡献。

明显的，贡献就是它的左边子树和右边子树各选出来一个点能组成一个有好点对的方案数量乘上这个点的权值。

我们可以枚举它的左子树中的叶子结点，然后再计算对面有多少个点是不满足条件的。

由于一个子树内的 dfs 序是连续的，所以说这个题目就被我们转换成了二维数点问题。

细节有点多。扔个代码实现 -> code。