cf962

Codeforces Round 962(Div.3) (A-E)

A.Legs

    签到题，直接放代码

Code:

#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, ans;
        cin >> n;
        if(n==2)
            ans = 1;
        else if(n%4==0)
            ans = n / 4;
        else
            ans = n / 4 + 1;
        cout << ans << endl;
    }
    return 0;
}

B.Scale

    简单模拟题，同上，直接放代码

Code:

#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k;
        cin >> n >> k;
        vector<string> s(n + 1);
        for (int i = 1; i <= n;i++)
            cin >> s[i], s[i] = " " + s[i];
        for (int i = 1; i <= n; i += k){
            for (int j = 1; j <= n; j += k)
                cout << s[i][j];
            cout << endl;
        }
    }
    return 0;
}

C.Sort(前缀和)

时间复杂度：$O(26 \cdot n)$

    题意就是判断区间内不同字符的个数，注意$n,q$的范围均高达$2 \cdot 10^5$,所以使用前缀和预处理维护各个字母的前缀和，并离线处理询问即可。

Code:

#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, q;
        cin >> n >> q;
        vector<vector<int>> pre1(n + 1, vector<int>(30));
        vector<vector<int>> pre2(n + 1, vector<int>(30));
        string a, b;
        cin >> a >> b;
        a = " " + a, b = " " + b;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= 26;j++){
                pre1[i][j] = pre1[i - 1][j];
                pre2[i][j] = pre2[i - 1][j];
            }
            pre1[i][a[i] - 'a' + 1]++;
            pre2[i][b[i] - 'a' + 1]++;
        }
        while(q--){
            int l, r, ans = 0;
            cin >> l >> r;
            for (int i = 1; i <= 26;i++)
                ans += min(pre1[r][i] - pre1[l - 1][i], pre2[r][i] - pre2[l - 1][i]); //区间内相同字符数量
            ans = r - l + 1 - ans;
            cout << ans << endl;
        }
    }
    return 0;
}

D.Fun(枚举，数学)

时间复杂度：$O(n \ln n)$

题意

    给定两个整数$n$与$x$，寻找数对$(a,b,c)$的数量，其中$ab+ac+bc \le n$以及$a+b+c \le x$。注意，数对$(a,b,c)$中$a,b,c$三者相互独立（顺序固定）且均是正整数.

数据范围

• $1 \le n,x \le 10^6$
• $\sum n, \sum x \le 10^6$

思路

    首先从暴力枚举的角度统计数量，三层循环一定是超时的，我们退而求其次，考虑只枚举$a,b$；因为有限定条件$ab \le n$且$a+b \le x$，所以两层循环（$i,j$分别代表$a,b$）枚举$a,b$的复杂度为$j+ \frac{j}{2}+ \frac{j}{3}+…+1$,调和级数的复杂度趋向$O(n\cdot \ln n)$,对于题设中$1e6$的范围上限显然是可以接受的.
    通过枚举的方式，每次循环$a,b$的值，所以$c$的正整数数量就是数对数量。由于$a,b$已知，由题设中两条不等式可推断：

• $c \le \dfrac{n-ab}{a+b}$
• $c \le x-a-b$

    综上,$c$的正整数数量就是$min(\dfrac{n-ab}{a+b},x-a-b)$.

Code:

#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, x;
        cin >> n >> x;
        int mn = min(n, x);
        i64 ans = 0;
        for (int i = 1; i < mn;i++) //枚举a
            for (int j = 1; i * j < n && i + j < x;j++) //枚举b
                ans += min(x - i - j, (n - i * j) / (i + j));
        cout << ans << endl;
    }
    return 0;
}

E.Decode

时间复杂度：$O(n \log_2 n)$

题意

    给定一个二进制字符串,对于每对整数$(l,r)(1 \le l \le r \le n)$,计算连续子串$s_x s_{x+1}…s_y$中0的数量等于1的数量的数对数量$(x,y)(l \le x \le y \le r)$。最后的答案取$1e9+7$的模.

数据范围

• $1 \le |s| \le 2 \cdot 10^5$
• $\sum |s| \le 2 \cdot 10^5$

思路

    对于子串数量的统计我们可以进行转化：求任意区间$(l,r)$中满足条件的子串$(x,y)$ $\Rightarrow$ 求满足条件的子串${(x,y)}$的区间$(l,r)$$(l \le x,r \ge y)$的方案数。所以问题转化为寻找所有区间数量0和1相同的子串，若当前子串为$(x,y)$，字符串长度为$n$,那么合法的$(l,r)$的方案总数量显然是$x\times(n-y+1)$（乘法原理）.
    寻找区间0和1数量相等的子串，经典思路就是将所有0置负，那么区间数量相等等价于区间和为0，即前缀和$pre[r]=pre[l-1]$；对于每一个枚举到的$l$,我们都需要找到右边所有满足区间和为0的$r$,所以需要使用维护一个后缀和，所以对于每一位枚举到的$l$，它对答案的贡献为$l*suf$.

Code:

#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
const i64 p = 1e9 + 7;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        int n = s.length();
        s = " " + s;
        vector<int> pre(n + 1);
        map<int, i64> suf;
        for (int i = 1; i <= n;i++){
            pre[i] = pre[i - 1];
            pre[i] += (s[i] == '1' ? 1 : -1);
        }
        suf[pre[n]] = 1;
        i64 ans = 0;
        for (int i = n - 1; i >= 1;i--){
            //cout << i << ' ' << suf[pre[i]] << endl;
            ans = (ans + 1LL * i * suf[pre[i - 1]] % p) % p;
            suf[pre[i]] += n - i + 1; //边遍历边统计
        }
        cout << ans << endl;
    }
    return 0;
}