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

AtCoder Beginner Contest 378

时间:2024-11-04 17:57:48浏览次数:2  
标签:AtCoder Beginner leq int ll long 378 include sum

AtCoder Beginner Contest 378 总结

A

直接模拟,存 \(1\) 到 \(4\) 出现个数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1;
map<int,int> H;
void solve()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    H[a]++,H[b]++,H[c]++,H[d]++;
    int ans=0;
    for(int i=1;i<=4;i++) ans+=H[i]/2;
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}


B

要确定 \(d\) 处于哪一段区间内,分类讨论一下就能出来。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=105;
int n,m;
ll q[N],r[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>q[i]>>r[i];
    cin>>m;
    while(m--)
    {
        ll t,d;
        cin>>t>>d;
        if(d<=r[t]) cout<<r[t]<<'\n';
        else 
        {
            if((d-r[t])/q[t]*q[t]==d-r[t]) cout<<d<<'\n';
            else cout<<(d-r[t])/q[t]*q[t]+r[t]+q[t]<<'\n';
        }
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}


C

每次更新该值出现的位置,用 map 记录,如果出现了就输出位置,否则输出 \(-1\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int a[N];
map<ll,int> H;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(H.count(a[i])) cout<<H[a[i]]<<' ';
        else cout<<-1<<' ';
        H[a[i]]=i;
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}


D

观察数据的范围都很小,直接用 dfs 模拟。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=15;
int n,m,k;
char g[N][N];
bool v[N][N];
int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};
int dfs(int x,int y,int cnt)
{
    if(cnt==k) return 1;
    int ret=0;
    v[x][y]=1;
    for(int i=0;i<4;i++) 
    {
        int nx=x+fx[i],ny=y+fy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!v[nx][ny]&&g[nx][ny]=='.') 
            ret+=dfs(nx,ny,cnt+1);
    }
    v[x][y]=0;
    return ret;
}
void solve()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++) 
            cin>>g[i][j];
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]=='.') 
                ans+=dfs(i,j,0);
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}


E

要推一下式子:

设 \(S_i = (A_1+A_2+\dots+A_i) \mathbin{\mathrm{mod}} M\),就有:

\[ \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right) = \sum_{1 \leq l \leq r \leq N} (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M \]

然后因为 \(0 \leq S_{l-1},S_r < M\),所以

\[ (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M = S_r - S_{l-1} + \begin{cases} 0 & (S_{l-1} \leq S_r) \\ M & (S_{l-1} > S_r)\end{cases} \]

这样就去掉了取模。

设 \(X_r\) 为在 \(S_0\) 到 \(S_{r-1}\) 中大于 \(S_r\) 的数的个数。所以:

\[ \sum_{r=1}^n \sum_{l=1}^r (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M = \sum_{r=1}^N \left( S_r \times r - \sum_{l=1}^r S_{l-1} + M \times X_r \right). \]

那么问题就是对于 \(X_r\) 的维护,可以用权值线段数组,单调修改,区间查询。
要注意 \(S_i\) 可以等于 \(0\),所以要么加上偏移量,要么特判一下。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m;
ll a[N],b[N],c[N];
int lowbit(int x) 
{
    return x&-x;
}
void add(int k,int x)
{
    if(!k) return ;
    for(int i=k;i<=m;i+=lowbit(i)) c[i]+=x;
}
ll query(int k)
{
    ll ret=0;
    for(int i=k;i;i-=lowbit(i)) ret+=c[i];
    return ret;
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=b[i-1]+a[i];
    for(int i=1;i<=n;i++) b[i]%=m;
    ll ans=0,s=0;
    for(int i=1;i<=n;i++)
    {
        ans+=b[i]*i-s+(query(m)-query(b[i]))*m;
        s+=b[i];
        add(b[i],1);
    }
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}


F

先理解下题意,要满足条件,就是找到两个度数为 \(2\) 的点,这两个点的路径上全是度数为 \(3\) 的点,将这两个点连接即可。

那么考虑暴力查找,对于每个度数为 \(2\) 的点,找到另一个度数为 \(2\) 的点,只有下一个点度数为 \(3\) 才能走过去。显然这样的做法是 \(O(n^2)\) 的,也很容易被卡。

再进一步思考,将路径换成两点到最近公共祖先的路劲拼起来,而且最近公共祖先的度数必须是 \(3\)。那么就可以枚举所有度数为 \(3\) 的点作为根节点,搜索度数为 \(2\) 的点的个数 \(sum\),贡献就是 \(sum \times (sum-1)/2\),标记经过的所有度数为 \(3\) 的点,不用重复计算。

复杂度为 \(O(n)\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
vector<int> g[N];
bool v[N];
int dfs(int x,int fa)
{
    int ret=0;
    v[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        if(y==fa) continue;
        if(g[y].size()==2) ret++;
        else if(g[y].size()==3) ret+=dfs(y,x);
    }
    return ret;
}
void solve()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    ll ans=0;
    for(int i=1;i<=n;i++) 
    {
        if(g[i].size()==3&&!v[i])
        {
            ll x=dfs(i,0);
            ans+=x*(x-1)/2;
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

标签:AtCoder,Beginner,leq,int,ll,long,378,include,sum
From: https://www.cnblogs.com/zhouruoheng/p/18525023

相关文章

  • AtCoder Beginner Contest 378
    ABC378光速切掉前四题,结果倒在了第五题。A-Pairing难度:红。弱智题,不解释。#include<bits/stdc++.h>usingnamespacestd;intmain(){inta[5]={0};for(inti=1;i<=4;i++){intx;cin>>x;a[x]++;}intans=0;for(inti=1;i<=4;i++){......
  • AtCoder
    AtCoder做题记录AtCoderBeginnerContest378APairing检查一下\(1\sim4\)各有几个即可。代码BGarbageCollection根据\(d\)求出当天的余数,让后和\(r\)比较一些即可。代码。CRepeating用map存上一个该数的位置。代码。DCountSimplePaths疑似深搜板子。代......
  • AtCoder Beginner Contest 378 F题题解
    题目:F-AddOneEdge2思路:可以发现题目就是要我们找出有多少个点对满足连成后是一个简单环环上的点度都为3因为是一个简单图所以不可以有重边和自环那么就代表着这个环肯定是由两个度为2的点和大于1个度为3的点组成的注意到两个点的最近公共祖先一定可以跟这两个点形......
  • AtCoder Beginner Contest 378
    省流版A.判断奇偶性即可B.根据余数计算偏移天数即可C.用map记录每个数出现的位置即可D.枚举起点,枚举每步的方向,朴素搜索即可E.考虑前缀和的两数相减代替区间和的情况,减为负数则加回正数,用树状数组维护减为负数的情况数F.枚举点,作为连边的俩个点的lca,考虑维护路径点......
  • ABC378
    A-Pairing简单模拟。B-GarbageCollection找到一个大于等于\(d\)的最小值,满足模$q=r$。简单分讨。C-Repeating简单模拟。D-CountSimplePaths纯DFS。枚举每个起点,暴力搜索统计答案。E-ModSigmaProblemF-AddOneEdge2G-Everlas......
  • ABC378G 官方题解 ChatGPT 4.0 翻译
    题目描述给定整数\(A\)、\(B\)和\(M\)。有多少种排列\(P=(P_1,\dots,P_{AB-1})\)满足以下所有条件?请将结果对\(M\)取模。\(P\)的最长递增子序列的长度为\(A\)。\(P\)的最长递减子序列的长度为\(B\)。存在一个整数\(n\),将\(n+0.5\)添加到\(P\)的末尾不......
  • AtCoder Beginner Contest 378题解
    省流:dfs都会写错。正片:A:Pairing统计一下每个数字出现了多少次即可,每次减去2。#include<bits/stdc++.h>usingnamespacestd;inta,b,c,d,ans;map<int,int>mp;intmain(){ cin>>a>>b>>c>>d; mp[a]++,mp[b]++,mp[c]++,mp[d]++; while(mp[a]>=2)mp[a......