C. 区间排序
题目描述
给定一个数组 \(A\)，你要按照如下方式对 \(A\) 排序：
- 将 \(A\) 分割成互不相交的子段，且每个元素恰好属于一个子段。
- 准备一个空数组 \(B\)，按顺序把这些子段完整地插入到 \(B\) 中的任意位置。
求至少要分成几个子段。
思路
很明显我们会贪心的尽可能长的取子段直到不能取。所以我们来考虑怎么判断非法。
- 如果当前元素小于上个元素，那么很明显不能放在同一段。
- 或者如果当前元素大于原数组中第一个大于 \(A_l\) （\(l\) 是当前区间左端点）的元素，那么也不能放在同一段。因为当前子段一定会插在其之前，所以不能大于它。
使用 set 维护即可。
空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 1000001;int n, a[MAXN], ans;int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) {cin >> a[i];}set<int> s;s.insert(0), s.insert(1000001);for(int i = 1, j = 1; i <= n; i = j) {int x = *s.upper_bound(a[i]);for(; j <= n && (i == j || a[j] >= a[j - 1]) && a[j] <= x; ++j) {}ans++;for(int k = i; k < j; s.insert(a[k]), ++k) {}}cout << ans;return 0;
}
D. 精准拼接
题目描述
给定两个长为 \(N\) 的数列 \(A,k\)。你要找出一个最长的且满足以下条件的数列 \(p_1,p_2,\dots,p_m\)：
- \(1\le p_1<p_2<\dots<p_m\le N\)。
- 对于 \(\forall 1<i\le m\)，都有 \(\text{popcount}(A_{p_{i-1}}\text{AND} A_{p_i})=k_{p_i}\)。
思路
令 \(dp_{i}\) 表示以 \(i\) 结尾的满足条件的子序列的最长长度。
令 \(maxdp_{i,j,k}\) 表示一个转移 \(a\rightarrow b\) 满足 \(A_a\) 二进制下最高 \(10\) 位为 \(i\)，\(A_b\) 二进制下最低 \(10\) 位为 \(j\)，\(A_a,A_b\) 的最低十位的 \(\text{popcount}\) 为 \(k\) 中最大的 \(dp_a\)。
我们可以这样使用 \(maxdp\) 转移（收集型）：
- 此时明显 \(j\) 已经确定，所以我们可以枚举 \(i\)。
- 由于我们知道要求 \(k_i\)，所以我们还可以求出 \(k\)。直接转移即可。
并这样更新 \(maxdp\)：
- 这次是 \(i\) 已经确定，同样枚举 \(j\)。同理 \(k\) 也确定了，直接更新即可。
空间复杂度 \(O(N+V^2\log V)\)，时间复杂度 \(O(NV)\)，其中 \(V=2^{10}\)。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 100001;int n, a[MAXN], pop[1 << 20], maxdp[21][1 << 10][1 << 10], pos[11][1 << 10][1 << 10], fa[MAXN], ans, p;void Print(int x) {if(!x) {return;}Print(fa[x]);cout << x << " ";
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);freopen("stitch.in", "r", stdin);freopen("stitch.out", "w", stdout);cin >> n;for(int i = 1; i < (1 << 20); ++i) {pop[i] = pop[i - (i & -i)] + 1;}for(int i = 1; i <= n; ++i) {cin >> a[i];}for(int i = 1, x, dp; i <= n; ++i) {cin >> x;dp = 1;for(int j = 0; j < (1 << 10); ++j) {int v = x - pop[j & (a[i] >> 10)];if(v >= 0 && maxdp[v][j][a[i] & ((1 << 10) - 1)] + 1 > dp) {dp = maxdp[v][j][a[i] & ((1 << 10) - 1)] + 1, fa[i] = pos[v][j][a[i] & ((1 << 10) - 1)];}}if(dp > ans) {ans = dp, p = i;}for(int j = 0; j < (1 << 10); ++j) {int v = pop[a[i] & j];if(dp > maxdp[v][a[i] >> 10][j]) {maxdp[v][a[i] >> 10][j] = dp, pos[v][a[i] >> 10][j] = i;}}}cout << ans << "\n";Print(p);return 0;
}
