CVBB ACM Team

• 分类：数学，KKT。
• 题意：给定一个 $n\times n$ 的正定二次型 $A$ 以及 $1\times n$ 的 $B$，找到 $(x_1,x_2,\cdots,x_n)$ 满足 $X^T A X \le 1$ 并且使得 $BX^T$ 最大，求最大值的平方。$n\le200$
• 题解：答案即为 $BA^{-1}B^T$。这道题即为 $KKT$ 模板。
  

令 $F(x)=BX^T+\lambda(XAX^T-1)$ 则取极值的条件为$$\begin{cases}B_i+2\lambda\sum_{j=1}^{n}A_{i,j}x_j=0 \\ XAX^T-1\le 0 \\ \lambda (XAX^T-1) = 0 \\ \lambda \ge 0\end{cases}$$ 易知 $X=\frac{-B{(A^{-1})}^T}{2\lambda}$ ,代入 $\lambda (XAX^T-1) = 0 $ 可知 $\frac{BA^{-1}B^T}{4{\lambda}^2}=1$
最大值的平方则为 $(BX^T)(BX^T)=\frac{BA^{-1}B^TBA^{-1}B^T}{4{\lambda}^2}=BA^{-1}B^T$

• comment：
• 数学 牛客多校第一天D

• 分类：
• 题意：
• 题解：
• comment：
• 单调栈 CF815D

• 分类：
• 题意：
• 题解：
• comment：

• 分类：
• 题意：
• 题解：
• comment：

• 2020.07.16 Codeforces Round #561(Div. 2)

• 牛客多校第一天D
  • comment:KKT get

• 2020.07.11 AIsing Programming Contest 2020

• CF815D

• 2020.07.11 AIsing Programming Contest 2020
• 2020.07.12 Codeforces Round #655 (Div. 2) Virtual participation
• 2020.07.15 Educational Codeforces Round 91 (Rated for Div. 2) Virtual participation

• 2020.07.11-2020.07.17