牛客练习赛 112 B~C题题解

卡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;
}