再也不想上机的时候手写堆了。

万能头：

#include <bits/stdc++.h>

vector 变长数组

动态数组，可以变长。

头文件：

#include <vector>

初始化

// 一维
vector<int> a; // <>里面写数据类型
vector<int> v(n); // 指定长度为n，初始值均为0
vector<int> v(n, 114514); // 指定长度为n、初始值都是n-1
vector<int> a{1,2,3,4,5}; // 初始化，数组长度为5
// 拷贝初始化
vector<int> a(n, 1);
vector<int> b(a); // b也是长度为n、初始值为1的数组
vector<int> c = a; // 另一种拷贝初始化方法

// 二维
vector<int> v[5]; // 第一维固定长度5，第二位可变长
vector<vector<int>> v; // 二维长度均可变，可以直接push_back进去一个数组
vector<vector<int>> a(n, vector<int>(n, 0)); // 行列均长度n且初始值为0

阅读全文

A Yuki 的连通块

题目描述

Yuki 有一个无向图，这个无向图有 $n$ 个点和 $m$ 条边，Yuki 希望知道这个无向图有多少个不同的连通块？

两个连通块不同，当且仅当两连通块的点集不同。

输入

第一行包含两个正整数 $n$ 和 $m$（$1 \le n, m \le 10^6$），分别表示无向图的点数和边数。
接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示编号为 $u$ 和 $v$ 的点之间有一条无向边。

输出

输出一行，表示该无向图的连通块数量。

输入样例

6 3
1 2
2 3
4 5

输出样例

3

阅读全文

做的跟shit一样，被虐爆了

F wiki数星星

题目背景

wiki正在一条直线上数星星，她想知道，哪里是离星星最近的地方呢？

题目描述

有一个函数 $ f(x) $，初始为常数函数 $ f(x) = 0 $。

接下来 $ Q $ 次操作：

• 更新 1 a b：给定整数 $ a, b $，令 $ g(x) = f(x) + |x - a| + b $，然后把 $ f(x) $ 替换为 $ g(x) $。

  例如：若当前 $ f(x) = 0 $，执行操作更新操作 1 2 1（即 $ a=2, b=1 $），则新的函数为 $ f(x) = |x-2| + 1 $；接着再执行操作 1 3 2（即 $ a=3, b=2 $），新的函数为
  $ f(x) = |x-2| + 1 + |x-3| + 2 $。

• 查询 2：输出使 $ f(x) $ 最小的整数 $ x $ 以及最小值 $ f(x) $。如果有多个使得最小的 $ x $，选择最小的那个整数。

例如：当 $ f(x) = |x - 2| + 1 $ 时，$ x = 2 $ 使得 $ f(x) $ 最小为 1。

已知询问时输出的值总是整数，请以整数格式输出。

阅读全文

软院大二上的算法课真是离谱，课上PPT几乎全是英文（怀疑完全是从算法导论原版书粘贴的），也听不懂。上机考试和上课讲的内容也没有关系，被纯纯虐杀，有的算法听都没听过...

第二章 算法基础

2.1 插入排序

基本算法：

​ 当选择循环下标j时，数组的A[1, j-1]已经排好序，剩余子数组为A[j+1, n]，将j下标的元素插入到前j-1个元素之中的合适位置：查找对应位置需要从j-1到1一个一个找到第一个小于等于A[j]的元素，找过的元素都往后移一位，A[j]放在停止的位置上。而循环下一次下标为j+1。

而当证明算法的正确性时，书中给出了需要证明的三条性质：

• 初始化： 循环的第一次迭代之前，它为真；
• 保持： 如果循环的某次迭代之前它为真，那么下次迭代之前它仍然为真；
• 终止： 在循环终止时，不变是为我们提供了一个有用的性质，该性质有助于证明算法是正确的。

阅读全文

A

题目描述

AndroidNeko 听说在计算复杂度的重要性刻进主题，想希望你以样写写一个程序来计算满足特定形式递归式的算法复杂度。

具体来说，给定正整数 $a, b, k$，所求递归式为：

$$ T(n) = aT\left(\frac{n}{b}\right) + O\left(n^k\right) $$

根据主定理，有：

$$ T(n) = \begin{cases} O\left(n^{\log_b a}\right), & \log_b a > k \\ O\left(n^k \log n\right), & \log_b a = k \\ O\left(n^k\right), & \log_b a < k \\ \end{cases} $$

输入格式

第一行一个正整数 $t$ $(1 \leq t \leq 2 \times 10^5)$，表示数据组数。

对于每组数据，一行三个正整数 $a, b, k$ $(1 \leq a, k \leq 10^9,\, 2 \leq b \leq 10^9)$，含义同题目描述。

输出格式

对于每组数据，输出一行：

• 若 $T(n)=O(n^{\log_b a})$，输出 n^{\log_ba}
• 若 $T(n)=O(n^k \log n)$，输出 n^klog n

• 若 $T(n)=O(n^k)$，输出 n^k

阅读全文