mip001's Blog

我太弱了，现在才学莫队

以下均假设 $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)$ ，显然不可接受。

本文针对 OI 进行了专门优化，包括安装 Ubuntu 20.04 LTS（NOI Linux 2.0 便是基于此系统）、配置 G++ 环境等。

第一部分，什么是 WSL

Windows Subsystem for Linux（适用于 Linux 的 Windows 子系统，简称 WSL）

WSL 可以让你在 Windows 上优雅地运行 GNU/Linux，包括大多数命令行工具、实用工具和应用程序， 不会产生传统虚拟机或双系统的庞大开销，且与 Windows 系统深度结合。

题干传送门

先说结论：若用一个数组 $c$ 来存数 $i(i>1)$ 中 $0$ 的个数，则：

• 当 $i$ 为偶数， $c_i=c_{\frac{i}{2}}+1$ ；
• 当 $i$ 为奇数， $c_i=c_{\lfloor\frac{i}{2}\rfloor}$ 。