首页 > 其他分享 > Codeforces Round 898 (Div. 4) A~H

Codeforces Round 898 (Div. 4) A~H

时间：2023-10-03 23:22:24浏览次数：52  
标签：const vis 898 ll Codeforces long cin int Div

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

标签：const,vis,898,ll,Codeforces,long,cin,int,Div
From： https://www.cnblogs.com/nannandbk/p/17741804.html

相关文章

  • Codeforces Round 901 (Div. 2)
    目录写在前面ABCDE写在最后写在前面比赛地址：https://codeforces.com/contest/1875。爱丽数码我真的好喜欢你啊为了你我要定制你的帆布包口牙！！！！A显然只会在剩余时间为1时使用工具，模拟即可。///*By:Luckyblock*/#include<bits/stdc++.h>#defineLLlonglong//========......
  • 「题解」Codeforces Round 894 (Div. 3)
    A.GiftCarpetProblem题目Sol&Code签到题#include<bits/stdc++.h>#defineN21typedeflonglongll;intmin(inta,intb){returna<b?a:b;}intmax(inta,intb){returna>b?a:b;}intT,n,m,a[4];std::strings[N];i......
  • CodeForces-1276#B 题解
    正文这是样例1第1组数据的图。让我们观察一下，路径1->6、1->7、2->6、2->7是可行的，所以答案为4。上述路径中好像点4没有贡献？再看看样例1第2组数据的图。发现点1和点4相互之间存在其他路径，无需经过点\(a\)和点\(b\)。综上，我们可以知道：在\(a\)和\(b\)......
  • Codeforces Round 730 (Div. 2) B. Customising the Track
    有\(n\)条高速公路，第\(i\)条告诉公路上的车流为\(a_i\)。现在可以执行以下操作任意次：将第\(i\)条高速公路上的一辆车移到第\(j\)条高速公路。需要求最小的\(\sum_{i=1}^{n}\sum_{j=i+1}^{n}|a_i-a_j|\)。不难发现可以构造\(\foralli,j,a_i=a_j\)使任......
  • Educational Codeforces Round 112 (Rated for Div. 2) A. PizzaForces
    有三种披萨：\(6\)、\(8\)、\(10\)块披萨。制作时间分别需要：\(15\)、\(20\)、\(25\)分钟。现在有\(n\)个人，每人需要一块披萨。询问使所有人能获得披萨的最快时间。观察：发现三种披萨的性价比都一样。（否则按最优性价比贪心）需要让得到的披萨数量\(m\geqn\)。不妨让\(n\)对......
  • 题解 Codeforces Round 901 (Div. 1) / CF1874A~E
    题解CodeforcesRound901(Div.1)/CF1874A~E比赛情况：过了AB。赛后发现B是假复杂度。https://codeforc.es/contest/1874A.JellyfishandGameProblemAlice&Bob又在博弈，Alice手上有\(n\)个苹果，第\(i\)个苹果的价值是\(a_i\)；Bob手上有\(m\)个苹果，第\(i\)......
  • Codeforces Round #885 (Div. 2)
    赛时A题意理解错误，导致A调试半小时没出样例，直接提前下班-->https://codeforces.com/contest/1848A.JellyfishandUndertale题意：初始时长为b的定时炸弹，没秒从n个工具中选一个加时长\(x_i\)，每次加时不能超过a，并流失一秒。问：炸弹爆炸前的最长时间是多长？思路：贪心枚举每个工具，每次......
  • Codeforces 1765H 题解
    题目大意题目大意给定一个\(n\)个点和\(m\)条边的有向图，并给定\(p_1,p_2,\cdots,p_n\)表示第\(i\)个点的拓扑序必须小于等于\(p_i\)，求出每个点的最小拓扑序。题解题解题目要求拓扑序尽量小，转换一下就是在反图上拓扑序尽量大。考虑拓扑排序，当一个点不得不入队......
  • div 让a内容居中方法
    <div>标签是HTML中的一个重要标签，它代表了一个文档中的一个分割区块或一个部分。在<div>标签中，我们可以放置各种内容，包括文本、图像、链接等等。有时候，我们需要将其中的链接<a>标签的内容水平居中显示，这就需要使用CSS设置div内部链接的居中显示。本文将详细讲解如何使用CSS使得<di......
  • Codeforces Round 901 (Div
    C.JellyfishandGreenApple题解显然\(n\%m=0\)，答案一定为\(0\)如果\(n>m\)，我们显然可以将\(n/m\)的苹果分给每个人，然后再处理$n%m$如果\(n<m\)，我们一定会将所有苹果一直对半切直到\(n>m\)，所以答案每次对半切一定会加\(n\)直到\(n\%m=0\)的时......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99