题意

给定一个已排序的正整数数组 $nums$，和一个正整数 $n$ 。从 $[1, n]$ 区间内选取任意个数字补充到 $nums$ 中，使得 $[1, n]$ 区间内的任何数字都可以用 $nums$ 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

Soluiton

容易证明，对于正整数 $x$，如果区间 $[1,x−1]$ 内的所有数字都已经被覆盖，且 $x$ 在数组中，则区间 $[1,2x−1]$ 内的所有数字也都被覆盖。

题意

现在有 $n$ 个音符和 $m$ 对共鸣关系，编号为 $1-n$，每个音符自己有一个奏响时的优美程度，共鸣关系 $(x,y,z)$ 表示音符 $x$ 和 $y$ 同时奏响的额外优美程度是 $z$，同时不奏响则为 $-z$，其他情况为 $0$，求最大优美程度。$(n,m \in [1,1e5])$

思路

对于一对共鸣关系而言，在不选的情况下收益为 $-z$，则选择一个的话，收益为 $-z + z = 0$，都选择的话为 $-z + 2z = z$。因此可以预先把每对关系的两个数都加上 $z$，刚开始我们是不选任何有联系的音符的，因此初值为 $-z$，那么选择一个数就会加上 $z$，选择两个就会加上 $2z$，满足了之前所讨论的关系。答案初始化为所有关系都不选的情况，即 $-sum(z)$，然后只要贪心的选择对答案有正贡献的值就行了。

题目

有 $n$ 个敌人，你现在的武器的耐久度为 $m$,杀每个敌人要消耗 $a_i$ 点耐久度，同时得到可以再杀死 $b_i$ 个人的权利。问最多可以杀死多少人，在杀人最多的情况下最少要消耗多少耐久度？

Solution

首先会想到对人进行分类，一类是 $b_i$ 为 $0$ 的，一类是 $b_i$ 不为 $0$ 的。

题意

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

Solution1

枚举重复的字符，然后计算对应字符的能构成的最大长度，取最大值。

题意

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

Solution

栈里面存左括号的位置，当遇到右括号时：

题意

给定两个严格递增数组，从任意一个数组出发到任意一个数组结束，当遇到相同元素时可以切换到另一个数组，只能从左到右走且每个数只计算一次，求最大累计得分。

Solution

当遇到两个数组都有的元素时可以切换，那其实从上一次遇到相同到这一次，假设中间这部分元素和是 $sum$，无非是看到底是上面这部分的 $sum$ 更大还是下面的 $sum$ 更大，然后选走罢了，如此循环下去。至于判断相同元素，提前用map记录每个元素的位置就好了。时间复杂度$O(n)$。

题意

给你一个只包含小写字母的字符串 s ，你需要找到 s 中最多数目的非空子字符串，满足如下条件：

1. 这些字符串之间互不重叠，也就是说对于任意两个子字符串 s[i..j] 和 s[k..l] ，要么 j < k 要么 i > l 。
2. 如果一个子字符串包含字符 char ，那么 s 中所有 char 字符都应该在这个子字符串中。

题意

一共有 $n$ 只牛在花坛旁边，第 $i$ 头牛每分钟破坏 $d_i$ 朵花，把第i头牛带回牛棚需要 $2 \times ti$ 这么多时间，每次只能带回一头牛，请问怎样能使得被破坏的花最少。

solution

以小化大，先考虑两头牛，先领 $a$ ，损失为：$2\times{t_a}\times{d_b}$，先领 $b$，损失为 $2\times{t_b}\times{d_a}$，故得到排序条件 ${a_t \times {b_d} < b_t \times {a_d}}$，最后模拟得出答案。

题意

$n$ 栋建筑，第 $i$ 栋建筑需要 $s_i$ 时间修，截止到 $t_i$ 时间，问最多可以修多少建筑。

solution

我们可以类比成写作业，先截止的我们会先做，这是大体的贪心策略。但他并不是最优的，因为可能那一科会花你非常多的时间，够你做更多的科目，得不偿失。因此我们用优先队列维护做过的作业中花费时间最大的那份，当目前要做的作业时间不够的时候，与这个最大值比较看是否花的时间更少，可行的话就把这个塞进去，那个丢出来，这样做了同样多的作业却花了更少的时间，同时维护答案。

题意

给定n个城市坐标，每个城市可以多次到达，问一共到m次，最短花费。给出起始位置，并且起始位置不在城市上。

solution

不难猜到要么就是一条路走到黑要么就是在路上找的两个城市然后一直往返。因此我们从原来的位置，往左右两边一直走下去，顺便枚举路上每两座城市之间横跳的花费，维护最小花费，同时注意边界情况。