Codeforces Round 970 (Div. 3)A~F

Nannan Lv5
  2024-09-26 10:27 2024-09-26 10:27 Created   2024-09-30 20:02:21 2024-09-30 20:02:21 Updated      

Codeforces Round 970 (Div. 3) A~F

A. Sakurako’s Exam

把1的个数和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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int a,b; cin>>a>>b;
        if(a % 2){
            cout<<"NO\n";
            continue;
        }

        if(a % 2 == 0 && b % 2 == 0) cout<<"YES\n";
        else{
            if(a >= 2)
                cout<<"YES\n";
            else cout<<"NO\n";
        }
    }


    return 0;
}

B. Square or Not

映射到矩阵暴力判断就行了。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    set<int>st;
    int x = 1;
    while(x < N){
        st.insert(x*x);
        x++;
    }

    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        string s; cin>>s;
        if(st.find(n) == st.end()){
            cout<<"No\n";
            continue;
        }

        int m = sqrt(n);
        s = "?" + s;
        char a[m+10][m+10];
        int idx = 0;
        for(int i = 1;i <= m; i++)
        {
            for(int j = 1;j <= m; j++){
                a[i][j] = s[++idx];
            }
        }

        // for(int i = 1;i <= m; i++)
        // {
        //     for(int j = 1;j <= m; j++){
        //         cout<<a[i][j];
        //     }
        //     cout<<"\n";
        // }
        // cout<<"\n";

        bool ok = true;
        for(int i = 1;i <= m; i++)
        {
            if(a[i][1] != '1' || a[i][m] != '1')ok = false;
            if(a[1][i] != '1' || a[m][i] != '1')ok = false;
            if(!ok)break;
        }


        for(int i = 2;i <= m-1; i++)
        {
            for(int j = 2;j <= m-1; j++)
            {
                if(a[i][j] != '0'){
                    ok = false;
                    break;
                }
            }
            if(!ok)break;
        }

        if(!ok)cout<<"No\n";
        else cout<<"Yes\n";

    }


    return 0;
}

C. Longest Good Array

发现是个等差，二分求最多能到哪。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        ll L,R; cin>>L>>R;
        ll l = 1,r = R-L+1;
        while(l <= r)
        {
            ll mid = (l + r)>>1;
            if((1+mid)*mid/2 >= R-L+1)r = mid - 1;
            else l = mid + 1;
        }
        cout<<r + 1<<"\n";
    }


    return 0;
}

D. Sakurako’s Hobby

思路：因为是个排列，那么就不会有多个环连起来的情况。我们画个图就能发现，在一个环上的都可相互到达。那么连通性可以用并查集来维护。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;



int val[N],p[N],siz[N];

int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}

bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    siz[x] += siz[y];
    p[y] = x;
    return true;
}


int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        for(int i = 1;i <= n; i++)
        {
            int x; cin>>x;
            val[i] = x;
            p[i] = i;
            siz[i] = 1;
        }
        string s; cin>>s;

        s = "?"+s;
        for(int i = 1;i <= n; i++)
        {
            if(p[i] == i){
                bool notself = false;
                int last = i,now = val[i];
                while(1)
                {
                    if(now == i){
                        break;
                    }
                    last = now,now = val[now];
                    // cout<<"last = "<<last<<" now = "<<now<<"\n";
                    
                    merge(last,now);
                }
            }
        }

        map<int,int>mp;
        for(int i = 1;i <= n; i++)
        {
            if(s[i] == '0')//black
            {
               mp[p[i]]++;
            }
        }

        for(int i = 1;i <= n; i++)
        {
            cout<<mp[p[i]]<<" ";
        }
        cout<<"\n";

    }


    return 0;
}

E. Alternating String

思路：因为要求长度是偶数，且奇数位相同，偶数位相同。且删数操作只能最多一次，那么肯定是长度奇数的时候必须要用删数，长度偶数只能进行改数。

我们注意到如果是偶数长度，只考虑该数。统计哪个字母出现最多就行了。

如果是奇数呢？考虑先删再改。删哪个呢？我们枚举删每一个点的代价，且注意到这个被删的点之后的奇偶性发生互换，写的时候要小心边界。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;


char a[N],b[N];
int cnta[N][30],cntb[N][30];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
  
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        string s; cin>>s;
        if(n == 1){
            cout<<1<<"\n";
            continue;
        }

        s = "?" + s;
        int n1 = 0,n2 = 0;
        memset(cnta,0,sizeof(a));
        memset(cntb,0,sizeof(b));

        for(int i = 1;i <= n; i++)
        {
            if(i % 2)a[++n1] = s[i];
            else b[++n2] = s[i];
        }

        // for(int i = 1;i <= n1; i++)
        //     cout<<a[i];
        // cout<<"\n";

        // for(int i = 1;i <= n2; i++)
        //     cout<<b[i];
        // cout<<"\n";

        // cout<<"____________________\n";

        for(int i = 1;i <= n1; i++){
            for(int j = 0;j < 26; j++){
                cnta[i][j] = cnta[i-1][j];
            }
            // cout<<"a[i] - 'a' ="<<a[i]-'a'<<"\n";
            cnta[i][a[i]-'a']++;
            // for(int j = 0;j < 26; j++){
            //     cout<<cnta[i][j]<<" ";
            // }
            // cout<<"\n";
        }

        for(int i = 1;i <= n2; i++){
            for(int j = 0;j < 26; j++){
                cntb[i][j] = cntb[i-1][j];
            }
            cntb[i][b[i]-'a']++;
        }

        // cout<<"n = "<<n<<"\n";
        // for(int i = 0;i < 26; i++)
        //     cout<<cnta[n1][i]<<" ";
        // cout<<"\n";
        // for(int i = 0;i < 26; i++)
        //     cout<<cntb[n2][i]<<" ";
        // cout<<"\n";

        if(n % 2 == 0){
            int ans1 = 0,ans2 = 0;
            for(int i = 0;i < 26; i++)
                ans1 = max(ans1,cnta[n1][i]);
            ans1 = n1-ans1;
            for(int i = 0;i < 26; i++)
                ans2 = max(ans2,cntb[n2][i]);
            ans2 = n2-ans2;
            cout<<ans1+ans2<<"\n";
        }else{
            n--;
            int res = 1e9;
            int ans1 = 0,ans2 = 0;

            for(int i = 1;i <= n1; i++){//删奇数位置
                 // cout<<"i = "<<i<<"\n";
                ans1 = 0,ans2 = 0;
                for(int j = 0;j < 26; j++){
                    // cout<<"j = "<<j<<"\n";
                    
                    ans1 = max(ans1,cnta[i-1][j] + cntb[n2][j]-cntb[i-1][j]);
                    ans2 = max(ans2,cntb[i-1][j] + cnta[n1][j]-cnta[i][j]);

                    // cout<<"cnta[i-1][j] = "<<cnta[i-1][j]<<" cntb[n2][j]-cntb[i-1][j] = "<<cntb[n2][j]-cntb[i-1][j]<<"\n";
                    // cout<<"cntb[n2][j]="<<cntb[n2][j]<<" cntb[i-1][j]="<<cntb[i-1][j]<<"\n";
                    // cout<<"ans1 = "<<ans1<<" ans2 = "<<ans2<<"\n";
                }

                ans1 = n/2-ans1;
                ans2 = n/2-ans2;
                // cout<<"i = "<<i<<" ans1 = "<<ans1<<" ans2 = "<<ans2<<"\n";
                res = min(res,ans1+ans2);
            }

            ans1 = 0,ans2 = 0;
            for(int i = 1;i <= n2; i++){//删偶数位置
                ans1 = 0,ans2 = 0;
                
                for(int j = 0;j < 26; j++){
                    ans1 = max(ans1,cnta[i][j] + cntb[n2][j]-cntb[i][j]);
                    ans2 = max(ans2,cntb[i-1][j] + cnta[n1][j]-cnta[i][j]);
                }

                ans1 = n/2-ans1;
                ans2 = n/2-ans2;
                // cout<<"i = "<<i<<" ans1 = "<<ans1<<" ans2 = "<<ans2<<"\n";
                res = min(res,ans1+ans2);
            }


            cout<<res+1<<"\n";
        }
    }

    return 0;
}

F. Sakurako’s Box

思路：不难发现答案是：

做一个化简：

那么可以对后面的做一个前缀和的预处理。然后算就行了。取模要千万小心！当然你也可以直接用python写。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll qmi(ll a, ll b, ll mod)
{
    ll ans = 1 % mod;
    a %= mod;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}


ll a[N];
ll s[N];
ll n;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;

    while(t--)
    {
        cin>>n;
        ll inv = qmi(n*(n-1),mod-2,mod);

        for(int i = 1;i <= n; i++)
            cin>>a[i];

        for(int i = 1;i <= n; i++)
        {
            s[i] = (s[i-1]+a[i])%mod;
        }

        __int128 ans = 0;
        for(int i = 1;i <= n-1; i++){
            ll t = (s[n]-s[i])%mod;
            if(t < 0) t += mod;
            t %= mod;
            t *= a[i];
            ans = ans + t;
            ans %= mod;
        }

        ans *= 2ll;
        ans %= mod;
        ans *= inv;
        ans %= mod;
        
        cout<<(ll)ans<<"\n";

    }



    return 0;
}

  • Title: Codeforces Round 970 (Div. 3)A~F
  • Author: Nannan
  • Created at : 2024-09-26 10:27:00
  • Updated at : 2024-09-30 20:02:21
  • Link: https://redefine.ohevan.com/2024/09/26/Codeforces Round 970 (Div. 3)/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Codeforces Round 970 (Div. 3)A~F
  1. Codeforces Round 970 (Div. 3) A~F
    1. A. Sakurako’s Exam
    2. B. Square or Not
    3. C. Longest Good Array
    4. D. Sakurako’s Hobby
    5. E. Alternating String
    6. F. Sakurako’s Box