堆排序
输入一个长度为 $n$ 的整数数列，从小到大输出前 $m$ 小的数。 输入格式 第一行包含整数 $n$ 和 $m$。 第二行包含 $n$ 个整数，表示整数数列。 输出格式 共一行，包含 $m$ 个整数，表示整数数列中前 $m$ 小的数。 数据范围 $\rm{1} \le m \le n \le {10^5}$ $\rm...
2021-06 归档
共 12 篇文章
连通块中点的数量
给定一个包含 $n$ 个点（编号为 $\rm{1} \sim {\rm{n}}$ ）的无向图，初始时图中没有边。 现在要进行 $m$ 个操作，操作共有三种： “C a b”，在点 $a$ 和点 $b$ 之间连成一条边，$a$ 和 $b$ 可能相等； “Q1 a b”，询问点 $a$ 和点 $b$ 是否在同一连通块中，$...
合并集合（并查集）
一共有 $n$ 个数，编号是 $\rm{1} \sim n$，最开始每个数各自在一个集合中。 现在要进行 $m$ 个操作，操作共有两种： “M a b”，将编号为 $a$ 和 $b$ 的两个数所在的集合合并，如果两个数已经在一个集合中，则忽略这个操作； “Q a b”，询问编号为 $a$ 和 $b$ 的两个数是否在同一...
Trie字符串统计
维护一个字符串集合，支持两种操作： “I x”向集合中插入一个字符串 $x$； “Q x”询问一个字符串在集合中出现了多少次。 共有 $N$ 个操作，输入的字符串总长度不超过 $\rm{10^5}$，字符串仅包含小写英文字母。 输入格式 第一行包含整数 $N$，表示操作数。 接下来 $N$ 行，每行包含一个操作指令，指...
KMP字符串
给定一个模式串 $S$，以及一个模板串 $P$，所有字符串中只包含大小写英文字母以及阿拉伯数字。 模板串 $P$ 在模式串 $S$ 中多次作为字串出现。 求出模板串 $P$ 在模式串 $S$ 中所有出现的位置的起始下标。 输入格式 第一行输出整数 $N$,表示字符串 $P$ 的长度。 第二行输入字符串 $P$。 第三行...
滑动窗口（单调队列）
给定一个大小为 $n \le 10^6$ 的数组。 有一个大小为 $k$ 的滑动窗口，它从数组的最左边移动到最右边。 你只能在窗口中看到 $k$ 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子： 该数组为 $\left\{ {1,3, - 1, - 3,5,3,6,7} \right\}$，$k$ 为 $\r...
单调栈
给定一个长度为 $n$ 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 $-1$。 输入格式 第一行包含整数 $N$，表示数列长度。 第二行包含 $N$ 个整数，表示整数数列。 输出格式 共一行，包含 $N$ 个整数，其中第 $i$ 个数表示第 $i$ 个数的左边第一个比它小的数，如果不存在则输出 $-1...
数组模拟的双链表
实现一个双链表，双链表初始为空，支持 $\rm{5}$ 种操作： 在最左侧插入一个数； 在最右侧插入一个数； 将第 $k$ 个插入的数删除； 在第 $k$ 个插入的数左侧插入一个数； 在第 $k$ 个插入的数右侧插入一个数 现在要对该链进行 $M$ 次操作，进行完所有操作后，从左到右输出整个链表。 注意：题目中第 $k...
区间和并
给定 $n$ 个区间 $\left[ {{{\rm{l}}i},{ri}} \right]$，要求合并所有有交集的区间。 注意：如果在端点处相交，也算有交集。 输出合并完成后的区间个数。 例如：$\left[ {1,3} \right],\left[ {2,6} \right]$ 可以合并为一个区间 $\left[ {...
区间和（离散化方法）
假定有一个无限长的数轴，数轴上每个坐标上的数都是 $\rm{0}$。 现在，我们首先进行 $n$ 次操作，每次操作将某一位置 $x$ 上的数加上 $c$。 接下来，进行 $m$ 次询问，每个询问包含两个整数 $l$ 和 $r$ ，你需要求出在区间 $\left[ {l,r} \right]$ 所有数的和。 输入格式 第...
1 / 2