mip001's Blog

我就是来水博客的

Day 1

T1 划

题意：给一个长度为 $n$ 的序列 $a$ 和一个 $d$，求最长的子区间 $[l,r]$，使得区间内的数排序之后相邻元素相差不超过 $d$，要求输出找到的区间长度。$n\leq 3\times 10^5,0\leq a_i\leq 10^9$

即找到最大的区间使得每个除了区间最大值以外的元素 $x$ 都有 $\leq x+d$ 的元素存在。

那么我们只需要跑出所有元素的左边和右边第一个 $\leq x+d$ 的元素，这个可以用 $set$ 维护；还需要知道所有元素的左边和右边最大的区间使得该元素为此区间的最大值，可以用单调栈维护

然后枚举 $r$ ，用线段树维护其最小的左端点即可，时间复杂度为 $O(n\log n)$。

基本概念

定义

记一个关于 $x$ 的式子：

$$f(x)=\sum\limits_{i=0}^na_i\times x^i$$

为一个 $n$ 次多项式。其中 $a_i$ 为常数，$n$ 为该多项式的度，也称次数，记作 $\deg f$。

显然，$f(x)$ 可以看作一个关于 $x$ 的 $n$ 次函数 $y=f(x)$。

这个 PPT 里面前半部分内容更完善

由于时间紧迫，本文不会太详细，并且由于 OI 不重视证明，本文很多时候可能只给出证明链接。

定理太多证明太难怎么办？证什么，背结论即可

2.1 记号

有确定界限的形式

我们要对一个有确定界限的式子求和：

$$a_1+a_2+\cdots+a_n$$

其中每个 $a_k$ 都是用某种方式定义的一个数。

我们可以用求和符号 $\sum$ 将其表示成这样：

$$\sum\limits_{k=1}^{n}a_k$$

我太弱了，现在才学莫队

以下均假设 $n,m$ 同阶。

普通莫队

简介

莫队算法主要用于解决离线区间查询等问题，若区间 $[l,r]$ 的答案能够 $O(1)$ 转移到与 $[l,r]$ 相邻的区间（即 $[l-1,r],[l+1,r],[l,r-1],[l,r+1]$），那么就可以使用莫队算法在 $O(n\sqrt{n})$ 内求出所有询问的答案。

题意

题面传送门

这是一道交互题。

目标：求出整数 $x\in 1\sim n$。

每次询问一个集合 $S$，交互库会返回是否 $x\in S$。交互库会骗你，但不会连续两次骗你。

其中，$n\leq 10^5$，至多询问 $53$ 次。交互库自适应

这个 PPT 里面的内容更完善

Part 1. 计数原理

加法原理和乘法原理是组合数学中最基础的计数原理。

注意：正如题目所言，本篇文章是学习笔记，只记录了某个知识点的框架和重点，具体内容请参照其它文章

第一部分：最小生成树

性质：

• 边权和最小
• 任意两点之间的最大边权最小

洛谷题面

以下认为 $n,m,k$ 同阶，时间复杂度都用 $n$ 表示。

Step 1

先思考一下普通二分的做法。

对于一个国家，设其在第 $w$ 波陨石雨后能收集到足够的陨石样本。我们设计一个函数 $solve(l,r)$ 表示答案 $w$ 在区间 $[l,r]$ 中，然后取出区间的中间值 $mid$ ，算出前 $mid$ 波陨石雨全部下下来所收集到的陨石数量，与希望收集的陨石数量比对，如果收集够了，说明答案 $w$ 在区间 $[l,mid]$ 中，否则，就在区间 $(mid,r]$ 中。

我们对于每个国家都进行一遍上述的流程，就可以解决这个问题。但是时间复杂度大概是 $O(n^2\log^2n)$ ，显然不可接受。