DP 基础题乱做

恶补基础 DP.

CF1061C 多样性

转移是经典的子序列 DP，考虑前 \(i\) 个数，子序列长度为 \(j\) 的方案数. 转移：

\[f_{i,j}=\begin{cases} f_{i-1,j-1}+f_{i-1,j}&j\mid a_i\\ f_{i-1,j}&otherwise. \end{cases} \]

可以滚动数组优化一维. 考虑优化，第二种转移直接继承，第一种转移不必枚举 \(j\)，可以 \(O(\sqrt v)\) 处理出所有约数，从大到小转移（与 \(0/1\) 背包原理类似）. 总时间复杂度 \(O(n\sqrt v)\).

CF2121H 冰宝贝

看到范围是区间，一个直接的想法是离散化. 然而我们可以换维，直接把值域当做 DP 值，把子序列长度开一维状态来记录. 另一个贪心的想法是我们一定要让子序列末尾尽量小，于是设计出一个状态：\(f_{i,j}\) 表示考虑前 \(i\) 个区间，不降子序列长度为 \(j\) 时末尾最小值，转移：

\[f_{i,j}=\begin{cases} f_{i-1,j-1}&l_i\le f_{i-1,j-1}\le r_i\\ f_{i-1,j} &otherwise. \end{cases} \]

优化仍然可以先滚动一维. 从 \(f\) 下标的角度看转移，就是区间 \([l_i,r_i]\) 整体右移了一位. 若当前最长子序列的末尾不大于 \(r_i\)，右移后不会有重叠的位置，最长子序列 \(+1\). 否则存在一个位置 \(p\) 重叠，考虑保留哪个更优. 注意到 \(f_j\) 显然不降，于是应该删掉原来 \(p\) 位置上的值，最长子序列长度不变.

考虑维护，实际上我们只关心查询最长子序列的长度，维护在有序的一列数中插入一个数，删除一个数，并且补位. 发现所有操作都可以用 multiset 维护，时间复杂度 \(O(\sum n\log n)\).

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int maxn = 2e5 + 10;
int T, n;void solve() {cin >> n;multiset<int> s; s.insert(0);while(n--) {int l, r; cin >> l >> r;auto p = s.upper_bound(r);s.insert(l); if(p != s.end()) s.erase(p);cout << s.size() - 1 << " ";} cout << "\n";return;
}int main() {ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> T; while(T--) solve();return 0;
}

AT_agc054_b [AGC054B] 贪心划分

agc 特有的结论计数题，鉴定为纯粹的脑筋急转弯.

结论：确定两人最终选择的物品集合后，两人拿物品的排列唯一确定，即二者构成双射. 可能不难感受到正确性，然而独立想到并不容易.

所以直接背包跑选 \(i\) 个物品凑到 \(sum\over2\) 的方案数，再赋予排列顺序加起来即可.

AT_agc054_c [AGC054C] 粗略排序

神人题.

考虑对于一个排列怎么交换使其合法. 发现由于所有数都比 \(1\) 大，\(1\) 至少要挪到位置 \(k+1\)，除非本来就在 \(k+1\) 前面，同理可以推广到数 \(i\) 至少要挪到 \(k+i\).

那么对于一个操作后的排列，\(p_i=i+k\) 的位置原来就只可能在区间 \([i+k,n]\)，乘起来即可.