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

1. 多重背包问题(单调队列优化)

分析:

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

单调队列用 dequeACWing 上还会超时,幽默了。


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(nlogn)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,其中 n1n2nk,k1n_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[i1][S]f[i-1][S]f[i][T]f[i][T] 的转移有哪些合法情况:

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

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


6. 区间分组(模拟+贪心)

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

分析:

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

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

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