2020-2021:teams:farmer_john:week_11
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:week_11 [2020/07/17 23:20] jjleo [Bazoka13] |
2020-2021:teams:farmer_john:week_11 [2020/07/17 23:32] (当前版本) jjleo [题目] |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| ====2sozx==== | ====2sozx==== | ||
| - | ===牛客多校第一场D=== | + | ===牛客2020多校第一场D Quadratic Form=== |
| * 分类：数学，KKT。 | * 分类：数学，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$ | * 题意：给定一个 $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$ | * 题解：答案即为 $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 | + | * comment：KKT get。 |
| - | * 数学 [[.2sozx:牛客多校第一天D]] | + | |
| ====Bazoka13==== | ====Bazoka13==== | ||
| - | ===CF815D=== | + | ===CF815D Karen and Cards=== |
| - | * 分类： | + | * 分类：单调栈。 |
| * 题意：每张卡片有三个属性a,b,c，其上限分别为A,B,C，现在有n张卡片，定义一张卡片能打败另一张卡片当且仅当至少两项属性要严格大于另一张的对应属性。问在所有可能的卡片中，有多少种卡片能打败这全部n张卡。 | * 题意：每张卡片有三个属性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： | + | * comment：偏序联系到单调栈，然后扫描，经典。 |
| - | * 单调栈 [[.bazoka13:CF815D|CF815D]] | + | |
| ====JJLeo=== | ====JJLeo=== | ||
| ===Aising2020 F Two Snuke=== | ===Aising2020 F Two Snuke=== | ||
| - | * 分类： | + | * 分类：生成函数。 |
| - | * 题意： | + | * 题意：设十元组$(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})$ |
| - | * 题解： | + | |
| - | * comment： | + | |
| - | ===CF1372F=== | + | * 题解：设$\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： | + | ===CF1372F Omkar and Modes=== |
| + | * 分类：交互题，二分。 | ||
| + | * 题意：一个未知的长度为$n$的排好序的序列，一共有$k$个不同的数（$k$未知），你需要经过不超过$4k$次询问得到这个序列。每次询问一个区间，返回这个区间中出现次数最多的数及其出现的次数，如果有多个数满足条件，返回最小的那个。$(1 \le n \le 2 \cdot 10^5,1 \le k \le \min(25000,n))$ | ||
| + | |||
| + | * 题解：考虑先处理$[1,n]$里出现次数最多的数，设其所处区间为$[l,r]$，则再分别处理$[1,l-1],[r+1,n]$，以此类推，直到所有区间都处理完毕。我们只需保证对每一种数字做$4$次询问得到其出现的准确区间即可保证最多进行$4k$次询问。 | ||
| + | * 设现在来到了区间$[l,r]$，考虑如何处理：首先询问一次$[l,r]$，设返回值为$(x,y)$，设$z$为最大的满足$z \le y$的$2$的次方，考虑所有$z$的倍数$i$，由上述$z$的性质可得只有一个或两个处于$[l,r]$中且满足$a_i=x$。若只有一个$i$满足上述条件，那么询问$[i-z+1,i]$和$[i,i+z-1]$，其中必有一个最多的数也是$x$，因此我们可以得到数字$x$所处区间的左边界或右边界，我们已经知道$y$因此可以知道另一个边界值；若存在$i,j(i < j)$均满足上述条件，那么询问$[i-z+1,j]$即可获得数字$x$所处区间的左边界，我们已经知道$y$因此可以知道右边界值。 | ||
| + | * 在查找所有所有$z$的倍数$i$是否满足条件时，我们可以直接暴力地枚举$[l,r]$内所有$z$的倍数，如果对应下标被查找过则直接判断，否则查找一下即可。可以发现因为我们所查找的数字的出现次数是不增的，$a \cdot 2^b$同时也是$2^{b-1},2^{b-2}, \cdots$的倍数，因此所有查过的下标一定会被用到。所以，对于上述第一种情况，我们最多询问了$1+1+2=4$次，对于上述第二种情况，我们询问了$1+2+1=4$次，满足题意。 | ||
| + | |||
| + | * comment：通过二分的方法绝妙地用四次询问找到一个连续区间的左右端点。 | ||
| ===== 2sozx ===== | ===== 2sozx ===== | ||
| 行 36: | 行 40: | ||
| ====题目==== | ====题目==== | ||
| * [[.2sozx:牛客多校第一天D|牛客多校第一天D]] | * [[.2sozx:牛客多校第一天D|牛客多校第一天D]] | ||
| - | * comment:KKT get | ||
| ===== Bazoka13 ===== | ===== Bazoka13 ===== | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
2020-2021/teams/farmer_john/week_11.1594999203.txt.gz · 最后更改: 2020/07/17 23:20 由 jjleo
