526互联

Codeforces Round 898 (Div. 4) A~H

发布时间 2023-10-03 23:20:40作者: nannan4128

Codeforces Round 898 (Div. 4) A~H

A. Short Sort

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

思路：模拟即可

// 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即可。

// 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

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

思路：模拟

// 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

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

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

// 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

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

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

// 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

题意：当\(h_i\)能被\(h_{i+1}\)整除，我们可以选择一段连续的子集合\([h_l,h_{l+1},...,h_r]\)，并获得对应的\([a_l,a_{l+1},...,a_r]\)的值的和。问，当我们\(a_i\)的和不能超过\(k\)时候的能取的最大的子集长度是多少？

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

// 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

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

  • 选择一个子串\(AB\)变成\(BC\)并获得一个硬币
  • 选择一个子串\(BA\)变成\(CB\)并获得一个硬币

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

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

对于\(...AAB\)我们变成\(BC\)。对于\(BAA...\)我们变成\(CB\)。能变的次数是\(B\)左边或者右边\(A\)的个数。

那么考虑对于一个串\(A..ABAA..AABABA..ABA..\),能有贡献的段是\(B\)的个数，那么我们处理出连续的\(A\)的个数，然后排序，取前\(B\)个是答案。

// 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

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

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

关于如何用topo排序判环

// 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;
}