Codeforces Round 962

还得练

A Legs

先除 $4$ 再除 $2$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin>>n;
    int cnt=n/4;
    if(n%4!=0)cnt++;
    cout<<cnt<<endl;
}

int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

B Scale

按题意合理间隔输出即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <bits/stdc++.h>
using namespace std;
const int N =1010;

char mp[N][N];

void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)cin>>mp[i][j];
    for(int i=1;i<=n;i+=k){
        for(int j=1;j<=n;j+=k)
            cout<<mp[i][j];
        cout<<endl;
    }
}

int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

C Sort

对 $a$ 到 $z$ 这 $26$ 个字符分别开前缀和，统计 $l$ 到 $r$ 之间他们不同的数量，更改差异数量除 $2$ (向上取整)，即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int n, q;
string a, b;

void solve() {
    cin >> n >> q;
    cin >> a >> b;
    a = " " + a; 
    b = " " + b; 

    vector<vector<int>> va(26, vector<int>(n + 1, 0)), vb(26, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (char x = 'a'; x <= 'z'; x++) {
            va[x - 'a'][i] = va[x - 'a'][i - 1];
            vb[x - 'a'][i] = vb[x - 'a'][i - 1];
        }
        va[a[i] - 'a'][i]++;
        vb[b[i] - 'a'][i]++;
    }
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        long long ans = 0;
        for (char x = 'a'; x <= 'z'; x++) {
            ans += abs((va[x - 'a'][r] - va[x - 'a'][l - 1]) - (vb[x - 'a'][r] - vb[x - 'a'][l - 1]));
        }
        if(ans&1)ans++;
        ans/=2;
        cout << ans << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

D Fun

给定两个整数 $n$ 和 $x$ ，求 $ab + ac + bc \leq n$ 和 $a + b + c \leq x$ 的个正整数的三元组 $(a, b, c)$ 的个数。注意顺序问题(例如 $(1, 1, 2)$ 和 $(1, 2, 1)$ 被视为不同)， $a$ ， $b$ ， $c$ 必须严格大于 $0$ 。

赛时只顾着研究这两个式子能否融合化简为一个式子，还是见题少了

看第一个式子可知，$a * b \leq n$, 所以 $b$ 有 $n\log n$ 个选择，可以循环 $ab$ 求解
再通过两个式子推得 $c \leq \frac{n - ab}{a + b}$ 和 $c \leq x - a - b$ ,将范围小的加入答案即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){
    ll n,x,ans=0;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        for(int j=1;j*i<=n;j++){
            ll mn=min((n-i*j)/(i+j),(x-i-j));
            mn=max(mn,0);
            ans+=mn;
        }
    }
    cout<<ans<<endl;
}

int main() {
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

E Decode

赛时题都没弄太明白每次找到符合区间会使答案加 $l * (n - r + 1)$

用前缀和记录当前位置 $1$ $0$ 出现次数，$1$ 指代此处为 $1$，$-1$ 指代此处为 $0$。然后逐位记录当前前缀和的大小，如果之前存过，那么就更新答案。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

void solve(){
    string s;
    cin>>s;
    int n=s.size();
    s=" "+s;
    vector<ll>pre(n+1,0);
    for(int i=1;i<=n;i++){
        pre[i]=(s[i]=='1'?1:-1)+pre[i-1];
    }
    map<int,ll>cnt;
    cnt[0]=1;
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans=(ans+cnt[pre[i]]*(n-i+1)*1LL%MOD)%MOD;
        cnt[pre[i]]=(cnt[pre[i]]+i+1)%MOD;
    }
    cout<<ans<<endl;
}

int main() {
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}