不等式

前言 这种优化我以前“听”过了很多次，但是好像都没学会qwq。 四边形不等式： 对于二元组 \(w_{x,y}\)，如果在定义域上任取四个点 \(a \le b \le c \le d\)，满足： \[w_{a,b}+w_{c,d} \ge w_{a,c}+w_{b,d} \]则称 \(w_{x,y ......

基本不等式 基本不等式定义 这是我们一般说的基本不等式：对非负实数 \(a,b\)，有 \[a+b\geqslant 2\sqrt{ab} \]等号成立当且仅当 \(a=b\)。 事实上，这个不等式来自于 \[(x-y)^2\geqslant 0 \]即 \[x^2+y^2 \geqslant 2x ......

\(\newcommand{\bbE}{\operatorname{\mathbb {E}}}\) 回想去年概统期末, 前四道题都非常正常, 最后一道题冷不丁来了这么一个问题: 令 \(X_i\) 为独立, 对称, 同分布的 \(L_p\) 随机变量, 求证 \[\bbE \left|\sum_{i ......

因为输入法没有给我满意的候选项所以这次就不取抽象标题了。 可恶每道题还要证明一下满足四边形不等式，真是难为我了。 A - Chef and Bitwise OR Operation https://vjudge.net/contest/602275#problem/A CodeChef - CHEF ......

\(x\)为整数时： 如果\(x>\frac{a}{b}\)，那么\(x\ge\lfloor\frac{a}{b}\rfloor+1\) 如果\(x<\frac{a}{b}\)，那么\(x\le\lceil\frac{a}{b}\rceil-1\) 如果\(x\ge\frac{a}{b}\)，那么\ ......

四边形不等式 对于任意的 \(l_1\le l_2\le r_1\le r_2\)，满足 \(w(l_1,r_1)+w(l_2,r_2)\le w(l_1,r_2)+w(l_2,r_1)\) 。 若等号恒成立，则称函数 \(w\) 为四边形恒等式。 如何证明 若满足 \(w(l,r-1)+w(l+1 ......

 ![](https://img2023.cnblogs.com/blog/2702872/202312/2702... ......

四边形不等式不仅在一维的线性dp中可以使用，在二维dp中也是很不错的东西 这个二维dp不局限于区间dp，虽然四边形不等式优化石子合并是很经典的东西 但是这种四边形不等式我不打算推导，而是直接背结论，因为我觉得知道推导过程对我的作用不是很大而且麻烦 在区间dp问题中，这样的方程\(f[i][j]=\d ......

Jensen 不等式定义 若 \(f(x)\) 为区间 \(I\) 上的下凸函数，则对于任意 \(x_{i} \in I\) 和满足 \(\displaystyle\sum_{i=1}^{n} \lambda_{i} = 1\) 的 \(\lambda_{i} \gt 0 \left( i = 1, ......

对于线性的dp \(f[i]=min(f[j]+val(i,j))\) 或者说是大致的转移方程可以写成这样的dp，时间复杂度大概是\(O(n^2)\) 能否优化主要取决于\(val(i,j)\)的内容和\(j\)的范围 假如\(j\)的范围是一个单调向后移动的窗口，只要\(val(i,j)\)能够用 ......

说明 设 \(w(x,y)\) 是定义在整数集合上的二元函数。 下文所有数都在默认的定义域上。 下文的四边形不等式定义是对于决策单调性函数中决策函数为 \(\min\) 而言的。如果要求考虑决策函数为 \(\max\) ，则需要将下文中的关于 \(w\) 的不等式符号全部取反，即所有值（不是下标、大 ......

已知函数\(f(x)=(x+2)\ln x,g(x)=x^2+(3-a)x+2(1-a)\) (1)若不等式\(f(x)\leq g(x)\)在\(x\in(-2,+\infty)\)上恒成立，求\(a\)取值范围. (2)证明:\(\displaystyle \sum\limits_{k=1}^{ ......

题目： 给你三个整数 a ，b 和 n ，请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2n。 由于答案可能会很大，返回它对 109 + 7 取余 后的结果。 注意，XOR 是按位异或操作。 题解： XOR的定义：对于两个二进制位，如果相同则结 ......

P5482 [JLOI2011] 不等式组 这道题比板子还是难不少，因为有大量的分类讨论。 看到题就可以考虑平衡树了。 \(ax+b>c\iff ax>c-b\)，根据不等式乘除法的变号规则分类。 \(a>0\)，不等号方向不变，\(x>\dfrac{c-b}{a}\)。 \(a<0\)，不等号方向 ......

今天在群里又看到了经典的数论不等式：\(\min x, s.t. L \le ax \bmod b \le R\)。以及杜岩旭问这个是不是等价于 \(\min at \bmod b, t \in [L, R]\)。实际上当然是等价的。首先我们可以胡乱处理一下令 \(a \perp b\)，无论在哪个 ......

背景： Lagrange 对偶：对于优化问题 \[\begin{aligned} &\mathrm{minimize} ~~ &f_0(x) \\ &\mathrm{subject ~ to} ~~ &f_i(x)\le 0, ~~ h_j(x)=0 \end{aligned} \] 可以建立其 L ......

Itst - 决策单调性与四边形不等式 学习笔记。 这方面是真的一点不会啊。学点东西吧 apj。 约定 对于 \(n \times m\) 的矩阵 \(A\)，定义： 子矩阵 \(A_{[i_1, i_2, \cdots, i_k],[j_1, j_2, \cdots, j_l]}\) 为矩阵 \( ......

第一道：证明\(\sum_{i=2}^n (\frac{1}{2n})^n<\frac{1}{\sqrt{e}(e-1)}\) \((\frac{1}{2n})^n=e^{n\ln \frac{1}{2n}}<e^{n(\frac{1}{2n})-1}=e^{\frac{1}{2}-n}\) \(\ ......

前言 使用方法：如果想得到更好的显示效果，可以点击全屏按钮，已经实现电脑端、手机端的适配，效果很好；电视端没有实现适配，Ipad端的适配没有测试； 思维导图 [全屏/Esc] ......

什么是糖水不等式？ \[\frac{a}{b}\lt \frac{a+m}{b+m} \ \ \ (m>0) \]凭直觉这个不等式当然是成立的，但数学这么严谨的东西你直觉算个姬直觉是不可靠的，那我们证明一下： 我们用改变后的浓度减去初始浓度： \[\frac{a+m}{b+m}-\frac{a}{b ......

前言： 没有前言（快累死了，不想写）。 solution： 题目传送门 设$ f_i $ 为第 $ i $ 句时最小的不协调度。 \[f_i = f_j + \left |s_i-s_j+i-j-1-L\right |^P \]\[f_i=f_j+\left |s_i+i-(s_j+j)-(L+1) ......

前置知识： 一般分配律： \(\displaystyle\sum_{\substack{j\in J\\k\in K}}a_jb_k\) \(=\displaystyle\sum_{\substack{j\in J}}\displaystyle\sum_{\substack{k\in K}}a_jb ......

前言 使用方法：如果想得到更好的显示效果，可以点击全屏按钮，已经实现电脑端、手机端的适配，效果很好；电视端没有实现适配，Ipad端的适配没有测试； 思维导图 [全屏/Esc] ......

洛谷传送门 首先特判 \(a_i = 0\)，然后： \(\begin{aligned} f_k(x) & = \sum\limits_{i = 1}^k |a_i x + b_i| \\ & = \sum\limits_{i = 1}^k a_i |x + \frac{b_i}{a_i}| \en ......

数分笔记——Fejér-Jackson不等式 Fiddie 【注：待更一些更强的结论】 参考书：梅加强《数学分析》. 下面文章也可以参考： 题目：若数列 \{na_n\} 单调收敛于0, 则函数项级数 \sum\limits_{n=1}^{\infty}a_n\sin nx 在 \mathbb{R} ......

零、前置知识 子矩阵： 设 \(A\) 为 \(n\times m\) 的矩阵，则子矩阵 \(A_{[i_1,\cdots,i_k],[j_1,\cdots,j_l]}\) 为矩阵 \(A\) 的第 \(i_1,\cdots,i_k\) 行与第 \(j_1,\cdots,j_l\) 列的交形成的矩阵 ......

# 理论知识 # 整体二分优化递推 注意用词，这里的式子大概是 $f_{i}=g_{j}+w(i,j)$ 的形式，那么如果能满足 $g$ 是预先知道的值且使得 $f_{i_1}$ 和 $f_{i_2}$（$i_1<i_2$）取到最优值的点 $j_1j_2$ 满足 $j_1\le j_2$，那么我们称 ......

#凹凸反转：证明指对跨阶不等式的利器 ##概述 在证明指对跨阶的不等式时，常可以将指数部分与对数部分分离在不等号两边，并在不等号两边构造凹凸性相反的函数，使得上凹函数的最小值大于上凸函数的最大值来证明原不等式 ##例题 $$ \text{please prove}\quad\forall x>0,\ ......

证明内容：$\frac{\sum_{i=1}^{n}a_i}{n}>=\sqrt[n]{\prod_{i=1}^{n}a_i}$ 首先介绍一下证明方法：向前向后的数学归纳法 第一步找到一个 **单调递增的发散** 序列{$a_n$}（本文为$2^{1},2^{2}......$） 第二步证明若$n= ......

> ⭐️ **本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 \[彭旭锐] 和 [BaguTree Pro](https://www.mdnice.com/writing/85b28c4e60354865a423728e668fc570) 知识星球提问。** > > 学习数据 ......