Codeforces Round 898 (Div. 4)A~H

Nannan Lv5
  2024-09-24 22:31 2024-09-24 22:31 Created   2024-09-30 20:01:25 2024-09-30 20:01:25 Updated      

Codeforces Round 898 (Div. 4) A~H

A. Short Sort

题意：输出不一样的字符的个数

思路：模拟即可

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
// 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--)
    {
        string s;
        string t = "abc";
        cin>>s;
        int cnt = 0;
        for(int i = 0;i < 3; i++)
        {
            if(s[i] != t[i])cnt++;
        }
        if(cnt>2)cout<<"NO\n";
        else cout<<"YES\n";
    }


    return 0;
}

B. Good Kid

题意：可以选一个数+1，然后把所有数乘起来，问如何操作使得值最大。

思路：排序，把最大的+1即可。

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
// 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 a[N];
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++)
            cin>>a[i];
        sort(a+1,a+1+n);
        a[1] += 1;
        ll ans = 1;
        for(int i = 1;i <= n; i++)
            ans *= a[i];
        cout<<ans<<"\n";
    }


    return 0;
}

C. Target Practice

题意：每一圈有一个权值，问总分数。

思路：模拟

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 20;
char a[N][N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        for(int i = 1;i <= 10; i++)
            for(int j = 1;j <= 10; j++)
                cin>>a[i][j];
        ll ans = 0;
        for(int j = 1;j <= 10; j++)
        {    if(a[1][j]=='X')ans += 1;
                    if(a[10][j]=='X')ans += 1;}

        for(int j = 2;j <= 9; j++)
        {    if(a[2][j]=='X')ans += 2;
                    if(a[9][j]=='X')ans += 2;}

        for(int j = 3;j <= 8; j++)
        {    if(a[3][j]=='X')ans += 3;
                    if(a[8][j]=='X')ans += 3;}

        for(int j = 4;j <= 7; j++)
       {     if(a[4][j]=='X')ans += 4;
                   if(a[7][j]=='X')ans += 4;}

        for(int j = 5;j <= 6; j++)
        {    if(a[5][j]=='X')ans += 5;
                    if(a[6][j]=='X')ans += 5;}

        for(int i = 2;i <= 9; i++)
        {    if(a[i][1]=='X')ans += 1;
                    if(a[i][10]=='X')ans += 1;}

        for(int i = 3;i <= 8; i++)
        {    if(a[i][2]=='X')ans += 2;
                    if(a[i][9]=='X')ans += 2;}

        for(int i = 4;i <= 7; i++)
        {    if(a[i][3]=='X')ans += 3;
                    if(a[i][8]=='X')ans += 3;}

        for(int i = 5;i <= 6; i++)
        {    if(a[i][4]=='X')ans += 4;
                    if(a[i][7]=='X')ans += 4;}



        cout<<ans<<"\n";
    }


    return 0;
}

D. 1D Eraser

题意：每次可以把连续的个细胞变成白色，问最少变多少次可以把所有的变白。

思路：暴力模拟即可。发现是黑的把它往后个变白。注意边界。

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
// 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 n,k;
        cin>>n>>k;
        string s;
        cin>>s;
        s = "?"+s;
        int cnt = 0;
        for(int i = 1;i <= n; i++)
        {
            if(s[i]=='B')
            {
                //cout<<"i+k-1 = "<<i+k-1<<"\n";
                for(int j = i;j <= min(n,i+k-1); j++)
                    s[j] = 'W';
                i = i+k-1;
                cnt++;
            }
        }
        //cout<<s<<"\n";
        cout<<cnt<<"\n";
    }


    return 0;
}

E. Building an Aquarium

题意：给你个点放的砖块的个数，往里面加水，问墙壁最大建多高，能满足装的水不超过。

思路：二分答案。用砖块个数-墙壁高度，负数部分是可以装水部分，按照这个来check即可。

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
// 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 a[N],l_max[N],r_max[N],b[N];
ll n,x;

bool judge(ll h)
{
    ll ans = 0;
    for(int i = 1;i <= n; i++)
        b[i] = a[i];
    for(int i = 1;i <= n; i++)
    {
        b[i] -= h;
        if(b[i]<0)
            ans += abs(b[i]);
    }
    return ans<=x;

}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>x;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        ll l = 1,r = 1e11;
        while(l<=r)
        {
            ll mid = (l+r)>>1;
            if(judge(mid))l = mid+1;
            else r = mid-1;
        }
        cout<<l-1<<"\n";
    }


    return 0;
}

F. Money Trees

题意：当能被整除，我们可以选择一段连续的子集合，并获得对应的的值的和。问，当我们的和不能超过时候的能取的最大的子集长度是多少？

思路：先预处理出符合整除条件的区间，但是这些区间不一定满足和小于等于，那么对于这些区间，我们枚举左端点二分右端点，答案对长度取即可。

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
// 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 a[N],h[N],pre[N];
int n,k;

bool judge(int l,int r)
{
    return pre[r]-pre[l-1]<=k;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        vector<pair<int,int>>res;
        for(int i = 1;i <= n; i++)
            cin>>a[i],pre[i] = 0;
        for(int i = 1;i <= n; i++)
            cin>>h[i];
        for(int i = 1;i <= n; i++)
            pre[i] = pre[i-1]+a[i];
        int l = 1,r = 1;
        while(r<=n-1)
        {
            //cout<<"l = "<<l<<" r = "<<r<<"\n";
            if(h[r]%h[r+1])
                res.push_back({l,r}),l = r+1;
            r++;
        }
        if(l!=n)
            res.push_back({l,n});
        for(int i = 1;i <= n; i++)
            res.push_back({i,i});
        //cout<<"[l,r]\n";
        // for(auto [l,r]:res)
        //     cout<<l<<" "<<r<<"\n";
        int ans = 0;
        for(auto [ll,rr]:res)
        {
            int l = ll,r = rr;
            if(pre[r]-pre[l-1]<=k)
                ans = max(ans,r-l+1);
            else{
                for(int i = l;i <= r; i++)
                {
                    int l_r = i,r_r = r;
                    while(l_r<=r_r)
                    {
                        int mid = (l_r+r_r)>>1;
                        if(judge(i,mid))l_r = mid+1;
                        else r_r = mid-1;
                    }
                    ans = max(ans,l_r-1-i+1);

                }

            }
        }
        cout<<ans<<"\n";
    }


    return 0;
}

/*
1
1 10
10
1
*/

G. ABBC or BACB

题意：你可以进行一下操作：

  • 选择一个子串变成并获得一个硬币
  • 选择一个子串变成并获得一个硬币

问最多可以获得多少硬币？

思路:考虑对于一个子串，我们如何变更优？

对于我们变成。对于我们变成。能变的次数是左边或者右边的个数。

那么考虑对于一个串,能有贡献的段是的个数，那么我们处理出连续的的个数，然后排序，取前个是答案。

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
// 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 le[N],ri[N];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int sz = s.size();
        s = "?"+s;
        int cnt = 0;
        vector<int>v;
        int b = 0;
        ll ans = 0;
        for(int i = 1;i <= sz; i++)
            if(s[i] == 'A')
                cnt++;
            else v.push_back(cnt),cnt = 0,b++;
        v.push_back(cnt);
        sort(v.begin(),v.end(),cmp);
        // for(auto x : v)
        //     cout<<x<<" ";
        // cout<<"\n";
        if(!b)
            cout<<0<<"\n";
        else
        {for(int i = 0;i < b;i++)
                    ans += v[i];
                cout<<ans<<"\n";}
    }   
    return 0;
}

H. Mad City

题意：有两个人和，告诉你起始位置，可以预知的位移，问是否一定可以逃跑。

思路：考虑什么时候可以逃跑？当在环里面的时候可以逃跑。那么如果当前不在环里面，就考虑到环上的点和到该点的距离，如果那么可以逃跑。那么接下来如果我知道哪些点是环上的点，在做一个是不是就解决了。那么现在问题变成了：如何确定哪些点是环上的点呢？是排序。

关于如何用topo排序判环 

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
// 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 n,a,b,d[N];
bool vis[N];
ll dist1[N],dist2[N];
vector<int> e[N];
bool vis2[N];
int tot,l[N];
void toposort()
{
    queue<int> q;
    tot = 0;
    for(int i = 1;i <= n; i++)
        vis2[i] = 0;
    for(int i = 1; i <= n; i++)
        if(d[i] == 1)
            q.push(i),vis2[i] = true;
    while(!q.empty())
    {
        int u = q.front();  q.pop();
        //l[++tot] = u;
       // cout<<"u = "<<u<<"\n";
        for(auto v : e[u])
            if(--d[v] <= 1 && !vis2[v])
                q.push(v),vis2[v] = true;
    }   

    // for(int i = 1;i <= tot; i++)
    //     cout<<l[i]<<" ";
    // cout<<"\n";
}



int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>a>>b;

        for(int i = 1;i <= n; i++)
            e[i].clear(),dist1[i] = 0,dist2[i] = 0,d[i] = 0;
        for(int i = 1; i <= n; i++)
        {
            int x , y;    cin>>x>>y;
            e[x].push_back(y);
            e[y].push_back(x);
            d[y]++;
            d[x]++;
        }
        toposort();
        queue<pair<int,ll>>q;
        q.push({a,0});
        dist1[a] = 0;
        memset(vis,false,sizeof(vis));
        vis[a] = true;

        while(!q.empty())
        {
            auto i = q.front();
            q.pop();
            int u = i.first,dis = i.second;
            for(auto v : e[u])
            {
                if(!vis[v])
                {
                    vis[v] = true;
                    dist1[v] = dis + 1;
                    q.push({v,dist1[v]});
                }
            }
        }
        
        q.push({b,0});
        dist2[b] = 0;
        memset(vis,false,sizeof(vis));
        vis[b] = true;

        while(!q.empty())
        {
            auto i = q.front();
            q.pop();
            int u = i.first,dis = i.second;
            for(auto v : e[u])
            {
                if(!vis[v])
                {
                    vis[v] = true;
                    dist2[v] = dis + 1;
                    q.push({v,dist2[v]});
                }
            }
        }
        bool ok = false;
        // for(int i = 1;i <= n;i++)
        //     cout<<d[i]<<" ";
        // cout<<"\n";
        //  for(int i = 1;i <= n;i++)
        //     cout<<dist1[i]<<" ";
        // cout<<"\n";
        //  for(int i = 1;i <= n;i++)
        //     cout<<dist2[i]<<" ";
        // cout<<"\n";
        for(int i = 1;i <= n;i++)
        {
            if(d[i]>1&&dist1[i]>dist2[i])ok = true;
        }
        if(ok)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}
  • Title: Codeforces Round 898 (Div. 4)A~H
  • Author: Nannan
  • Created at : 2024-09-24 22:31:00
  • Updated at : 2024-09-30 20:01:25
  • Link: https://redefine.ohevan.com/2024/09/24/Codeforces Round 898 (Div. 4)A~H/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Codeforces Round 898 (Div. 4)A~H
  1. Codeforces Round 898 (Div. 4) A~H
    1. A. Short Sort
    2. B. Good Kid
    3. C. Target Practice
    4. D. 1D Eraser
    5. E. Building an Aquarium
    6. F. Money Trees
    7. G. ABBC or BACB
    8. H. Mad City