随手记录一些刷题经历，先做做 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;
    }

c