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：KKT get。

分类：单调栈。

题意：每张卡片有三个属性a,b,c，其上限分别为A,B,C，现在有n张卡片，定义一张卡片能打败另一张卡片当且仅当至少两项属性要严格大于另一张的对应属性。问在所有可能的卡片中，有多少种卡片能打败这全部n张卡。

题解：将题目转化为求哪些卡片不能打败所有的卡，即变成求一个立方体并，对于某属性$a$和另一张卡片${x,y,z}$，如果$a\leq x$，则$b>y \& \& c>z$为假，否则$b \leq y\&\&c\leq z$，此时就可以转化为求矩形并。单调栈预处理之后枚举$a$统计即可。

comment：偏序联系到单调栈，然后扫描，经典。

分类：生成函数。

题意：设十元组$(s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2)$满足下列条件，$0 \leq s_1 < s_2,0 \leq n_1 < n_2,0 \leq u_1 < u_2,0 \leq k_1 < k_2,0 \leq e_1 < e_2,$$s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \leq N$，求所有满足条件的十元组的$(s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1)$的和，对$10^{9} +7$取模。$(1 \leq N \leq 10^{9})$ * 题解：设$\Delta{s}=s_2-s_1$，其它变量同理，则有$\Delta{s},\Delta{n},\Delta{u},\Delta{k},\Delta{e} > 0, 2s_1 + \Delta{s} + 2n_1 + \Delta{n} + 2u_1 + \Delta{u} + 2k_1 + \Delta{k} + 2e_1 + \Delta{e} \leq N$，求所有满足条件的十元组$(s_1,\Delta{s},n_1,\Delta{n},u_1,\Delta{u},k_1,\Delta{k},e_1,\Delta{e})$的$\Delta{s}\Delta{n}\Delta{u}\Delta{k}\Delta{e}$的和。构造生成函数：$2s_1$对应$1+x^2+x^4+ \cdots = \dfrac{1}{1-x^2}$，有$5$个所以乘以五次方，得到$\dfrac{1}1-x_2_5_delta_s_因为最后要求的是不是方案数而是乘积和_因此对应_x_2x_2_3x_3_cdots_dfrac_x_1-x_2_有_5_个所以乘以五次方_得到_dfrac_x_5_1-x_10$；最后因为求的是$\leq N$，还要乘以一个$1+x+x^2+ \cdots = \dfrac{1}{1-x}$求前缀和。最后这三个乘起来得到$f(x)=\dfrac{(1+x)^{11}x^5}{(1-x^2)^{16}}$，因此我们只需要知道$\dfrac{(1+x)^{11}}{(1-x^2)^{16}}$展开后$x^{N-5}$的系数即可。观察发现分子分母单独拿出来都很好展开，而分子展开后只有有限的$12$项，因此我们只用枚举分子的每一项，计算出分母对应项系数的和，将两个系数乘起来最后加起来即可。

comment：巧妙的生成函数构造+求解对应系数方法。

分类：

题意：

题解：

comment：

2020.07.16 Codeforces Round #561(Div. 2)

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