首页 > 其他分享 >AtCoder Beginner Contest 368 补题记录（A~D，F，G）

AtCoder Beginner Contest 368 补题记录（A~D，F，G）

时间：2024-08-24 22:04:45浏览次数：8  
标签：rt AtCoder Beginner int ll cin eb 补题 define

被伟大的 G 创似辣。

A

signed main(){
    int n,k;cin>>n>>k;
    F(i,1,n)cin>>a[i];
    queue<int>stk;
    G(i,n,1)stk.push(a[i]);
    while(k--){
        int t=stk.front();
        stk.push(t);
        stk.pop();
    }
    stack<int>t;
    F(i,1,n){
        t.push(stk.front());
        stk.pop();
    }
    while(t.size()){
        cout<<t.top()<<' ';
        t.pop();
    }
    cout<<'\n';
    return 0;
}

B

const int N=1000100;
int a[N];
signed main(){
    int n,k;cin>>n;
    F(i,1,n)cin>>a[i];
    int cnt=0;
    VI t;
    F(i,1,n)t.eb(a[i]);
    while(true){
        if(t.size()<2)break;
        sort(rng(t),greater<>());
        --t[0],--t[1];
        VI nw;
        for(auto &x:t)
            if(x>0)nw.eb(x);
        t.swap(nw);
        // cout<<"qwq: ";
        // for(auto &x:t)cout<<x<<' ';
        // cout<<'\n';
        ++cnt;
    }
    cout<<cnt<<'\n';
    return 0;
}

C

容易发现攻击 \(3\) 次一循环，一共对怪物攻击 \(5\) 次。所以对于 \(a_i\ge 5\) 的部分直接算，\(a_i<5\) 的部分暴力模拟。

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

const int N=1000100;
int a[N];
signed main(){
    int n;cin>>n;
    F(i,1,n)cin>>a[i];
    int cnt=0;
    F(i,1,n){
        cnt+=a[i]/5*3;
        a[i]%=5;
        while(a[i]>0){
            ++cnt;
            if(cnt%3==0)a[i]-=3;
            else --a[i];
        }
    }
    cout<<cnt<<'\n';
    return 0;
}

D

这让我想起了昨天做过的某道树剖。考虑在 \(a\) 中随机钦定一个结点为根，然后以这个点为根重构整棵树。枚举 \(a\) 中每一个点，将 \(a\) 到根的简单路径上每一个点都打一个标记。最后询问总共有多少个标记即可。

这个东西可以用树剖套线段树（或者 ODT）维护，维护当前区间内总共被打了多少个标记，然后再上一个懒标记即可，但是因为树剖没有复制板子导致吃 \(3\) 发罚时。

因此总时间复杂度为 \(O(n\log^2n)\)。

const int N=600100;
int n,m,s;
VI z[N];
int sz[N],dep[N],hev[N],top[N],up[N],dfn[N],back[N],a[N],xia[N];
void dfs(int u,int fa){
    sz[u]=1,dep[u]=dep[fa]+1,up[u]=fa;
    for(auto &v:z[u])if(v!=fa){
        dfs(v,u),sz[u]+=sz[v];
        xia[u]=v;
        if(sz[hev[u]]<sz[v])hev[u]=v;
    }
}
int idx;
void dfs2(int u,int Top,int fa){
    top[u]=Top;
    dfn[u]=++idx,back[idx]=u;
    if(hev[u])dfs2(hev[u],Top,u);
    for(auto &v:z[u])if(v!=fa&&v!=hev[u])
        dfs2(v,v,u);
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]])
            u=up[top[u]];
        else
            v=up[top[v]];
    }
    if(dep[u]<dep[v])
        return u;
    return v;
}
namespace yhb{

struct qwq{
    int l,r,sum,tag;
    void init(int p){
        l=r=p;sum=0;
        tag=0;
    }
    void yhb(int v){
        sum=(r-l+1)*v;
        tag=v;
    }
}z[N<<2];
qwq operator+(const qwq&l,const qwq&r){ //pushup
    return {l.l,r.r,l.sum+r.sum,0ll};
}
void build(int l,int r,int rt){
    if(l==r)return z[rt].init(l);
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
void pushyhb(int rt){ //pushdown
    if(z[rt].tag){
        z[rt<<1].yhb(z[rt].tag);
        z[rt<<1|1].yhb(z[rt].tag);
        z[rt].tag=0;
    }
}
void modify(int l,int r,int rt,int ll,int rr,int v){
    if(ll<=l&&r<=rr){z[rt].yhb(v);return;}
    int mid=l+r>>1;pushyhb(rt);
    if(ll<=mid)modify(l,mid,rt<<1,ll,rr,v);
    if(mid<rr)modify(mid+1,r,rt<<1|1,ll,rr,v);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
int query(int l,int r,int rt,int ll,int rr){
    if(ll<=l&&r<=rr)return z[rt].sum;
    int mid=l+r>>1,s=0;pushyhb(rt);
    if(ll<=mid&&mid<rr)return query(l,mid,rt<<1,ll,rr)+query(mid+1,r,rt<<1|1,ll,rr);
    if(mid<rr)return query(mid+1,r,rt<<1|1,ll,rr);
    return query(l,mid,rt<<1,ll,rr);
}
}
void lnk_modify(int u,int v,int w){
    while(top[u]!=top[v]){
        if(dep[up[top[u]]]<dep[up[top[v]]])
            swap(u,v);
        yhb::modify(1,n,1,dfn[top[u]],dfn[u],w);
        u=up[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    yhb::modify(1,n,1,dfn[u],dfn[v],w);
}
int lnk_query(int u,int v){
    int s=0;
    while(top[u]!=top[v]){
        if(dep[up[top[u]]]<dep[up[top[v]]])
            swap(u,v);
        s+=yhb::query(1,n,1,dfn[top[u]],dfn[u]);
        u=up[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    s+=yhb::query(1,n,1,dfn[u],dfn[v]);
    return s;
}

#ifndef THIS_IS_JIAOHUTI
signed main(){
    // freopen("count_in","r",stdin);freopen("count.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    int k;
    cin>>n>>k;F(i,1,n-1){
        int u,v;cin>>u>>v;
        Adde(u,v);
    }
    F(i,1,k)cin>>a[i];
    dfs(a[1],0),dfs2(a[1],a[1],0);
    yhb::build(1,n,1);
    F(i,1,k)lnk_modify(a[1],a[i],1);
    cout<<yhb::z[1].sum<<'\n';
}

E

咕咕咕。

F

每一个游戏之间互相独立，所以考虑求解每一个游戏的 SG 值。

对每一个 SG 值做一次记忆化 dp：

  • 若 \(x=1\)，则 \(\text{SG}(x)=0\)。
  • 否则，\(\forall\ d\ s.t.\ d\mid x\)，令 \(F\leftarrow x\)，则 \(\text{SG}(x)=\text{Mex}(F)\)。

求所有满足条件的 \(d\) 可以 Pollard-Rho 然后暴力重构做到大概是 \(O(n^\frac{4}{5}+n\ln^2n)\)，但是我懒所以直接暴力分解质因数，做到了 \(O(n^\frac{3}{2})\)。

const int N=600100;
int sg[N];
int SG(int x){
    if(~sg[x])return sg[x];
    VI t;
    for(int i=1;i*i<=x;++i){
        if(x%i==0&&i!=x)t.eb(SG(i));
        if(x%i==0&&i*i!=x&&x/i!=x)t.eb(SG(x/i));
    }
    unordered_set<int>se;
    for(auto &x:t)se.insert(x);
    F(i,0,1e18)if(!se.count(i)){
        return sg[x]=i;
    }
    return -1;
}
#ifndef THIS_IS_JIAOHUTI
signed main(){
    // freopen("count_in","r",stdin);freopen("count.out","w",stdout);
    // ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    int xr=0;
    FIN(sg);
    F(i,1,100000){
        // if(i%1000==0)cout<<i<<'\n';
        SG(i);
    }
    F(i,1,n){
        int x;cin>>x;
        xr^=sg[x];
    }
    if(xr)cout<<"Anna\n";
    else cout<<"Bruno\n";
}

#else

#define NO_MAIN
void no_main() {
    puts("pwp");
}

#endif

G

首先考虑维护一大堆线段树分别维护：

  • 每个元素最左边的 \(1\) 位置 \(i_1\)。
  • 每个元素最右边的 \(1\) 位置 \(i_2\)。
  • 每一段区间的和 \(i_3\)。
  • 每一段区间的最大 \(b\) 值 \(i_4\)。
  • 每一段区间 \(b\) 值的最大位置 \(i_5\)。

然后可以使用 \(4\) 个线段树来维护上述的所有信息。时间复杂度为 \(O(n)\)。

维护完之后可以发现暴力时间复杂度正确：因为选择乘法的次数不会超过 \(\log_2 10^{18}\approx 60\)，因此把所有连续 \(1\) 块暴力缩之后最多只会枚举 \(120\) 个元素。因此总的时间复杂度是 \(O(n\log n\log V)\)，其中 \(V\) 是值域。

说的有点混乱，建议结合代码查看。

#
/*
#define THIS_IS_JIAOHUTI
*/
#


#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#ifndef THIS_IS_JIAOHUTI
#define int long long
#endif
#define F(i,x,y) for(int i=x;i<=y;++i)
#define G(i,x,y) for(int i=x;i>=y;--i)
#define FD(x,y) for(int i=x;i*i<=y;++i)
#define GD(x,y) for(int i=x;i*i>=y;--i)
#define adde(x,y) z[x].eb(y);
#define Adde(x,y) z[x].eb(y),z[y].eb(x);
#define addew(x,y,w) z[x].eb(y,w)
#define Addew(x,y,w) z[x].eb(y,w),z[y].eb(x,w)
#define FIMX(X) memset(X,0x3f,sizeof X)
#define FIMI(X) memset(X,-0x3f,sizeof X)
#define FI0(X) memset(X,0,sizeof X)
#define FIN(X) memset(X,-1,sizeof X)
#define rng(X) X.begin(),X.end()
#define PII pair<int,int>
#define PDD pair<double,double>
#define PIII tuple<int,int,int>
#define VI vector<int>
#define VII vector<PII>
#define VID vector<pair<int,double>>
#define VDD vector<PDD>
using namespace std;
const int N=600100;
int a[N],b[N];
#if 0
struct Range{
    int l,r,v;
} ;
int R[N],L[N];
//R[i]: i zui you bian de yi ge b shu zu bu shi 1 de wei zhi de zuo bian yi ge wei zhi 
namespace t1{

struct qwq{
    int l,r,mx,tag;
    void init(int p){
        l=r=p;
        mx=L[p];
        tag=-1;
    }
    void yhb(int v){
        mx=(r-l+1)*v;
        tag=v;
    }
}z[N<<2];
qwq operator+(const qwq&l,const qwq&r){
    return {l.l,r.r,l.mx+r.mx,-1ll};
}
void build(int l,int r,int rt){
    if(l==r)
        return z[rt].init(l);
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
void pushyhb(int rt){
    if(z[rt].tag!=-1){
        z[rt<<1].yhb(z[rt].tag);
        z[rt<<1|1].yhb(z[rt].tag);
        z[rt].tag=-1;
    }
}
void modify1(int l,int r,int rt,int ll,int rr,int v){
    if(ll<=l&&r<=rr)
        return z[rt].yhb(v);
    int mid=l+r>>1;
    pushyhb(rt);
    if(ll<=mid)
        modify1(l,mid,rt<<1,ll,rr,v);
    if(mid<rr)
        modify1(mid+1,r,rt<<1|1,ll,rr,v);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
int query1(int l,int r,int rt,int ll,int rr){
    if(ll<=l&&r<=rr)
        return z[rt].mx;
    int mid=l+r>>1;
    pushyhb(rt);
    if(ll<=mid&&mid<rr)
        return query1(l,mid,rt<<1,ll,rr)+query1(mid+1,r,rt<<1|1,ll,rr);
    if(mid<rr)
        return query1(mid+1,r,rt<<1|1,ll,rr);
    return query1(l,mid,rt<<1,ll,rr);
}
}
namespace t2{

struct qwq{
    int l,r,mx,tag;
    void init(int p){
        l=r=p;
        mx=R[p];
        tag=-1;
    }
    void yhb(int v){
        mx=(r-l+1)*v;
        tag=v;
    }
}z[N<<2];
qwq operator+(const qwq&l,const qwq&r){
    return {l.l,r.r,l.mx+r.mx,-1ll};
}
void build(int l,int r,int rt){
    if(l==r)
        return z[rt].init(l);
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
void pushyhb(int rt){
    if(z[rt].tag!=-1){
        z[rt<<1].yhb(z[rt].tag);
        z[rt<<1|1].yhb(z[rt].tag);
        z[rt].tag=-1;
    }
}
void modify1(int l,int r,int rt,int ll,int rr,int v){
    if(ll<=l&&r<=rr)
        return z[rt].yhb(v);
    int mid=l+r>>1;
    pushyhb(rt);
    if(ll<=mid)
        modify1(l,mid,rt<<1,ll,rr,v);
    if(mid<rr)
        modify1(mid+1,r,rt<<1|1,ll,rr,v);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
int query1(int l,int r,int rt,int ll,int rr){
    if(ll<=l&&r<=rr)
        return z[rt].mx;
    int mid=l+r>>1;
    pushyhb(rt);
    if(ll<=mid&&mid<rr)
        return query1(l,mid,rt<<1,ll,rr)+query1(mid+1,r,rt<<1|1,ll,rr);
    if(mid<rr)
        return query1(mid+1,r,rt<<1|1,ll,rr);
    return query1(l,mid,rt<<1,ll,rr);
}
}
namespace t3{

struct qwq{
    int l,r,mx,tag;
    void init(int p){
        l=r=p;
        mx=a[p];
        tag=-1;
    }
    void yhb(int v){
        mx=(r-l+1)*v;
        tag=v;
    }
}z[N<<2];
qwq operator+(const qwq&l,const qwq&r){
    return {l.l,r.r,l.mx+r.mx,-1ll};
}
void build(int l,int r,int rt){
    if(l==r)
        return z[rt].init(l);
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
void pushyhb(int rt){
    if(z[rt].tag!=-1){
        z[rt<<1].yhb(z[rt].tag);
        z[rt<<1|1].yhb(z[rt].tag);
        z[rt].tag=-1;
    }
}
void modify1(int l,int r,int rt,int ll,int rr,int v){
    if(ll<=l&&r<=rr)
        return z[rt].yhb(v);
    int mid=l+r>>1;
    pushyhb(rt);
    if(ll<=mid)
        modify1(l,mid,rt<<1,ll,rr,v);
    if(mid<rr)
        modify1(mid+1,r,rt<<1|1,ll,rr,v);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
int query1(int l,int r,int rt,int ll,int rr){
    if(ll<=l&&r<=rr)
        return z[rt].mx;
    int mid=l+r>>1;
    pushyhb(rt);
    if(ll<=mid&&mid<rr)
        return query1(l,mid,rt<<1,ll,rr)+query1(mid+1,r,rt<<1|1,ll,rr);
    if(mid<rr)
        return query1(mid+1,r,rt<<1|1,ll,rr);
    return query1(l,mid,rt<<1,ll,rr);
}
}
//t1 维护 L
//t2 维护 R
//t3 维护 a
//b 不需要维护
#endif
struct qwq{
    int l,r,cnt,ch,mx;
    void init(int p){
        l=r=p;
        mx=a[p];
        ch=b[p];
        if(b[p]!=1)
            cnt=1;
        else
            cnt=0;
    }
}z[N<<2];
qwq operator+(const qwq&l,const qwq&r){
    return {l.l,r.r,l.cnt+r.cnt,0ll,l.mx+r.mx};
}
void build(int l,int r,int rt){
    if(l==r)
        return z[rt].init(l);
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
void modify1(int l,int r,int rt,int p,int v){
    if(l==r){
        z[rt].mx=v;
        return;
    }
    int mid=l+r>>1;
    if(p<=mid)
        modify1(l,mid,rt<<1,p,v);
    else
        modify1(mid+1,r,rt<<1|1,p,v);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
void modify2(int l,int r,int rt,int p,int x){
    if(l==r){
        z[rt].ch=x;
        if(x!=1)z[rt].cnt=1;
        else z[rt].cnt=0;
        return;
    }
    int mid=l+r>>1;
    if(p<=mid)
        modify2(l,mid,rt<<1,p,x);
    else
        modify2(mid+1,r,rt<<1|1,p,x);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
PII query1(int l,int r,int rt,int ll,int rr){
    if(l==r){
        if(z[rt].cnt)return {l,rt};
        else return {0,0};
    }
    int mid=l+r>>1;
    if(ll<=l&&r<=rr){
        if(z[rt<<1].cnt)
            return query1(l,mid,rt<<1,ll,rr);
        else
            return query1(mid+1,r,rt<<1|1,ll,rr);
    }else{
        PII z={0,0};
        if(ll<=mid)
            z=query1(l,mid,rt<<1,ll,rr);
        if(mid<rr&&!z.first) z=query1(mid+1,r,rt<<1|1,ll,rr);
        return z;
    }
}
int query2(int l,int r,int rt,int ll,int rr){
    if(ll<=l&&r<=rr)
        return z[rt].mx;
    int mid=l+r>>1;
    if(ll<=mid&&mid<rr)
        return query2(l,mid,rt<<1,ll,rr)+query2(mid+1,r,rt<<1|1,ll,rr);
    if(ll<=mid)
        return query2(l,mid,rt<<1,ll,rr);
    return query2(mid+1,r,rt<<1|1,ll,rr);
}
#ifndef THIS_IS_JIAOHUTI
signed main(){
    // freopen("count_in","r",stdin);freopen("count.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    F(i,1,n)cin>>a[i];
    F(i,1,n)cin>>b[i];
    build(1,n,1);int q;cin>>q;
    while(q--){
        int o;cin>>o;
        if(o==1){
            int l,r;cin>>l>>r;
            modify1(1,n,1,l,r);
        }else if(o==2){
            int l,r;cin>>l>>r;
            modify2(1,n,1,l,r);
        }else{
            int l,r;cin>>l>>r;
            int mx=0;
            while(l<=r){
                auto T=query1(1,n,1,l,r);
                if(!T.first)break;
                // cout<<"qwq "<<T.first<<' '<<T.second<<'\n';
                if(T.first!=l)mx+=query2(1,n,1,l,T.first-1);
                else;
                mx=max(mx*z[T.second].ch,mx+z[T.second].mx);
                l=T.first+1;
            }
            if(l<=r)
                mx+=query2(1,n,1,l,r);
            cout<<mx<<'\n';
        }
    }
}

#else

#define NO_MAIN
void no_main() {
    puts("pwp");
}

#endif

标签：rt,AtCoder,Beginner,int,ll,cin,eb,补题,define
From： https://www.cnblogs.com/yhbqwq/p/18378344

相关文章

  • AtCoder Beginner Contest 049
    A-UOIAUAI#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); charc; cin>>c; if(c=='a'||c=='e'||c=='i'||c==�......
  • AtCoder Beginner Contest 367 A ~ F（无D题）题解
    AtCoderBeginnerContest367A~F（̸\notD）几天前就已经vp过了，但是忘写题解了今天才想起来痛，早知道这么简单，我就不在家里摆烂了A.ShoutEveryday罚了好几发，我打比......
  • AtCoder Beginner Contest 358
    C-Popcorn思路：从集合S中选出非空子集，使得子集中糖果口味有M种。观察到集合S中的元素数量n<=10。因此，总共的子集数为C<=2^10-1，考虑枚举所有的子集。代码：#include<bits/stdc++.h>#defineintlonglong#defineullunsignedlonglong#defineiosios::sync_with_s......
  • AtCoder Beginner Contest 050
    基本上独立做出来了。A-AdditionandSubtractionEasy模拟。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); intA,B; charC; cin>>A>>C>>B; if(C==......
  • AtCoder Beginner Contest 中的小思维题
    078Dhttps://atcoder.jp/contests/abc078/tasks/arc085_b问题陈述我们有一副由\(N\)张牌组成的扑克牌。每张牌上都写着一个整数。从最上面开始的第\(i\)张牌上的整数是\(a_i\)。两个人X和Y将用这副扑克牌玩一个游戏。最初，X手中有一张写有\(Z\)的牌，Y手中有一张......
  • AtCoder Beginner Contest 048
    A-AtCoder***Contest先输出首字母，然后遍历字符串，遇到空格就输出后面的第一个字符。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); strings; getline(cin,s); cout<<s[0];......
  • Atcoder Beginner Contest 365
    AtcoderBeginnerContest365A题意输入年份，输出该年份天数。思路略B题意输入一个序列，输出该序列次大值的位置。思路略C题意给定\(N\)，序列\(A\)和\(M\)。求满足下条件的\(x\)最大值。\[\sum_{i=1}^{n}\min(x,A_i)\leM\]思路式子左边有单调性，二分\(x\)......
  • AtCoder Beginner Contest 047
    A-FightingoverCandies简单排序。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); vector<int>a(3); cin>>a[0]>>a[1]>>a[2]; sort(a.begi......
  • AtCoder Beginner Contest 367
    A-ShoutEveryday思路：水题一道，模拟即可。B-Cut.0思路：直接cin和cout即可，c++输入输出性质。C-EnumerateSequences思路：注意到数据范围很小，因此考虑到搜素所有的序列，然后判断是否合法。D-Pedometer思路：观察到是环上问题，先断环为链，观察题目，可以发现，对于s,它的终......
  • AtCoder Beginner Contest 046
    A-AtCoDeerandPaintCans#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); set<int>s; for(inti=0;i<3;i++){ intx; cin>>x; s.inser......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99