¶ 底层原理

CPU 定期接受定时器中断，调用由操作系统指定的中断处理函数，操作系统根据策略调度运行进程。

¶ 区别

¶ 抢占式调度

抢占式调度是一种调度方法，在该方法中，每个任务都分配有优先级。 一种简单的调度策略是完全按照优先级调度，高优先级任务会抢占低优先级任务的 CPU 时间。 即使较低优先级的任务仍在运行，若有等待中的任务比正在运行的任务优先级高，操作系统会中断低优先级任务，让高优先级任务运行。

¶ 什么是非抢占式调度

在这种调度方法中，操作系统不会主动打断进程运行。只有在当前进程终止或者主动让出 CPU 时间，操作系统才会进行任务调度。 这是可用于各种硬件平台的唯一方法。这是因为它不需要抢先式调度之类的专用硬件（例如计时器）。

¶ 总结

抢占式调度有一个由定时器中断周期性调用的调度器。它强制当前进程暂停并切换到最高优先级的进程执行。 非抢占式调度并不强迫进程切换。进程必须自愿放弃对内核的控制，以允许其他进程执行。

¶ 例子

在非抢占式SJF调度中，一旦将CPU周期分配给进程，进程便将其保持到达到等待状态或终止为止。

考虑以下五个过程，每个过程都有自己独特的突发时间和到达时间。

步骤0）在时间=0时，P4到达并开始执行。

步骤1）在时间=1，过程P3到达。但是，P4仍需要2个执行单元才能完成。它将继续执行。

步骤2）在时间=2，过程P1到达并添加到等待队列中。P4将继续执行。

步骤3）在时间=3，过程P4将完成其执行。比较P3和P1的突发时间。执行过程P1是因为其突发时间比P3少。

步骤4）在时间=4，过程P5到达并添加到等待队列中。P1将继续执行。

步骤5）在时间=5，过程P2到达并添加到等待队列中。P1将继续执行。

步骤6）在时间=9，进程P1将完成其执行。比较P3，P5和P2的突发时间。执行过程P2是因为其突发时间最短。

步骤7）在时间=10，P2正在执行，P3和P5在等待队列中。

步骤8）在时间=11，过程P2将完成其执行。比较P3和P5的突发时间。执行处理P5是因为其突发时间较短。

步骤9）在时间=15，过程P5将完成其执行。

步骤10）在时间=23，过程P3将完成其执行。

¶ 优缺点

¶ 抢占式调度

优势

• 抢占式调度方法更加健壮，可以使一个进程无法独占 CPU
• 每次中断后都重新考虑运行任务的选择
• 每个事件都会导致正在运行的任务中断
• 操作系统确保所有正在运行的进程的 CPU 使用率相同。
• 在这种情况下，CPU 的使用是相同的，即所有正在运行的进程将平均使用 CPU
• 改善了平均响应时间
• 将其用于并行环境时，抢占式调度将非常有用

缺陷

• 有调度开销
• 调度程序需要更长的时间来挂起正在运行的任务，切换上下文并调度新的传入任务
• 如果某些高优先级进程连续到达，则低优先级进程需要等待更长的时间

¶ 非抢占式调度的优势

优势

• 提供低调度成本
• 倾向于提供高吞吐量
• 概念非常简单
• 调度所需的计算资源更少

缺陷

• 错误可能导致机器冻结
• 实时和优先级调度困难

感谢我的老师。

基本思想是把 $y=kx+b$ 变换成 $\frac{y-kx}{b}=1$ 来代换。

¶ 简单情况

先考虑最简单的情况，平衡位置为 $x=0$，振幅为 $A$，质点质量为 $m$，弹簧劲度系数为 $k$，从平衡位置起振。

由运动学规律得

这个家伙很菜，什么也没有留下

ZJ 老年高二卑微弱校 D 类选手

ZJOI 2020 各种暴毙

虽然说我从来没有期望过进省队，但是 rk89 也是远低于预期

当时连退役记都没心情写，教练问我 WC 和 APIO 要不要去，我全拒了，报了暑假各种文化课培训班

万万没想到被续了 D 类

偷一张图

定义 $f_u$ 为：$\mathrm{tag}_u = 1$ 的概率。

定义 $g_u$ 为：$u$ 的祖先存在 $\mathrm{tag} = 1$ 的概率。

1. 白色： $g=g/2,f=f/2$
2. 橙色： $f=(g+f)/2$
3. 深灰： $g=(1+g)/2,f=(1+f)/2$
4. 浅灰： $g=(1+g)/2$
5. 黄色：（啥都不用干

¶ 翻译

¶ A. Contest for Robots

给出长度为 $1\le n\le 100$ 的两个序列 $r,b$，且满足 $r_i, b_i\in\{0, 1\}$，你需要确定 $p_i$（$p_i\ge 1$）。

满足 $\sum_{i=1}^n r_ip_i > \sum_{i=1}^n b_ip_i$，并且最小化 $\max_{i=1}^n{p_i}$ 。

如果不可能，输出 $-1$ 。

¶ B. Journey Planning

给出长度为 $1\le n\le 2\cdot 10^5$ 的序列 $b$，$1\le b_i\le 4\cdot 10^5$

称合法序列为，$c_1,\cdots,c_k$，满足 $c_i<c_{i+1}$ 和 $c_{i+1}-c_i = b_{c_{i+1}}-b_{c_i}$（$k=1$ 时也是合法的），定义其美丽值为 $\sum_{i=1}^k b_{c_i}$ 。

求最大美丽值。

¶ 2017

¶ 「雅礼集训 2017 Day1」市场

支持区间减，区间整除，区间最小查询，区间和查询。

线段树，考虑一个区间的最大值 $a$ 和最小值 $b$

若 $k=a-\lfloor a/d \rfloor = b-\lfloor b/d \rfloor$， 则对于 $a<c<b$ 有 $c-\lfloor c/d\rfloor=k$

事实上满足上述的只有 $a=b$ 或 $a=b+1$

证明可令 $a=\alpha k+p_1,b=\beta k+p_2$ 具体略

域名备案批下来了，服务器是阿里云的 9.5r/mon

用这个搭了一些小服务，全程使用 docker。所有 password/key/secret 用 QAQ 替代

用 nginx 进行反向代理

是道好题

可惜卡常数

感觉题目出得不是很难，部分分给得很足