三角函数

单调性

对于三次函数 $f(x)=ax^3+bx^2+cx+d\ \ (a>0)$. 其导函数为 $f'(x)=3ax^2+2bx+c$ , 判别式为 $\Delta=4(b^2-3ac)$.

1. $\Delta=4(b^2-3ac)\leq0$, 则 $f'(x)\geq 0$, $f(x)$于 $\mathbb{R}$ 上单调递增.
2. $\Delta=4(b^2-3ac)>0$, 则 $f'(x)$ 存在两零点$x_1,x_2$, $f(x)$ 于 $(-\infty,x_1)$ 和 $(x_2,\infty)$ 上单调递增, $(x_1, x_2)$ 上单调递减.

极值

1. $\Delta=4(b^2-3ac)\leq0$, 则 $f'(x)$ 无变号零点, $f(x)$ 于 $\mathbb{R}$ 上无极值.
2. $\Delta=4(b^2-3ac)>0$, 则 $f'(x)$ 存在两零点$x_1,x_2$, $f(x)$ 于 $x=x_1$ 取极大值, 于$x=x_2$取极小值.

零点个数

1. $b^2-fac\leq 0$, 方程 $f(x)=0$ 恰有一个实根, 函数 $f(x)$ 恰有一个零点.
2. $b^2-fac> 0$, 且$f(x_1)\cdot f(x_2)>0$, 方程 $f(x)=0$ 恰有一个实根, 函数 $f(x)$ 恰有一个零点.
3. $b^2-fac> 0$, 且$f(x_1)\cdot f(x_2)=0$, 方程 $f(x)=0$ 有两个不等实根, 函数 $f(x)$ 有两个零点.
4. $b^2-fac> 0$, 且$f(x_1)\cdot f(x_2)<0$, 方程 $f(x)=0$ 有三个不等实根, 函数 $f(x)$ 有三个零点.

若方程$ax^3+bx^2+cx+d=0(a\neq 0)$的解为$x_1,x_2,x_3$,

则有$ax^3+bx^2+cx+d=a(x-x_1)(x-x_2)(x-x_3)$.

右边展开, 再比较系数可得:

$x_1+x_2+x_3=-\frac{b}{a}$

$x_1x_2+x_2x_3+x_3x_1=\frac{c}{a}$

$x_1x_2x_3=-\frac{d}{a}$

这个结论叫三次方程的韦达定理.

对称性

定理: 三次函数 $f(x)=ax^3+bx^2+cx+d(a\neq 0)$ 的图像关于点$(-\frac{b}{3a},f(-\frac{b}{3a})$对称.

[证明]:

注意到 $f(x)$ 可化为 $f(x)=ax^3+bx^2+cx+d=a(x+\frac{b}{3a})^3+(c-\frac{b^2}{3a})(x+\frac{b}{3a})+f(-\frac{b}{3a})$.

令 $g(x)=ax^3+(c-\frac{b^2}{3a})x$, 则 $f(x)=g(x+\frac{b}{3a})+f(-\frac{b}{3a})$,

易知 $g(x)$ 为奇函数, 其图像关于原点对称, 所以 $f(x)$ 的图像关于点 $(-\frac{b}{3a},f(-\frac{b}{3a}))$ 对称.

结论说明, 任意一个三次函数都有对称中心, 且对称中心的横坐标就是导函数图像的对称轴, 又是两个极值点的中点, 也是二阶导数的零点 (拐点就是对称中心).

三次函数的解析式

1. 一般形式: $f(x)=ax^3+bx^2+cx+d(a\neq 0)$.
2. 易知函数图像的对称中心为 $(m,n)$, 则 $f(x)=a(x-m)^3+b(x-m)+n(a\neq 0)$.
3. 易知函数图像与 $x$ 轴的三个交点的横坐标分别为 $x_1,x_2,x_3$ , 则 $f(x)=a(x-x_1)(x-x_2)(x-x_3)(a\neq 0)$.
4. 易知函数的图像与 $x$ 轴的一个交点的横坐标为 $x_0$, 则 $f(x)=(x-x_0)(ax^2+mx+n)(a\neq 0)$.

切割线性质

定理: 如图所示, 点 $P$ 是函数 $f(x)=ax^3+bx^2+cx+d(a\neq 0)$ 图像上任意一点(非对称中心), 过点 $P$ 作切线 $PT$ 和割线 $PAB$, 点 $A, B, T$ 均在 $f(x)$ 的图像上, 则 $x_A,x_T,x_b$ 成等差数列, 即 $x_t=\frac{x_a+x_b}{2}$.

[证明]:

设 $y=ax^3+bx^2+cx+d(a\neq 0)$ ,

直线 $PT$: $y-k_0x+m_0$,

直线 $PAB$: $y=kx+m$,

联立 $y, l_{PT}$, 由韦达定理得 $2x_T+x_P=-\frac{b}{a}$,

同理可得 $x_A+x_B+x_P=-\frac{b}{a}$,

所以有 $2x_T=x_A+x_B$,

故 $x_A,x_T,x_B$ 成等差数列.

倒装

全部倒装: 谓语动词全部置于主语之前.

部分倒装: 部分谓语动词置于主语之前.

全部倒装

1. here, there, now, then, next等词置于句首, 而谓语动词是be, 或动作性的不及物动词时(come, go, rush, run etc.)

   e.g. Here/There comes the head teacher.

   Next is/comes your turn.

2. in, out, up, down, away, back等表示方位的副词置于句首,而谓语动词是动作性的不及物动词时(come, go, fly, run)

   e.g. Up flew my kite.

   Out rushed the angry boy.

3. 表示地点的介词短语位于句首，而谓语动词是be或者sit, lie, stand, hang等不及物动词时

   **e.g.**At the foot of the mountain lies a beautiful lake.

   On the wall hung a portrait of the owner.

4. 在主系表结构中主语较长时，为使句子平衡，将表语(adj./doing/done/pp)提前到句首，而动词多为be。

   **e.g.**Present at the meeting are all the teachers and student representatives.

   Gone are the days when we were free from care.

   Joining us today is Linda, our foreign teacher.

   全部倒装通常只用与一般现在时和一般过去时。主语为代词时取消倒装。

   Here is the book you need./Here you are.

部分倒装

部分谓语动词置于主语之前。be/助动词/情态动词 + 主语 + 谓语动词其他部分

1. 否定意义的词或短语置于句首时，引起部分倒装。(never, no, not, little, few, hardly, rarely, seldom, scarcely, barely, no longer, nowhere, none, by no means, in no case, on no account etc.)

   e.g.Never have I seen such a breathtaking place.

注意⚠️：含有否定词的连词(不表否定意义)部分倒装。:

• Not only …(倒装)… but also

• No sooner …(had sb. done)… than …/

• Hardly/Scarcely …(had sb. done)… when …

• Not until … sb./sth …(倒装)…

  Not only has the activity enriched campus life, but it has sparked students’ passion for learning.

  Many people won’t realize the importance of health until they lose it.

  Not until they lose it will many people realize the importance of health.

2. 当**only+状语(词/短语/句子)**置于句首时，句子要部分倒装。

e.g. Only in Yangzhou can you eat anthentic Yangzhou fried rice.

Only when you see it with your own eyes will you realize

3. So/Neither/Nor + be/助动词/情态动词+主语。意为 “…也一样/也一样不…”

4. 在**so…that…/such…that…**句型中，so+adj./adv. 或 such+n. 位于句首时，主句要部分倒装。

   **e.g.**So seriously has the river been polluted that there is no fish in it.

5. if 虚拟条件句中，若将从句中的were/should/had提前至句首，不仅省略if，也构成了部分倒装。

   If I had taken your advice, I would have avoided the mistake.

   Had I taken your advice, I would have avoided…

   If I were you, I would look on the bright side of it.

   Were I you, I would .look on the bright side of it.

   If it should break in two years, you would get a new one.

   Should it break in two years, you would get a new one.

Atcoder Beginner Contest #263 D - Left Right Operation

题目大意

给定一串长度为$n$的数列, 可以进行如下操作, 每种最多一次:

• 将$A_1 A_2 \cdots A_i$赋值为$L$
• 将$A_j A_{j+1} \cdots A_n$赋值为$R$

求出操作后数列$A$的最小值

数据规模

$1 \leq N \leq 2 \cdot 10^5$

$-10^9 \leq L,R \leq 10^9$

$-10^9 \leq A_i \leq 10^9$

$N,L,R,A \in \mathbb{Z}$

我的思路(错)

对于数列$A$,处理出前缀和le和后缀和ri

从前往后遍历, 求出从头替换的数列最小值及其替换位置pos1

从后往前遍历, 求出从尾替换的数列最小值及其替换位置pos2

然后比较pos1和pos2的大小, 分情况讨论

大佬代码

heno239

对于数列$A$变换后的数列$A'$的每一位$A'_i$, 只有三种可能:

1. 被填充为$R$
2. 保持不变
3. 被填充为$R$

且三种情况必须顺次出现.

所以对于每一位数字, 对应每种情况存在三个状态, 且每个状态只能转移到大于等于该状态编号的状态:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

rep(i, n)
{
	vector<ll> ndp(3, INF);
	for (int x = 0; x < 3; x++)
		for (int y = x; y < 3; y++)
		{
			ll cost;
			if (y == 0)
				cost = l;
			else if (y == 1)
				cost = a[i];
			else
				cost = r;
			chmin(ndp[y], dp[x] + cost);
		}
	swap(dp, ndp);
}

时间复杂度$\Theta(N)$

hank55663

代码非常简短.

预处理ans = r * n

对于每一位数字, 计算其前缀和的最小值pre = min(pre + a[i], (i + 1) * l);,同时计算出答案ans = min(ans, (n - i - 1) * r + pre);

时间复杂度$\Theta(N)$

hitonanode

预处理数组left和right:

• left[i] 表示若将数列$A$从头至第i位替换为$L$, 与原数组的差
• right[i]表示若将数列$A$从第i为至末尾替换为$R$, 与原数组的差

对于每一位i，寻找数列和加上left[i]以及从此位至末尾最小的right[j]的值，记录并更新答案

时间复杂度$\Theta(N)$

时分共享（time sharing）：[[操作系统导论 第2章 操作系统介绍#2.1 虚拟化CPU|将单个CPU（或其中一小部分）转化为看似无限数量的CPU，从而让许多程序看似同时运行。]]

4.1 抽象：进程概念

操作系统为正在运行的程序提供的抽象，就是作为的进程（progress）。
进程的机器状态（machine state）：

• 它能访问的内存（称为[[操作系统导论 第2章 操作系统介绍#^6644e1|地址空间]]，address space）；
• 寄存器，包括一些非常特殊的寄存器，如
  • 程序计数器（Program Counter, PC)（或指令指针，Instruction Pointer， IP），告诉程序执行哪个指令；
  • 栈指针（stack pointer），相关的帧指针（frame pointer），用于管理函数参数栈、局部变量和返回地址；

4.2 进程API

• 创建（create）：创建新进程，运行指定程序；
• 销毁（destroy）：强制销毁进程，防止程序不退出；
• 等待（wait）：等待进程停止运行；
• 其他控制（miscellaneous control）：如暂停进程，然后恢复；
• [[操作系统导论 第4章 抽象：进程#4.4 进程状态|状态]]（status）：获得进程的状态信息；

4.3 进程创建：更多细节

• 操作系统运行程序的第一件事：将代码和所有静态数据（如初始化变量）加载（load）到内存中，加载到进程的[[操作系统导论 第2章 操作系统介绍#^6644e1|地址空间]]中。
  早期（或简单的）操作系统中，加载过程尽早（eagerly）完成，即在运行程序之前全部完成。现代操作系统惰性（lazily）执行该过程，即仅在程序执行期间需要加载的代码或数据片段，才会被加载。
• 操作系统为程序的运行时栈（runtime stack，stack）分配内存；
• 操作系统为程序的堆（heap）分配内存；
• 操作系统执行一些其他的初始化任务，特别时与输入/输出（I/O）相关的任务。
• 最后一项任务：起动程序，在入口处运行，即main()。通过跳转到main()例程（[[操作系统导论 第5章 插叙：进程API]]），OS将CPU的控制权转移到新创建的进程中，从而程序开始执行。

4.4 进程状态

进程可以处在一下三钟状态之一：

• 运行（running）：进程正在处理器上运行，正在执行指令。
• 就绪（ready）：程序已准备好运行，但由于某种原因，操作系统选择不在此时运行。
• 阻塞（blocked）：一个进程执行了某种操作，直到发生其他事件时才会准备运行。
  ![[图4.2 进程：状态转换.png]]

4.5 数据结构

对于停止的进程，寄存器上下文将保存其寄存器的内容。当一个进程停止时，它的寄存器将被保存到这个内存位置。通过恢复这些寄存器（将它们的值放回实际的物理寄存器中），操作系统可以恢复运行该进程。[[操作系统导论 第6章 机制：受限直接执行#保存和恢复上下文|上下文切换（context switch）]]。
有时系统会有一个初始（initial）状态，表示进程在创建是处于的状态。另外，一个进程可以处于已退出但尚未清理的最终（final）状态（UNIX中称为僵尸状态），它允许其他进程（通常是其父进程）检查进程的返回代码，并查看刚刚完成的进程是否执行。完成后，父进程将执行最后一次调用（例如，[[操作系统导论 第5章 插叙：进程API#5.2 wait()系统调用|wait()]]），已等待子进程的完成，并告诉操作系统它可以清理这个正在结束的进程所有相关的数据结构。

第二章 操作系统介绍

程序运行时会发生什么？

1. 从内存中获取（fetch）一条指令；
2. 对其进行解码（decode）；
3. 执行（execute）；
4. 重复上述过程。

操作系统（Operating System, OS）：让程序运行变得容易，允许程序共享内存，让程序与设备交互。又称为虚拟机（virtual machine）。

虚拟化（virtualization）：操作系统将物理（physical）资源（处理器，内存，硬盘等）转化为更通用、更强大且更易于使用的虚拟形式。

操作系统提供了一些接口（[[操作系统导论 第4章 抽象：进程#4.2 进程API|API]]），以及几百个系统调用（system call）让应用程序调用。即提供了一个标准库（standard library）。

2.1 虚拟化CPU

在硬件的一些帮助下，操作系统负责提供一种假象（illusion），即操作系统拥有非常多的虚拟CPU的假象。

虚拟化CPU：将单个CPU（或其中一小部分）转化为看似无限数量的CPU，从而让许多程序看似同时运行。

两个序想要在特定时间运行，应该运行哪个？这个问题由操作系统的策略（policy）来回答。在操作系统的许多不同的地方采用了一些策略，来回答这类问题，所以我们将在学习操作系统实现的基本机制（mechanism）（例如一次运行多个程序的能力）时研究这些策略。因此，操作系统承担了资源管理器 （resource manager）的角色。
[[操作系统导论 第4章 抽象：进程]]

2.2 虚拟化内存

内存就是一个字节数组。要读取（read）内存，必须制定一个地址（address），才能访问数据。要写入（write）或更新（update）内存，还必须要写入给定地址的数据。每个进程访问自己私有的虚拟地址空间（virtual address space）（有时称为地址空间address space），操作系统一某种方式映射到机器的物理内存上。

2.3 并发

2.4 持久性

2.5 设计目标

• 建立一些抽象（abstraction），让系统方便和易于使用；
• 提供高性能（performance），最小化操作系统的开销（minimize the overhead）；
• 在应用程序之间以及在OS和应用程序之间提供保护（protection），让进程彼此隔离（isolation）是保护的关键；
• 操作系统必须不间断运行，提供高度的可靠性（reliability）
• 能源效率，安全性，移动性……

2.6 简单历史

早期操作系统：只是一些库

批（batch）处理：线把一些工作准备好，然后由操作员以“分批”的方式运行。一次运行一个程序。

超越库：保护

系统调用（system call）：添加一些特殊的硬件指令和硬件状态，让向操作系统过度变为更正式的、受控的过程。

系统调用和过程调用之间的关键区别在于，系统调用将控制转移（跳转）到OS中，同时提高硬件特权级别（hardware privilege level）。用户应用程序以所谓的[[操作系统导论 第6章 机制：受限直接执行#^82a54b|用户模式（user mode）]]运行，这意味着硬件限制了应用程序的功能。在发起系统调用时［通常通过一个称为陷阱（trap）的特殊硬件指令］，硬件将控制转移到预先指定的陷阱处理程序（trap handler），并同时将特权级别提升到[[操作系统导论 第6章 机制：受限直接执行#^2ba595|内核模式（kernel mode）]]以完全访问系统的硬件，因此可以执行诸如发起I/O请求或为程序提供更多内存等功能。当操作系统完成请求的服务时，它通过特的陷阱返回（return-from-trap）指令将控制权交还给用户，该指令返回到用户模式，同时将控制权交还给应用程序，回到应用离开的地方。

多道程序时代

操作系统将大量作业加载到内存中并在它们之间快速切换，从而提高CPU利用率。
在I/O进行和任务中断时，要支持多道程序和重叠运行。内存保护、并发等问题变得关键。

摩登时代

个人计算机。

2.7 小结

不闻不若闻之，闻之不若见之，见之不若知之，知之不若行之。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment

方程与代数式

1. 多项式恒等: $x$取任意值时$Q(x)$与$R(x)$都相等, 则称$Q(x)$与$R(x)$恒等. 记作$Q(x)\equiv R(x)$.

   多项式恒等定理: 一直两个次数均不超过$n$的多项式$Q(x)$与$R(x)$, 若$x$取$n+1$个不同值时有$Q(x)=R(x)$, 则有$Q(x)\equiv R(x)$.

2. 余数定理: $f(x)\equiv f(a)\quad(mod\ x-a)$

   因式定理: $f(a)=0\Lrarr x-a|f(x)$

3. 整系数多项式的有理根定理
   设$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$为整系数多项式,

   而$\frac{r}{s}$为其有理根, 其中 $ r,s$ 互素, 那么必有:

   $s|a_n,\ r|a_0$

   *若$a_n=1$, 则所有有理根都是整数.

4. 韦达定理:

   若一元 n 次多项式$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$的根为$x_1,x_2,\cdots,x_n$, 则有:
   $x_1+x_2+\cdots+x_n = -\frac{a_{n-1}}{a_n}$
   $x_1x_2+x_2x_3+\cdots+x_{n-1}x_n=\frac{a_{n-1}}{a_n}$
   $x_1x_2x_3+x_2x_3x_4+\cdots+x_{n-2}x_{n-1}x_n=-\frac{a_{n-3}}{a_n}$
   $\cdots\cdots$
   $x_1x_2\cdots x_n=(-1)^n\frac{a_0}{a_n}$

Codeforces Round #806F. Yet Another Problem About Pairs Satisfying an Inequality

题目大意

给定数列$a_1, a_2, \dots a_n$, 求出满足$a_i < i < a_j < j$的$i, j$个数.

数据规模

$1 \leq k \leq 1000$

$2 \leq n \leq 2 \cdot 10^5$

$0 \leq a_i \leq 10^9$

其中, $\Sigma n \leq 2 \cdot 10^5$

思路

根据定义，可以排除所有的$a_i\geq i$, 然后通过二分查找，统计$j$的个数.

时间复杂度:$\mathcal{O}(n \log n)$.

反思与感悟

根据题意，进行剪枝优化

[比赛代码]

时间不够, 没想出来.

SSRS_

树状数组

Atcoder Regular Contest #142 B - Unbalanced Squares

题目大意

有一个$n * n$的矩阵，其中有$n^2$个数。确保对于每一个位置$(i,j，在其相邻的八个方格中，存在大于和小于它的数。

数据范围

$2 \leq n \leq 500$

我的思路

不会。

反思与感悟

tourist

用 vector 嵌套以及初始化简化代码

因为数字已经确定，所以可以根据奇偶性判断。