卡B题了,难受
B. qsgg and Subarray
B-qsgg and Subarray_牛客练习赛112 (nowcoder.com)
题意
给定一个长为n的序列,求有多少个子区间的按位与和为0。
思路
要想按位与之和为0,那么对于区间的所有数,二进制位都要有一个0。设f[i]表示二进制位i的最右边一个0出现的位置,枚举序列的每一个元素,更新数组f,左端点就取所有二进制位的最小值。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> v(n+1);
for(int i = 1; i <= n; i++) {
cin >> v[i];
}
array<int, 31> f{0};
ll ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 31; j++) {
if(!(v[i] >> j & 1)) {
f[j] = i;
}
}
int mn = INT_MAX;
for(int j = 0; j < 31; j++) {
mn = min(mn, f[j]);
}
ans += mn;
}
cout << ans << "\n";
return 0;
}
C. qsgg and Permutation
C-qsgg and Permutation_牛客练习赛112 (nowcoder.com)
题意
给定两个长为n的排列A,B,每次操作可以将A中的一个元素插到任意位置,求最少操作使得A = B。
思路
即求n减去最长公共子序列的长度。求最长公共子序列的O(nlogn)做法为,把B中的元素转化为该元素在A中第一次出现的位置,然后求B的最长上升子序列。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n+1), b(n+1);
for(int i = 1, tmp; i <= n; i++) {
cin >> tmp;
a[tmp] = i;
}
for(int i = 1; i <= n; i++) {
cin >> b[i];
b[i] = a[b[i]];
}
int cnt = 1;
vector<int> p(n+1);
p[1] = b[1];
for(int i = 2; i <= n; i++) {
if(b[i] > p[cnt]) {
p[++cnt] = b[i];
} else {
int j = upper_bound(p.begin(), p.begin() + cnt + 1, b[i]) - p.begin();
p[j] = b[i];
}
}
cout << n - cnt << "\n";
return 0;
}