浅念づ昔夜's Blog

传送门

Solution

设 $F_{i,len, d}$ 表示以 $a_i$ 结尾，长度为 $len$，公差为 $d$ 的等差数列数量。转移方程为

$$F_{i,len,d}=\sum\limits_{j=1}^{i-1} F_{j,len-1,d}$$

传送门

Solution

从 $1$ 到 $n$ 枚举数字，对于当前数字，若与栈顶元素相同，则弹出栈顶元素，否则压入当前数字。随后将当前栈的状态通过哈希映射到 map 数组中。map 数组负责统计该状态出现的次数。

传送门

Solution

设有雪顶和无雪顶的山的总高度差为 $c$。

通过计算代表山峰类型的 $01$ 矩阵的二维前缀和，可以求出每个大小为 $k\times k$ 的方形区域中，两种类型的山的数量差。设每个方形的数量差分别为 $a_i$，则问题转换为方程

传送门

Solution

注意到每把武器只使用一种金属锻造，可以独立计算每种金属锭的贡献。

把问题转换为：有一个数 $x$ 和 $n$ 个操作，每个操作包含两个参数 $a_i$、$b_i$。当满足 $x\le a_i$，则可执行操作 $i$，使 $x$ 变为 $x-(a_i-b_i)$。求可对 $x$ 操作次数的最大值。

传送门

Description

有大小为 $n$ 的数组 $a_i$，正整数 $l$、$r$。数组中相邻的多个数可绑定为一组。一个数只能在一个组内。求最多能有多少组满足组内元素之和在 $[l,r]$ 内。

传送门

Description

一张连通无向图，你可以剪断任意一条边。求剪断后存在路径的点对数的最小值。

传送门

Description

给定一个长度为 $n$ 的数组 ${a_i}$和正整数 $k$，数组可任意排序且不占用操作次数。一次操作可将 $a_i=a_i+k$。求最少多少次操作能将该数组变为回文数列，即保证 $a_i=a_{n - i + 1}$。

简介

对比朴素枚举，KMP 的思想是当匹配出现不一样的字符时，根据模式串当前子串的最大相同前后缀，将模式串的指针回退到最大相同前缀的末尾而非模式串的开头，从而优化时间复杂度。

记录子串最大相同前后缀长度的数组为 $next_i$。下图展示了 $next_i$ 的求解过程。

传送门

逐个对集合 $P$ 中的字符串进行 KMP ，得出其在串 $S$ 中的所有覆盖区间。问题转换成如何选取相互无重合部分的区间，以 $S$ 串的左端点为起点，能覆盖最大的连续区域。

对区间以左端点为关键字，从小到大进行排序。定义数组 $b_i$ 记录点 $i$ 的左侧是否已被全部无重合地覆盖。枚举区间，若区间左端点的左边已全部覆盖，即 $b_l = 1$，则该区间可选取，使 $b_{r+1} = 1$。同时更新答案 $ans = r$。

简介

set 和 multiset 作为 C++ STL 的一部分，由红黑树实现，能保持容器内元素始终有序。其插入、查找、删除的时间复杂度均为 $\Theta(\log n)$。两者区别在于 set 不允许有重复元素，multiset 允许有重复元素。

这里顺便提起 unordered_set 和 unordered_multiset，底层实现是哈希表，容器内元素无序。插入、查找、删除的时间复杂度最好为 $\Theta(1)$，最坏为 $\Theta(n)$。空间换时间。