随手记录一些刷题经历，先做做 Acwing 上的算法基础课，之后再找找各校真题。

1. 多重背包问题（单调队列优化）

分析：

时间复杂度最多支持 O(NV)O(NV)，因此对多重物品的处理必须在常数时间完成；我们考虑多重背包和完全背包的区别：完全背包可采用刷表法，可以持续刷到最大容量 VV，但多重背包至多只更新 jj，j+vij+v_i，j+2vij+2v_i …… j+svij+sv_i，假设当前容量为 ii。我们发现可以利用单调维护 fjf_j，fj+vif_{j+v_i} 等值，使得队列里至多只有前 ss 个元素并保持单调递增性即可；利用这种方法可以枚举完 i≡r (mod vi)i\equiv r~ (mod~ v_i) 的位置，因此第二重循环我们只需枚举 00 ~ viv_i 的范围即可。

单调队列用 deque 在 ACWing 上还会超时，幽默了。


2. 第k大数（快排）

分析：

也是经典老题，首先注意到快排性质：每轮快排结束后，左边的数都<=a[mid]，右边的数都>=a[mid]，即 mid 处的值是最终固定的。 因此只要判断 mid 和 k 的关系即可递归寻找第k大数了。

代码：

int find(int l,int r, int k) {
    if (l>=r) return a[k];
    int i = l, j = r, mid = a[(l+r)/2];
    do {
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i<=j) swap(a[i++], a[j--]);
    } while (i<=j);
    
    if (k <= j) return find(l, j, k);
    else return find(i, r, k);
}

3. 最长上升子序列（LIS）

分析：

这题我从高中一直以来的解法是：在 O(n2)O(n^2) 时间复杂度的基础上，先用离散化将数组离散至 1 to n 范围内，然后用树状数组或线段树之类的数据结构硬刚，时间复杂度 O(nlog⁡n)O(n\log n)，但是大常数。

但实际上，这道题正确的（或者一种更简单的）做法是：考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。我们维护一个单调栈一样的东西，然后在栈上二分，从而持续构造一个当前最优的递增子序列，可证明这种构造是完备的。

我居然忘记怎么写二分了，奇耻大辱。

代码：

#define N 200001
int n, f[N], a[N], stk[N], st=0;

// 一个比较靠谱的二分函数
int middle_find(int x) {
    int l=1, r=st, mid, ans;
    while (l<=r) {
        mid = (l+r) >> 1;
        if (stk[mid] >= x) ans = mid, r = mid-1;
        else l = mid+1;
    }  return ans;
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];

    stk[++st] = a[1];
    for (int i=2; i<=n; i++) 
        // 如果满足单调性则直接入栈
        if (a[i] > stk[st]) stk[++st] = a[i];
        else {
            // 修改栈内元素，使得递增子序列最优
            int pos = middle_find(a[i]);
            stk[pos] = a[i];
        }
    
    cout << st << '\n';
    return 0;
}

4. 整数划分（DP状态构造）

一个正整数 nn 可以表示成若干个正整数之和，形如：n=n1+n2+…+nkn=n_1+n_2+…+n_k，其中 n1≥n2≥…≥nk,k≥1n_1≥n_2≥…≥n_k,k≥1；我们将这样的一种表示称为正整数 nn 的一种划分。现在给定一个正整数 n，请你求出 n 共有多少种不同的划分。

分析：

设 f[i][j] 正整数j 由前 i 个正整数可表示的划分数，则可等价为如下背包问题：有无限个重量为 1~n 的物品，装入容量为 n 的背包，这个实质上是求方案数，f[n][n] 输出即可；当然，第一维也可以滚掉。

代码：

// Initialize: 0 的方案数始终为 1
for (int i=0; i<=n; i++) f[i][0] = 1;
for (int i=1; i<=n; i++) 
    for (int j=0; j<=n; j++) {
        f[i][j] = f[i-1][j];
        // 由前 i-1 个正整数表示，加上由正整数 i 组成的方案数
        // 此处是完全背包板子，正向枚举 j
        if (j>=i) f[i][j] = (f[i-1][j] + f[i][j-i]) %p;
    }


5. 多米诺划分（状压）

把 N×M 的棋盘分割成若干个 1×2 的多米诺，有多少种方案。（题意见链接）

分析：

如果简单地构造动态规划的状态（如 f[i][j]f[i][j] 表示 i×j 矩阵的方案数），很容易发现这个状态推不出来，因为会存在一个多米诺横置，导致跨列的情况，无法从上一行/列转移。

但是看到 N 很小，考虑状压DP，令 f[i][T]f[i][T] 表示前 i 列的总方案数，状压后的状态表示 第 i 列 的每位是否向后一列凸出（0 表示没凸出，1 表示凸出了）。显然， 1 代表了横放的状态，0表示竖放的状态，因此状态需要偶数个 0 连在一起才算合法，先预处理所有合法状态，并初始化 f[0][0]=1f[0][0] = 1.

为啥这样设计状态呢？ 首先题目中有一个很好的性质，就是：当你把所有的横向多米诺放下去之后，若放置合法，则结果唯一。 即如果你知道最后一行有哪些位置已经被 i-1 行和 i 行的横置多米诺占用之后，你就可以唯一确定最后一行的摆放方式；其次，如果仅将状态设置为最后一列的占用状态，则无法区分横置的多米诺到底起点是哪儿，造成状态混乱。

那我们考虑从 f[i−1][S]f[i-1][S] 向 f[i][T]f[i][T] 的转移有哪些合法情况：

  • S 和 T 在同一数位上不能同时取 1，即 S&T=0S \& T = 0.
  • S, T 描述的是 i-1, i 行的多米诺是否凸出，而非实际的占有情况。通过 S∣TS|T 运算后得到了第 i 行的实际占有情况，并判断其是否合法；

考虑一下这两个转移就行了，答案取 f[m][0]f[m][0]，表示没有多米诺越界即可。


6. 区间分组（模拟+贪心）

给定 NN 个闭区间 [ai,bi][a_i,b_i]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

分析：

这题唉其实一点儿也不难，纯粹是脑子浆糊了，结果第二遍过的时候发现还是不会，感觉有点傻逼，记录一下。

首先开一个像是集合的东西去维护划分的组，把所有区间按左端点排序后依次往后扫，如果发现当前线段的左端点比现有集合中的右边界要大，则利用该线段的右端点去刷新边界；如果发现集合中所有的右边界都大于左端点（即相交），则贪心地往集合中加入一个元素（表示一个新的划分组）。

具体实现中，可以用小根堆去维护，方便时刻取出最小的右边界判断是否可以更新（其实也是利用了贪心的思想）。


7. 接雨水 - 力扣

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子在下雨之后能接多少雨水。

分析：

这个题本质上就是，每处位置水槽的高度是由左右两个区间中最高点的较小值决定的。我一开始的想法是维护一个 st 表，查询左右区间的最大值，然后取较小者就行了。但这个时间复杂度是 O(nlogn)，表现不太优秀。

然后就到了力扣民最喜欢的双指针环节。我们设左右端点的指针为 left 和 right，左区间最大高度值为 leftMax，右区间最大高度值为 rightMax，这样我们就可以从两侧向中间收缩。

当两个指针没有相遇时，执行以下操作：如果 h[left]<h[right]h[left]<h[right]，则必有 leftMax<rightMaxleftMax<rightMax，下标 left 处能接的雨水量等于 leftMax−h[left]leftMax−h[left]，右侧同理。


8.寻找峰值（局部最大、局部最小）

峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。

分析：

我服了…… 这道题给我最大的教训就是，别管想没想出来正解，想到啥先说出来，然后视情况口胡。最忌讳的是脑子里想了一堆，然后一句话不说，那老师哪知道你水平怎么样。

反正这题还挺反直觉的，老师强调了这题有 O(logn) 的解法，我寻思 logn 的算法不就二分吗，但这题没有单调性，怎么二分？但其实并不一定非要有序才可使用二分搜索，特定条件的无序也是可以的。

以下我们仅考虑局部最大点，对于当前二分到的某点 k 来说，如果两侧的点都比 a[k] 小，那么我们就找到了一个解；如果在该点呈现了从左到右的递增趋势，那么就更新左端点到 mid；如果呈现了从右到左的趋势，那么就更新右端点到 mid；如果是平的就无所谓了。后来一想感觉就顺着二分的思路往下想想就能得出结果，感觉还是脑子太猪鼻了。

9. TIPS ON priority_queue

问：priority_queue<int, vector<int>, greater<int> > q 和 priority_queue<int> q 这两种写法有什么不同？

答：

  • priority_queue<int> 是一个默认的最大堆。内部数据结构是一个基于 vector 的堆（heap），使用 less<int> 作为比较函数，这意味着队列中优先级最高的元素（最大值）会位于堆顶。

  • 而 priority_queue<int, vector<int>, greater<int> > q 是一个最小堆。它使用 greater<int> 作为比较函数，意味着队列中优先级最高的元素（最小值）会位于堆顶。