首页 > 其他分享 >AtCoder Beginner Contest 372(4/7)

AtCoder Beginner Contest 372(4/7)

时间:2024-09-24 09:35:54浏览次数:9  
标签:std AtCoder Beginner int res long -- && 372

比赛链接:https://atcoder.jp/contests/abc372

开头:

过去一个多月了,虽然暑假就上了蓝,但感觉自已一直还没达到蓝的水准,网络赛也打了两场,打的一般,开学之后一直比较忙,现在稳定了下来,接下来打算尽量每周3-4篇atcoder的题解吧,这是这周第一篇,虽然有点水(

A. delete .

思路:

签到题

代码:
#include<bits/stdc++.h>
using i64=long long;

void solve(){
    std::string s;
    std::cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]!='.'){
            std::cout<<s[i];
        }
    }
    std::cout<<'\n';
}

int main(){
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    solve();
}

B. 3^A

思路:

以开始读错题了,然后卡了会,其实就是转化成三进制

代码:
#include<bits/stdc++.h>
using i64=long long;

void solve(){
    i64 n;
    std::cin>>n;
    std::vector<i64> a(21);
    a[0]=1;
    for(int i=1;i<=20;i++){
        a[i]=a[i-1]*3;
    }
    std::vector<int> res(21,0);
    int cnt=0;
    for(int i=20;i>=0;i--){
        if(n>=a[i]){
            n-=a[i];
            res[i]=1;
            cnt++;
            if(n>=a[i]){
                res[i]=2;
                n-=a[i];
                cnt++;
            }
        }
    }
    std::cout<<cnt<<'\n';
    for(int i=0;i<=20;i++){
        if(res[i]==1){
            std::cout<<i<<' ';
        }
        else if(res[i]==2){
            std::cout<<i<<' '<<i<<' ';
        }
    }
    std::cout<<'\n';
}

int main(){
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    solve();
}

C. Count ABC Again

思路:

只看修改的位置即可,然后计数

代码:
#include<bits/stdc++.h>
using i64=long long;

void solve(){
    int n,q;
    std::cin>>n>>q;
    std::string s;
    std::cin>>s;
    int res=0;
    for(int i=0;i<n;i++){
        if(s[i]=='A'&&i+2<n&&s[i+1]=='B'&&s[i+2]=='C'){
            res++;
        }
    }
    for(int i=1;i<=q;i++){
        int x;char c;
        std::cin>>x>>c;
        x--;
        if(s[x]=='A'){
            if(x+2<n&&s[x+1]=='B'&&s[x+2]=='C'){
                if(c!='A'){
                    res--;
                }
            }
        }
        else if(s[x]=='B'){
            if(x+1<n&&x-1>=0&&s[x+1]=='C'&&s[x-1]=='A'){
                if(c!='B'){
                    res--;
                }
            }
        }
        else if(s[x]=='C'){
            if(x-2>=0&&s[x-1]=='B'&&s[x-2]=='A'){
                if(c!='C'){
                    res--;
                }
            }
        }
        if(c=='A'){
            if(x+2<n&&s[x+1]=='B'&&s[x+2]=='C'){
                if(s[x]!='A'){
                    res++;
                }
            }
        }
        else if(c=='B'){
            if(x+1<n&&x-1>=0&&s[x+1]=='C'&&s[x-1]=='A'){
                if(s[x]!='B'){
                    res++;
                }
            }
        }
        else if(c=='C'){
            if(x-2>=0&&s[x-1]=='B'&&s[x-2]=='A'){
                if(s[x]!='C'){
                    res++;
                }
            }
        }
        s[x]=c;
        std::cout<<res<<'\n';
    }
    
}

int main(){
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    solve();
}

D. Buildings

思路:

自己没想出来,但思路是有的,看来题解后明白了

其实就是求每个点之后的单调递增的子序列,每个点的后一个点必定在子序列中,同时为了降低时间复杂度,从后往前遍历,这样一次遍历就求出了所有的结果,当要插入的数比栈顶大时,栈就要弹出

代码:
#include<bits/stdc++.h>
using i64=long long;

void solve(){
    int n;
    std::cin>>n;
    std::vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        std::cin>>a[i];
    }
    std::vector<int> res(n+1,0);
    std::stack<int> st;
    for(int i=n-1;i>=1;i--){
        while(st.size()&&a[st.top()]<a[i+1]){
            st.pop();
        }
        st.push(i+1);
        res[i]=st.size();
    }
    for(int i=1;i<=n;i++){
        std::cout<<res[i]<<' ';
    }
    std::cout<<'\n';
}

int main(){
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    solve();
}

E. K-th Largest Connected Components(待补)

思路:

洛谷原题:永无乡

看了一下,基本上是并查集+FHQ,还没学到,待我学了再来补

代码:

F. Teleporting Takahashi 2(待补)

思路:
代码:

G. Ax + By < C(待补)

思路:
代码:

标签:std,AtCoder,Beginner,int,res,long,--,&&,372
From: https://www.cnblogs.com/lime-wk/p/18428392

相关文章

  • AtCoder Regular Contest 184 D Erase Balls 2D
    转化计数对象。直接数最终剩下的球的集合似乎并不好做。考虑数选择的球的集合(显然选择的顺序不重要,只有选择了哪些球重要)。先把所有球按\(x\)坐标从小到大排序。设我们选择的球的下标为\(i_1<i_2<\cdots<i_k\)。那么能选择这些球当且仅当\(y_{i_1}>y_{i_2}>\cdots......
  • 题解:AT_abc372_e [ABC372E] K-th Largest Connected Components
    题意给出\(q\)个操作。将\(u\)和\(v\)连边。问\(u\)所在的连通块中编号第\(k\)大的点。思路连通块很容易想到并查集,求第\(k\)大可以用平衡树(虽然赛时没看到\(k\le10\)),合并时将信息从将小的连通块合并到大的连通块,这样可以减少时间复杂度。什么?你不会写平衡......
  • AtCoder Beginner Contest 372 补题记录
    A-delete题意:输出删除字符串中.后的字符串思路:只输出字符串中不是.的字符voidsolve(){strings=sread();for(autoit:s)if(it!='.')cout<<it;cout<<endl;}B-3^A题意:给出M,求将M拆分成N个3的\(A_i\)次方相加思路:贪心,从大到小用......
  • 『比赛记录』ABC 372
    赛时差点改出了F,遂写比赛记录纪念。delete.ABC的T1一般都直接看完样例就莽的,比如这个就一眼是将字符串中的.删去然后输出其他的。Reviewrecord.B.3^A发现\(M\)范围很小,可以直接处理出值域内所有三的不同次幂,然后从大的开始减即可。因为把\(5\times10^5\)当成......
  • ABC372 F 题解
    F-TeleportingTakahashi2先把问题转化一下:把环断开成链,复制\((K+1)\)层,每走一步就相当于前进一层:可以想到一个简单的dp:设\(f(i,j)\)表示走到第\(i\)层第\(j\)个位置的方案数。初始化:\(f(0,1)=1\),其它均为\(0\),表示Takahashi从第\(0\)层的\(1\)位置......
  • ABC372 Review
    ABC372ReviewA语言基础题B类似于二进制拆分,就像跳LCA的时候一样,尽可能多地选大的即可。C一个位置的字母被改变仅仅会对相邻两个位置之类的答案产生影响,暴力统计即可。D对于每一个\(i\)去暴力地统计\(j\)显然是不可行的,所以可以转而想一想每个\(j\)会对答案产生多......
  • 题解:AT_abc372_f [ABC372F] Teleporting Takahashi 2
    题意给出一个\(n\)个点的有向图,点\(i\)连向点\((i+1)\),点\(n\)连向点\(1\)。再给你\(m\)条额外边。你的初始位置为\(1\),问你移动\(k\)步的不同方案数(仅当路径不同时两个方案不同)。思路先想怎样暴力转移,显然移动\(k\)步到达一个点的方案数为所有跟这个点连边的移......
  • 题解:AT_abc372_e [ABC372E] K-th Largest Connected Components
    博客内食用更佳这道题的\(k\le10\)其实没什么用,代码区别仅在于手写平衡树和使用内置容器。这道题让查询与一个节点相连的所有点的信息,所以不难想到并查集。又因为让查询第\(k\)大,所以不难想到平衡树和线段树启发式合并。至此思路明显。我们对并查集中的每个节点开一个平......
  • 题解:AT_abc372_c [ABC372C] Count ABC Again
    博客内食用更佳乍一看好像是数据结构。我们结合题目所求内容考虑。对于每次修改,能对答案产生影响的最多只能是当前字符向前和向后延伸\(2\)个元素所构成的长为\(5\)的子串。那么我们先\(\mathcal{O}(n)\)计算出来初始答案。每次修改的时候,不妨先把\(i-2\simi\)和\(i-......
  • AtCoder Beginner Contest 372(A - F)
    A:直接输出。B:把\(M\)三进制拆分,最多10位,每位最多为2,\(N\le20\)足够了。C:暴力修改,每次只产生\(O(1)\)影响。D:预处理st表,二分每个\(j\)会断哪些\(i\)产生贡献,差分一下。E:启发式合并平衡树,\(k\)更大也能做。F:只保留有特殊边经过的点,把\(i,j\)之间的\(j-i......