首页 > 其他分享 >AtCoder Beginner Contest 378 题解

AtCoder Beginner Contest 378 题解

时间：2024-11-12 19:50:45浏览次数：1  
标签：Showball AtCoder le int 题解 long 378 vector using

AtCoder Beginner Contest 378 题解

比赛链接

A - Pairing 贪心

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    vector<int> a(5);
    for(int i=0;i<4;i++){
        int x;
        cin>>x;
        a[x]++;
    }
    int cnt=0;
    for(int i=1;i<=4;i++) cnt+=a[i]/2;
    cout<<cnt<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

B - Garbage Collection

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    int n;
    cin>>n;
    vector<int> q(n),r(n);
    for(int i=0;i<n;i++){
        cin>>q[i]>>r[i];
    }
    int m;
    cin>>m;
    while(m--){
        int x,d;
        cin>>x>>d;
        x--;
        cout<<d+(q[x]+r[x]-d%q[x])%q[x]<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

C - Repeating

使用 map 开个桶记录一下每个数上次出现的位置即可。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    map<int,int> mp;
    for(int i=0;i<n;i++){
        if(!mp[a[i]]) cout<<"-1 ";
        else cout<<mp[a[i]]<<" ";
        mp[a[i]]=i+1;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

D - Count Simple Paths 深搜

数据范围很小，直接枚举每个点，然后从每个点开始深搜即可。标准的深搜，写法比较套路。注意 st数组的更新。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    int h,w,k;
    cin>>h>>w>>k;
    vector<string> a(h);
    for(int i=0;i<h;i++){
        cin>>a[i];
    }
    vector<vector<int>> st(h,vector<int>(w));

    auto check=[&](int x,int y){
        return (0<=x&&x<h&&0<=y&&y<w&&a[x][y]=='.'&&!st[x][y]);
    };

    const int dx[]={1,-1,0,0};
    const int dy[]={0,0,1,-1};
    int ans=0;
    function<void(int,int,int)> dfs=[&](int x,int y,int cnt){
        if(cnt>=k){
            ans++;
            return;
        }
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(check(xx,yy)){
                st[xx][yy]=1;
                dfs(xx,yy,cnt+1);
                st[xx][yy]=0;
            }
        }
    };
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(a[i][j]=='.') {
                st[i][j]=1;
                dfs(i,j,0);
                st[i][j]=0;
            }
        }
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

E - Mod Sigma Problem 思维

如果两层都要取模，那就非常简单，只有一层，我们先不管取模尝试化简这个式子。

考虑使用前缀和，原式 = $\sum_{1\le l,r \le N} ({S_r-S_{l-1}}) $ 。

继续化简: \(\sum_{1\le i \le N} \sum_{1\le j \le i} ({S_i-S_{j-1}})\) = \(\sum_{1\le i \le N} \sum_{1\le j \le i-1} ({S_i-S_{j}})\)

把 \(S_i\) 拿出来，即：\(\sum_{1\le i \le N} ({i*S_i-\sum_{1\le j\le i-1}S_{j}})\) 。

式子被我们化成了差的形式，因此，如果 \(S_i < S_j\) 那么结果就会变成负数，因此我们就需要加上一个 \(m\) 。

考虑如何快速统计需要增加的 \(m\) 的数量。发现问题转化为求在 \(s_i\) 之前有多少个数比它大。

其实就是经典的逆序对问题，使用归并排序或者树状数组即可解决。

这里采用树状数组，注意，这里的数组值要对 \(m\) 取模，值可能为 \(0\)，因此，使用权值树状数组时，可能会 TLE。

所以，我们只需要偏移一位下标即可。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    int n,m;
    cin>>n>>m;
    vector<i64> a(n+1),s(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=(s[i-1]+a[i])%m;
    }

    vector<i64> tr(m+2);
    auto add=[&](int x){
        for(;x<=m;x+=x&-x) tr[x]++;
    };

    auto getsum=[&](int x){
        i64 ret=0;
        for(;x;x-=x&-x) ret+=tr[x];
        return ret;
    };

    i64 tot=0,res=0;
    for(int i=1;i<=n;i++){
        res+=i*s[i]-tot;
        tot+=s[i];
        res+=1LL*m*(getsum(m)-getsum(s[i]+1));
        add(s[i]+1);
    }
    cout<<res<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

F - Add One Edge 2 图论

要构成满足条件的环，我们只需要首尾点的度数为 \(2\) , 中间点的度数为 \(3\) 即可。发现度数为 \(3\) 的点组成的联通块周围的度数为 \(2\) 的点两两都是可达的。

那么我们只需要维护出每个点周围有多少个度数为 \(2\) 的点，然后乘法原理即可。最后 \(BFS\) 统计一下答案即可。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
    int n;
    cin>>n;
    vector<vector<int>> e(n);
    vector<int> d(n);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        u--,v--;
        e[u].push_back(v);
        e[v].push_back(u);
        d[u]++;
        d[v]++;
    } 

    vector<int> w(n);
    function<void(int,int)> dfs=[&](int u,int fa){
        for(auto v:e[u]){
            w[u]+=(d[v]==2);
            if(v==fa) continue;
            dfs(v,u);
        }
    };

    auto bfs=[&](int st){
        int ret=0;
        queue<int> q;
        q.push(st);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            ret+=w[u];
            d[u]=0;
            for(auto v:e[u]){
                if(d[v]!=3) continue;
                q.push(v);
            }
        }
        return ret;
    };

    dfs(0,-1);
    
    i64 ans=0;
    for(int i=0;i<n;i++){
        if(d[i]==3){
            int t=bfs(i);
            ans+=1LL*t*(t-1)/2;
        }
    }
    cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

标签：Showball,AtCoder,le,int,题解,long,378,vector,using
From： https://www.cnblogs.com/showball/p/18542511

相关文章

  • 题解：[XIX Open Cup, Grand Prix of Korea] Dev, Please Add This!
    前置知识：2-SAT题意[XIXOpenCup,GrandPrixofKorea]Dev,PleaseAddThis!在一张网格上有以下几种物品：空地（.）墙（#）星星（*）一个球（O）现在你要玩一个游戏。你可以让球朝上下左右某一个方向移动，但是一旦移动就必须走到底，也就是说直到前面是墙或者边界才能停。另外，如果你走......
  • 【题解】洛谷P7286：「EZEC-5」人赢
    P7286「EZEC-5」人赢可以想到对于每个数要找到比他大的数中下标最大的数，我们按照数的大小排序，我们维护原序列的一个指针，对于每个数如果比指针大那么就左移指针，可以思考下为什么：指针上的数比现在这个数要小那比后面的数都小，于是我们左移指针直到大于这个数，可以发现我们也在一直......
  • 【题解】洛谷P8346：最澄澈的空与海
    【题解】洛谷P8346：最澄澈的空与海猜结论题，本身其实很简单，在纸上画个差不多就能想出来，我一开始想二分图最大匹配，但是还是太大了，不可以。当一个二分图有且仅有一种解时，必定有节点的入度为\(1\)。我们想到有多种匹配的情况，可以想到如果这是一个环的情况，一个左边的点将他右边的点......
  • MX-S5 T1~T2 题解
    MX-S5题解A.王国边缘题目链接见到循环结构，先把下标转成从\(0\)开始，以方便用同余描述位置。倍增。用二元组来表示位置：\((u,v)\)表示第\(u\)个循环节的第\(v\)个位置。设\(f(i,j)\)表示从位置\((0,i)\)开始跳\(2^j\)次以后的位置。假设已经可以初始化\(f(i,......
  • CF 705 题解
    CF705题解AHulk模拟即可.BSpiderMan打sg表可以发现,奇数个球先手必败(sg=0),偶数先手必胜(sg=1).多个组合只要把sg值异或起来就好.CThor暴力模拟就可以了,用队列模拟.DAntMan结论:按照编号由小到大加入链表,每次尽量让答案最小贪心就是对的.若原来是......
  • 题解：洛谷 P5180 【模板】支配树
    在图论模拟赛被T4的有向图必经点硬控了\(10^9+7s\)，写篇题解纪念一下。其实，求有向图的必经点，通法就是支配树。一些定义：支配点：在确定起点\(S\)的情况下，对于一个点\(k\)，若存在\(x\)，使得删除\(x\)以及与\(x\)连接的边后，\(x\)与\(k\)，不再强连通，那么就称\(k\)为\(x......
  • 【题解】洛谷P3118： Moovie Mooving G
    洛谷P3118：MoovieMoovingG看到数据范围考虑状压，题目要求看的电影最少那就维护时间最大，我们设\(f_{i}\)为\(i\)状态最多可以看多久的电影，对于不在集合的点我们枚举转移。我们每个开始时间都对应一个截至时间，问能加入这个点，每个点花费时间是固定的，我们又要不间断所以我们找......
  • CF785D 题解
    CF题目luogu题目题解似乎清一色是同一个做法，这里给一个容斥的做法。首先枚举一个位置\(i\)，设\([1,i]\)的左括号个数为\(p\)，\([i+1,n]\)的右括号个数为\(q\)，那么以\(i\)这个位置为分界点的合法括号数有\(\sum_{i=1}^{\min(p,q)}C_p^iC_q^i\)个。通过范德蒙德卷......
  • CF 1325 题解
    CF1325题解AEhAbAnDgCd有\(\gcd(1,x)=1,\text{lcm}(1,x)=x\),因此输出\(1x\).BCopyCopyCopyCopyCopy要求严格上升子序列,那么答案的上界当然是去重后的元素个数.能否取到上界呢?当然可以,每一段内选一个你想要的就可以了.CEhabandPath-eticMEXs发现\(0,......
  • 历年CSP-J初赛真题解析 | 2020年CSP-J初赛完善程序（34-43）
    学习C++从娃娃抓起！记录下CSP-J备考学习过程中的题目，记录每一个瞬间。附上汇总贴：历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客（质因数分解）给出正整数n，请输出将n质因数分解的结果，结果从小到大输出。例如：输入n=120，程序应该输出22235，表示120=2×2×2×......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99