随手记录一些刷题经历，先做做 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> 作为比较函数，意味着队列中优先级最高的元素（最小值）会位于堆顶。


1172 Panda and PP Milk - PAT (Advanced Level)

题意：大熊猫会排队吃盆盆奶。它们能和谐吃奶的前提，是它们认为盆盆奶的分配是“公平”的，即：更胖的胖达能吃到更多的奶，等胖的胖达得吃到一样多的奶。另一方面，因为它们是排好队的，所以每只胖达只能看到身边胖达的奶有多少，如果觉得不公平就会抢旁边小伙伴的奶吃。现在给定一排胖达的体重，请你帮饲养员计算一下，在保持给定队形的前提下，至少应该准备多少毫升的盆盆奶。

分析：

一眼上去感觉是贪心，因为每个潘达都仅和左右的比较体重。但是整体上还得满足一个趋势。因此可以考虑左右分方向考虑动态规划，设 l[i], r[i] 表示从左/右枚举至第 i 位时的最小容量，最终答案取二者的较大值。

转移的时候仅需要考虑与临近元素的关系，以向左转移为例：如果前一个元素比当前元素小，那应该有更多的奶吃，因此 l[i] = l[i-1]+100；如果前一个元素和另一元素相等，则维持 l[i]=l[i-1]（很重要）；否则赋位初始值 l[i]=200。


1174 Left-View of Binary Tree - PAT (Advanced Level) - 图结构

求一个树的最左侧序列。其实这个没啥难度，主要是给定的输入是中序遍历和先序遍历。要先将其处理为图结构。

其实也就是按照算法模拟一遍：

// [l, r] 表示中序遍历区间，返回当前根节点
int build(int& k, int l, int r)
{
    if (l > r) return 0;
    int rt = l;
    
    // 找到先序遍历的根节点在中序遍历中的位置
    for (; rt<=r; rt++) 
        if (pre[k] == in[rt]) break;
    
    // 以中序节点的 rt 分为左右子树，递归
    int root = in[rt]; k++;
    G[root].first  = build(k, l, rt-1);
    G[root].second = build(k, rt+1, r);
    return root;
}

11. 盛最多水的容器 - 双指针

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

class Solution {
public:
    // **移动双指针的重点不是使得每次更新更优，
    // 而是使得更新不会更劣**
    int maxArea(vector<int>& a) {
        int ans=0, l=0, r=a.size()-1;
        while (l<r) {
            int now = min(a[l], a[r]) * (r-l);
            if (now > ans) ans = now;
            if (a[l] < a[r]) l++; else r--;
        }
        return ans;
    }
};

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

分析：

用哈希表维护某个数是否出现过，然后按序遍历表即可。值得注意的是，比起使用 set，unordered_set 内部实现了一个 哈希表，查找的时间复杂度可达到O(1)。


1074 Reversing Linked List - PAT (Advanced Level)

给你链表的头节点 head ，每 k 个节点一组进行翻转，返回修改后的链表。

分析：

比较典的链表模拟题，可以先确定接下来 k 个节点的 head & tail，作为一个子链表进行翻转；翻转函数就是使得子链表的每条边反向。返回的时候把头尾节点对调一下就行了。

#include <bits/stdc++.h>
#define cle(x) memset(x,0,sizeof(x))
#define ok cout<<'!'<<endl
#define inf 2147483647
#define ll long long
#define fir first
#define sec second
#define pr pair<int,int>
using namespace std;

int read()
{   int x=0,f=0; char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}

#define N 100001
int H[N], nex[N];

// 把每条链的方向翻转即可
void reverse(int head, int tail) {
    int pre = head, cur = nex[head];
    while (pre != tail) {
        int next = nex[cur];
        nex[cur] = pre;
        pre = cur, cur = next;
    }
}

int main()
{
    int init, n, k;
    cin >> init >> n >> k;
    
    for (int i=1; i<=n; i++) {
        int adr, data, adr1;
        cin >> adr >> data >> adr1;
        H[adr] = data; nex[adr] = adr1;
    }
    
    nex[100000] = init;
    for (int p = 100000; p != -1;) {
        int head = nex[p], tail = p;
        for (int i=0; tail != -1 && i<k; i++) tail = nex[tail];
        if (tail == -1) break;
        int tnex = nex[tail];

        reverse(head, tail);
        nex[p] = tail;
        nex[head] = tnex;
        p = head;
    }

    for (int p=100000; p != -1; p=nex[p]) {
        if (p==100000) continue;
        if (nex[p] != -1) printf("%05d %d %05d\n", p, H[p], nex[p]);
        else printf("%05d %d -1\n", p, H[p]);
    }
    return 0;
}