eat12ac

题解

未归档(8)

/ 注册

全部文章 / 题解（共4篇）

K - K-Bag

K 思维思路一个 Part-K-Bag 一定是由 "零个或多个 K-Bag" + "不含 K-Bag 的 Part-K-Bag" 组成。为方便起见，下称 "零个或多个 K-Bag" 为 K-Bags, "不含 K-Bag 的 Part-K-Bag" 为 Exclude-K-Bag。 1、我们先...

2020-07-31

0 638

D - Quadratic Form

D 凸优化题意给出正定的实对称矩阵和向量,向量满足约束：，试求思路构造拉格朗日函数，，其中，那么首先对求偏导，得：得到取最大值时，有：由拉格朗日对偶性，可得：再对求偏导，得：得到：，联立，可得，取最大值时：同样地，取最大值时：，故：高斯消元求逆即可，时间复杂度...

2020-07-30

0 511

A - B-Suffix Array 题解

A 思维思路函数关于字符串的后缀数组并不好求，因为每个的后缀并不是的后缀，我们尝试正难则反。因此，我们考虑函数，满足：1、2、3、如果找不到这样的，可以发现一个01字符串，它对应的越大，那么它的越小，可知与是反序关系。由于每个的后缀就是的后缀...

2020-07-30

0 706

F - Fraction Construction Problem 题解

F 数论题意给出，要求：且试求：思路原式变形可得到，将化为最简分数，由最简分数的唯一性可得：，当时，我们令，可以得到：，这是一组可行解。当时，我们不能直接令。我们希望能找到的互质因子，使得，从而代入上述方程，通过扩展欧几里得解出和。如果找不...

2020-07-18

11 699