浅念づ昔夜's Blog

传送门

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)$。空间换时间。

传送门

Solution

并查集。在一个 $k$ 下能通过若干次交换相互得到的物品构成一个集合。

对 $q$ 个询问升序排序，离线处理。

对大小为 $n+m$ 的数组 $a_n$ 进行排序，枚举 $a_i$，二分查找在哪个询问时合并 $a_i$ 和 $a_{i+1}$ 所在集合。

一个集合包含的元素必然在有序数组 $a_n$ 中构成连续区间。

传送门

Solution

2-SAT 板子题。

设点 $u_{i}$ 为 $i=-1$，$u_{i+n}$ 为 $i=1$。

对于每一列，最少要有两个 $1$。这意味着，若一列中的一个数为 $-1$，则其余两个数必定为 $1$，这就得到了两条有向边。我们分别假设一列中的三个数为 $-1$，就得到了 $6$ 条有向边。因为有 $n$ 列，所以一共有 $6n$ 条有向边。然后跑 Tarjan，判断是否有 $u_{i}$、$u_{i+n}$ 在同一强连通分量内即可。