牛客周赛 Round 38

比赛链接：牛客周赛 Round 38

A：小红的正整数自增

void solve(){
    ll n;
    cin >> n;
    for(int i = 0; i <= 9; i ++){
        ll y = n + i;
        if(y % 10 == 0){
            cout << i << '\n';
            return;
        }
    }
}

B：小红的抛弃后缀

思路：9的倍数数位和也是9的倍数，模拟即可

void solve(){
    string s;
    cin >> s;
    ll sum = 0;
    for(auto c : s){
        int a = c - '0';
        sum += a;
    }
    ll sum1 = 0, ans = 0;
    for(int i = s.size() - 1; i >= 0; i --){
        if((sum - sum1) % 9 == 0) ans ++;
        int a = s[i] - '0';
        sum1 += a;
    }
    cout << ans << '\n';
}

C：小红的字符串构造

思路：因为给出的k<=n/2，所以先每两个一组，剩下的位不出现回文即可

void solve(){
    ll n, k;
    cin >> n >> k;
    for(int i = 1; i <= k; i ++){
        int u = i % 3;
        if(u == 0) cout << "aa";
        else if(u == 1) cout << "bb";
        else cout << "cc";
        n -= 2;
    }
    for(int i = 1; i <= n; i ++){
        int p = i % 22;
        char c = 'd' + p;
        cout << c;
    }
}

D：小红的平滑值插值

思路：如果没有大于等于k的间隙就制造一个，如果有等于k没有大于k的，就是0，如果有大于k的间隙就往中间插数字，使得间隙缩小，注意如果间隙是k的整数倍要-1

void solve(){
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    ll ans = 0, res = 0;
    for(int i = 2; i <= n; i ++){
        ll cha = abs(a[i] - a[i - 1]);
        if(cha > k){
            ans += cha / k;
            if(cha % k == 0) ans --;
        }
        else if(cha == k) res ++;
    }
    
    if(ans > 0) cout << ans << '\n';
    else{
        if(res == 0) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}

E：小苯的等比数列

思路：枚举起始数字和公比即可

void solve(){
    int n;
    cin >> n;
    int ans = 0;
    vector<int> a(n + 1), num(N);
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        num[a[i]] ++;
        ans = max(ans, num[a[i]]);
    }
    for(int i = 1; i < N; i ++){
        for(int j = 2; j * i < N; j ++){
            int now = i, cnt = 0;
            while(now < N && num[now]){
                now *= j;
                cnt ++;
            }
            ans = max(ans, cnt);
        }
    }
    cout << ans << '\n';
}

 F：小苯的回文询问

思路：记录每一个数字的上一个出现的地址，用一个map来记录每个数字出现的地址，映射到b来先处理出每个数字上次出现的位置，然后再从后往前看有没有相邻出现的情况，如果有就让b[i] = b[b[i]]，这样就映射到了这个数字的相邻位置的前一个的位置，最后维护一下区间最值，只要区间最值大于等于L即可，区间最值实现方法多种

struct ST{
    int n, q;
    vector<vector<int>> f;
    ST(int _n) : n(_n), f(25, vector<int>(n + 1, 0)) {}
    void init(vector<int> & a){
        for(int i = 1; i <= n; i ++) f[0][i] = a[i];
        for(int j = 1; j <= 20; j ++){
            for(int i = 1; i + (1 << j) - 1 <= n; i ++){
                f[j][i] = max(f[j - 1][i], f[j - 1][i + (1ll << (j - 1))]);
            }
        }
    }
    int query(int l, int r){
        int len = __lg(r - l + 1);
        return max(f[len][l], f[len][r - (1 << len) + 1]);
    }
};
void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    map<int, int> la;
    for(int i = 1; i <= n; i ++){
        if(la.count(a[i])){
            b[i] = la[a[i]];
        }
        la[a[i]] = i;
    }
    for(int i = n; i >= 1; i --){
        if(b[i] == i - 1){
            b[i] = b[b[i]];
        }
    }
//    for(int i = 1; i <= n; i ++) cout << b[i] << ' ';
    ST st(n);
    st.init(b);
    while(q --){
        ll l, r;
        cin >> l >> r;
        ll ans = st.query(l, r);
        if(ans >= l) cout << "YES\n";
        else cout << "NO\n";
    }
}

G：小红的区间删除

思路：先思考逆序对的一种计算方法：一个数能过组成的逆序对就是它前面大于它的数字和它后面小于它的数字的数量之和

所以我们用维护两个东西：前缀和后缀

这里用滑动窗口来维护到 i 的一个最大的删除后满足性质的区间，每次加上这个区间的长度，原因是可以发现，窗口的前缀以及中间的都会随着窗口的改变被计算过，所以只需要计算一个后缀的区间即可

每次删除一个元素的时候要注意删去它在后缀中小于这个数字的贡献，再删去前缀中大于这个数字的贡献

当释放滑动窗口内的元素，加上这个元素前缀中的贡献和后缀中的贡献

特殊的，当整个数组的逆序数本身满足大于等于k，不要忘记加上

struct BIT{
    int n;
    vector<int> tr;
    BIT(int _n) : n(_n), tr(n + 10) {}
    int lowbit(int x) {return x & (- x);};
    void add(int x, int y){
        for(int pos = x; pos < n; pos += lowbit(pos)){
            tr[pos] += y;
        }
    }
    ll query(ll x){
        ll res = 0;
        for(int pos = x; pos; pos -= lowbit(pos)){
            res += tr[pos];
        }
        return res;
    }
    ll query(ll l, ll r){
        return query(r) - query(l - 1);
    }
};
void solve(){
    int n, k;
    cin >> n >> k;
    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    BIT bit1(1e6 + 10);//维护后缀 
    BIT bit2(1e6 + 10);//维护前缀 
    ll sum = 0;
    for(int i = n; i >= 1; i --){
        bit1.add(a[i], 1);
        sum += bit1.query(a[i] - 1);
    }//处理逆序对和后缀 
    
    int ans = (sum >= k);
    for(int i = 1, j = 1; i <= n; i ++){
        bit1.add(a[i], -1);//删掉ai 
        sum -= bit1.query(a[i] - 1);//从后缀中删掉比ai小的 
        sum -= bit2.query(a[i] + 1, 1e6);//从前缀中删掉（所有的-小于等于ai）即删去前缀中大于ai的 
//        cout << sum << '\n';
        while(j <= i && sum < k){//小于，就要把aj补回来，注意是补入前缀数组 
            bit2.add(a[j], 1);
            sum += bit1.query(a[j] - 1);
            sum += bit2.query(a[j] + 1, 1e6);
            j ++;
        }
        ans += (i - j + 1);
//        cout << i << ' ' << j << '\n'; 
    }
    cout << ans << '\n';
}