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

AtCoder Beginner Contest 376

时间：2024-10-20 21:10:44浏览次数：1  
标签：AtCoder ch return Beginner int MAX read include 376

AtCoder Beginner Contest 376

A - Candy Button

有一个人按若干次按钮，如果距离上次得分的时间超过\(C\)，那么就会获得一颗糖。

给出这个人按按钮的时刻，回答最终会获得有多少糖。

模拟题

#include<iostream>
#include<cstdio>
using namespace std;
int n,c,a,ans;
int main()
{
    cin>>n>>c;
    for(int i=1,lt=-c;i<=n;++i)
    {
        cin>>a;
        if(a-lt>=c)++ans,lt=a;
    }
    cout<<ans<<endl;
    return 0;
}

B - Hands on Ring (Easy)

一个环被分成\(n\)个区域，一开始左手在区域\(1\)，右手在区域\(2\)，每次可以把一只手移动到一个相邻区域，但是任何时候两只手都不能在同一个区域。

现在给出Q个操作，每个操作给定手和一个位置，表示在不动另一只手的情况下将给定手移动到给定位置。

回答最小的总操作次数。

模拟题，判断是顺时针移动还是逆时针移动就好了。

#include<iostream>
#include<cstdio>
using namespace std;
int n,Q;
int nL,nR;
int p,ans;
char c;
int check(int a,int b,int c)
{
    //顺时针
    if(a<=c&&c<=b)return c-a;
    if(a>b&&a<=c+n&&c+n<=b+n)return c+n-a;
    if(a<=c&&c<=b+n&&a>=b)return c-a;
    //逆时针  
    if(a>=c)return a-c;
    else return a+n-c;
}
int main()
{
    cin>>n>>Q;
    nL=1,nR=2;
    while(Q--)
    {
        cin>>c>>p;
        if(c=='L')ans+=check(nL,nR,p),nL=p;
        else ans+=check(nR,nL,p),nR=p;
    }
    cout<<ans<<endl;
    return 0;
}

C - Prepare Another Box

给出N个物品，第\(i\)个物品的体积是\(a_i\)。现在有\(N-1\)个背包，第\(i\)个背包的容量是\(b_i\)，现在希望再加一个包，使得每个玩具都能放到一个容量大于其体积的背包中，每个背包只能放一个物品。

问加的这个包的容量的最小值是多少。

假设已经有\(n\)个包，判断很方便，两个数组分别排序之后检查对应位置大小关系即可。

再加一个二分答案即可求出最小值。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
#define MAX 200200
int n,a[MAX],b[MAX],c[MAX];
bool check(int x)
{

    for(int i=1;i<n;++i)c[i]=b[i];
    c[n]=x;
    sort(&c[1],&c[n+1]);
    cout<<endl;
    for(int i=1;i<=n;++i)
        if(a[i]>c[i])return false;
    return true;
}
int main()
{
    n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<n;++i)b[i]=read();
    sort(&a[1],&a[n+1]);
    int l=1,r=a[n],ans=-1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

D - Cycle

给定一个有向图，问是否存在一个包含节点\(1\)的环。

如果存在，求出最小的环的长度。

正图反图分别求一次到\(1\)的最短路。

对应点加起来就是包含这个点和\(1\)的最小环。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX 200200
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n,m,ans;
struct Graph
{
    int h[MAX],cnt;
    struct Edge{int v,next;}e[MAX<<1];
    void Add(int u,int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
    int dis[MAX];
    bool vis[MAX];
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >Q;
    void Dijkstra()
    {
        for(int i=2;i<=n;++i)dis[i]=n+1;
       	Q.push(make_pair(dis[1]=0,1));
        pair<int,int> u;
        while(!Q.empty())
        {
            u=Q.top();Q.pop();
            if(vis[u.second])continue;
            vis[u.second]=true;
            dis[u.second]=u.first;
            for(int i=h[u.second];i;i=e[i].next)
            {
                int v=e[i].v;
                if(vis[v])continue;
                Q.push(make_pair(u.first+1,v));
            }
        }
    }
}T1,T2;
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read();
        T1.Add(u,v);
        T2.Add(v,u);
    }
    T1.Dijkstra();
    T2.Dijkstra();
    ans=n+1;
    for(int i=2;i<=n;++i)ans=min(ans,T1.dis[i]+T2.dis[i]);
    if(ans>n)puts("-1");
    else printf("%d\n",ans);
    return 0;
}

E - Max × Sum

有两个长度为\(n\)的数组\(A\)和\(B\)。

现在需要选出一个大小为\(k\)的下标集合\(S\)，最小化\((\max_{i\in S}A_i)\times (\sum_{i\in S }B_i)\)

按照A排序，这样子枚举就可以确定最大值。

要最小化目标式，左边的max固定，所以要最小化右边的求和，因此选择最小的\(B\)就行了。

拿一个堆维护一下就解决了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX 200200
#define ll long long
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int T,K,n;
pair<int,int> A[MAX];
priority_queue<int> Q;
ll ans,sum;
int main()
{
    T=read();
    while(T--)
    {
        n=read();K=read();
        for(int i=1;i<=n;++i)A[i].first=read();
        for(int i=1;i<=n;++i)A[i].second=read();
        sort(&A[1],&A[n+1]);
        ans=1e18;sum=0;
        while(!Q.empty())Q.pop();
        for(int i=1;i<=K-1;++i)Q.push(A[i].second),sum+=A[i].second;
        for(int i=K;i<=n;++i)
        {
            sum+=A[i].second;
            ans=min(ans,sum*A[i].first);
            Q.push(A[i].second);
            sum-=Q.top();
            Q.pop();
        }
        cout<<ans<<endl;
    }
    return 0;
}

F - Hands on Ring (Hard)

一个环被分成\(n\)个区域，一开始左手在区域\(1\)，右手在区域\(2\)​，每次可以把一只手移动到一个相邻区域，但是任何时候两只手都不能在同一个区域。

现在给出Q个操作，每个操作给定手和一个位置，表示在可以移动另一只手的情况下将给定手移动到给定位置。

回答最小的总操作次数。

考虑dp，但是发现我们需要同时存在左右手的位置。

但是注意到每个条件执行完之后我们已经知道了一个手的位置，所以只需要知道另一个手的位置就好了。

设\(f[i][j]\)表示执行完第\(i\)步之后，没确定位置的那只手的位置是\(j\)。

考虑转移，要么像\(B\)题一样不动另一只手，判断顺时针还是逆时针即可。否则要移动这只手，一定是恰好移动到目标位置的下一个位置，然后让目标手移动过来。（贪心的想想，移动更多的位置只是单纯的为了后续的操作，那么不影响我先移动完这次操作再动另一只手）

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 3030
int n,Q;
int p[MAX],ans;
char c[MAX],s[10];
int f[MAX][MAX];
int check(int a,int b,int c)
{
    if(a==c)return 0;
    if(b==c)return 1e7;
    //顺时针
    if(a<=c&&c<=b)return c-a;
    if(a>b&&a<=c+n&&c+n<=b+n)return c+n-a;
    if(a<=c&&c<=b+n&&a>=b)return c-a;
    //逆时针  
    if(a>=c)return a-c;
    else return a+n-c;
}
int main()
{
    cin>>n>>Q;
    for(int i=1;i<=Q;++i)
    {
        scanf("%s%d",s,&p[i]);
        c[i]=s[0];
    }
    c[0]='L';p[0]=1;
    for(int i=0;i<=Q;++i)
        for(int j=1;j<=n;++j)
            f[i][j]=1e7;
    f[0][2]=0;
    for(int i=1;i<=Q;++i)
        for(int j=1;j<=n;++j)
        {
            int L,R;
            if(c[i-1]=='L')L=p[i-1],R=j;
            else L=j,R=p[i-1];
            //第一种转移 非目标手不动
            if(c[i]=='L')
                f[i][R]=min(f[i][R],f[i-1][j]+check(L,R,p[i]));
            else 
                f[i][L]=min(f[i][L],f[i-1][j]+check(R,L,p[i]));
            //否则，非目标手移动到目标位置旁边
            //顺时针的旁边
            int pos=p[i]%n+1;
            if(c[i]=='L')
                f[i][pos]=min(f[i][pos],f[i-1][j]+check(R,L,pos)+check(L,pos,p[i]));
            else
                f[i][pos]=min(f[i][pos],f[i-1][j]+check(L,R,pos)+check(R,pos,p[i]));
            //逆时针的旁边
            pos=(p[i]==1)?n:(p[i]-1);
            if(c[i]=='L')
                f[i][pos]=min(f[i][pos],f[i-1][j]+check(R,L,pos)+check(L,pos,p[i]));
            else
                f[i][pos]=min(f[i][pos],f[i-1][j]+check(L,R,pos)+check(R,pos,p[i]));
        }
    ans=1e7;
    for(int i=1;i<=n;++i)
        ans=min(ans,f[Q][i]);
    printf("%d\n",ans);
    return 0;
}

G - Treasure Hunting

给定一棵\(N+1\)个节点的有根树树，\(0\)号节点是根节点。现在在\(1-N\)中有一个节点有宝藏，第\(i\)个节点有宝藏的概率是\(\frac{a_i}{\sum_{j=1}^N a_j}\)。

每次可以选一个点挖掘，一个点能够被挖掘当且仅当其所有祖先节点都已经被挖掘过。初始时根节点已经被挖掘。挖掘到宝藏时停止。

求出最小的挖掘次数的期望。

先考虑一个极端情况，如果整个树是菊花树，那么一定每次会选择概率最大的进行挖掘。

为了方便，假设我们的挖掘序列是\(\{b_1,b_2,...,b_n\}\)

那么此时的期望是\(\frac{1}{\sum_{i=1}^n a_i}\sum_{i=1}^n a_{b_i}\times i\)​，我们需要最小化这个结果。

这个问题是一个套路贪心。

每次考虑最大的\(a_x\)，那么毫无疑问，我们一定要让\(x\)在序列中尽可能靠前的出现，那么这意味着，一旦其父亲节点被挖掘了，那么这个点一定立即跟在后面挖掘。

每次取出最大的\(a_x\)段，然后把他和其父亲节点拼在一起看成一个节点就好了。合成的新的节点的权值是该节点代表的所有点的\(a\)的平均值。

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
#define MAX 200200
#define MOD 998244353
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int fpow(int a,int b)
{
    int x=1;
    while(b)
    {
        if(b&1)x=1ll*x*a%MOD;
        a=1ll*a*a%MOD;
        b>>=1;
    }
    return x;
}
int N,fa[MAX];
int a[MAX],sum;
struct Node{int v,sz,x;}V[MAX];
bool operator<(Node a,Node b)
{
    if(1ll*a.v*b.sz==1ll*b.v*a.sz)return a.x<b.x;
    return 1ll*a.v*b.sz>1ll*b.v*a.sz; 
}
int f[MAX];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
int main()
{
    int T=read();
    while(T--)
    {
        N=read();sum=0;
        for(int i=1;i<=N;++i)fa[i]=read();
        for(int i=1;i<=N;++i)sum+=(a[i]=read());
        for(int i=1;i<=N;++i)V[i]=(Node){a[i],1,i};
        V[0]=(Node){-(int)1e8,1,0};
        set<Node> S;S.clear();
        for(int i=1;i<=N;++i)S.insert(V[i]),f[i]=i;
        int ans=0;
        for(int i=1;i<=N;++i)
        {
            int x=(*S.begin()).x;
            S.erase(V[x]);
            int y=getf(fa[x]);
            S.erase(V[y]);
            f[x]=y;
            ans=(ans+1ll*V[y].sz*V[x].v)%MOD;
            V[y].sz+=V[x].sz;
            V[y].v+=V[x].v;
            S.insert(V[y]);
        }
        int inv=fpow(sum,MOD-2);
        ans=1ll*ans*inv%MOD;
        printf("%d\n",ans);
    }
    return 0;
}

标签：AtCoder,ch,return,Beginner,int,MAX,read,include,376
From： https://www.cnblogs.com/cjyyb/p/18487907

相关文章

  • 题解：AT_abc376_c [ABC376C] Prepare Another Box
    很好的一道二分答案题。听说CSP考前写tj可以让rp+=inf？注：下文中\(w\)指物品重量序列，\(x\)指箱子容量序列。先问个问题：为什么我上来就敢肯定这是个二分答案题？或者说，单调性在哪儿？非常简单：如果一个盒子的容量越大，能装下的东西就更多（废话）。那么如果\(v\)不够用，可以扩......
  • 题解：AT_abc376_c [ABC376C] Prepare Another Box
    这道题要求把\(a\)数组和\(b\)数组一一匹配，且要求无法匹配的数量最多为一，并且这个无法匹配的元素最小。可以注意到我们把两个数组排序以后一一对应以后如果出现一个无法匹配的元素，那么这一定就是答案。但是如果我们从小到大枚举，会发现最后剩下的元素不一定最小，所以我们选择......
  • abc376C Prepare Another Box
    有N个玩具，大小分别为A[i]；另外有N-1个盒子，大小分别为B[i]。现要再买一个盒子，把所有玩具装到盒子里，要求每个玩具都装一个盒子，并且玩具大小不超过盒子大小。问买的盒子至少为多大？如果无法满足，输出-1。2<=N<=2E5,1<=A[i],B[i]<=1E9分析：将玩具按从大到小排序再依次处理，每次用不小于......
  • abc376D Cycle
    有N个顶点M条边的简单有向图，求包含1号点的最小环的顶点数，如果不存在，输出-1。2<=N<=2E5,1<=M<=2E5分析：bfs求最小环。#include<bits/stdc++.h>usingi64=longlong;voidsolve(){ intN,M; std::cin>>N>>M; std::vector<std::vector<int>>adj(N); fo......
  • abc376E Max x Sum
    有序列A[N]和B[N]，选出一组大小为K的下标，让A[i]的最大值乘以(B[i]之和)的结果最小，求最小值。1<=T<=2E5,1<=K<=N<=2E5,1<=A[i],B[i]<=1E6分析：因为A[i]跟B[i]要同步选，因此对下标排序，然后枚举每个A[i]作为最大值，从B[i]中选出最小的K个求和，得到结果，B[i]之和可以用堆来维护。#inclu......
  • abc376B Hands on Ring (Easy)
    由1~N的块构成的环，最初左手在1号、右手在2号，接下来有Q组操作{H,T}，H可以是L或者R，分别表示左手和右手，T是目标位置，移动时要求左右手不能在同一个块上。3<=N<=100,1<=Q<=100分析：模拟，关键在于如何判断是顺时针移动还是逆时针移动。#include<bits/stdc++.h>usingi64=longlong......
  • Atcoder Library 配置入门
    配置首先，你需要在这个blog里面下载AtcoderLibrary的压缩包。可以发现里面有三堆东西，一个python程序，两种语言的document，还有一个库文件夹。把库文件夹直接拖到你的编译器库文件相同目录下。Mingw的路径应该都是\lib\gcc\x86_64-w64-mingw32\8.1.0\include\c++，如果不是......
  • Atcoder Beginner Contest 376
    新猫ΛΛ＿_／(*ﾟーﾟ)／＼／|￣UU￣|＼／||／A.CandyButton\(\text{diff}19\)你按一次按钮就会得到一颗糖，如果这次按按钮和上次得到糖的间隔时间小于\(C\)则不会得到糖，给你若干按按钮的时间，问能得到多少糖intn,c;inta[1000001];signedmain(){cin>>n>>......
  • AtCoder Beginner Contest 376
    AtCoderBeginnerContest376\(A\)CandyButton贪心，模拟。点击查看代码intmain(){lln,c,x,last=-0x3f3f3f3f,ans=0,i;cin>>n>>c;for(i=1;i<=n;i++){cin>>x;if(x-last>=c){last=x;......
  • [ABC376E] Max × Sum 题解
    [ABC376E]Max×Sum题解原题链接洛谷链接一道简单的推性质题，首先明确一个性质，子集是非连续的，所以在计算时并不用连续区间求。拿过题来，首先想的是枚举\(B\)的最小子集，但其复杂度为\(O(C_N^K)\)复杂度过高，不足以通过本题。于是转变思路，枚举\(A\)之中的最大值。若\(a_i......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99