首页 > 其他分享 >AtCoder Beginner Contest 369 补题记录(A~G)

AtCoder Beginner Contest 369 补题记录(A~G)

时间:2024-08-31 23:04:20浏览次数:12  
标签:AtCoder const Beginner bridge int ed cin 补题 mp

A

const int N=1000100;
int a[N];
signed main(){
    int x,y;cin>>x>>y;
    if(x==y)cout<<"1\n";
    else if(x%2==y%2)cout<<"3\n";
    else cout<<"2\n";
}

B

const int N=1000100;
int a[N];
signed main(){
    int n;cin>>n;
    int cnt=0;
    VI l,r;
    F(i,1,n){
        int x;char o;cin>>x>>o;
        if(o=='L')l.eb(x);else r.eb(x);
    }
    F(i,1,(int)l.size()-1)cnt+=abs(l[i]-l[i-1]);
    F(i,1,(int)r.size()-1)cnt+=abs(r[i]-r[i-1]);
    cout<<cnt<<'\n';
}

C

发现满足条件的合法连续子序列 \((L,R)\) 必然可以用 \(K\) 个二元组 \((A_1,B_1)\),\((A_2,B_2)\),\(\ldots\),\((A_k,B_k)\) 来表示,其中任意一个合法的连续子序列 \((L,R)\) 均满足 \(\exists\ i\in[1,k]\cap\textbf{N}_+\),\(A_i\le L\le R\le B_i\)。然后还可以发现 \(\forall\ i,j\in [1,K],\ i<j\),\(B_i-A_j\ {\color{red}{=}}\ 1\)。因此答案即为 \(-K+1+\sum\limits_{i=1}^K\frac{(B_i-A_i+1)(B_i-A_i)}{2}\),双指针滑动找出所有满足条件的 \((A_i,B_i)\) 二元组,时间复杂度为 \(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;
    int l=1,r=1;
    while(l<=n&&r<=n){
        while(r<=n&&(r-l<=1||a[r]-a[r-1]==a[r-1]-a[r-2]))++r;
        --r;
        int len=r-l+1;cnt+=len*(len+1)/2;
        --cnt;
        l=r;
        if(r==n)break;
    }
    cout<<cnt+1<<'\n';
}

D

设 \(f_{i,j}\) 表示当前前 \(i\) 只怪物击败了 \(j\) 只怪物最大的贡献,可以发现 \(j\) 对答案的影响只和 \(j\bmod 2\) 的值有关系,因此设 \(f_{i,0/1}\) 表示当前前 \(i\) 只怪物击败了 \(j\) 只怪物的最大贡献,显然有:

  • \(f_{i,0}=\max(f_{i-1,0},f_{i-1,1}+2a_i)\)。
  • \(f_{i,1}=\max(f_{i-1,1},f_{i-1,0}+a_i)\)。

初始条件为 \(f_{0,0}=0\),\(f_{0,1}=-\infin\)。

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

const int N=1000100;
int a[N];
int f[N][2];
//f[i][j] 表示当前前 i 只怪物击败了 0/1 奇数/偶数怪物
signed main(){
    int n;cin>>n;
    F(i,1,n)cin>>a[i];
    f[0][1]=-1e18;
    F(i,1,n){
        f[i][0]=f[i-1][0],f[i][1]=f[i-1][1];
        f[i][0]=max({f[i][0],f[i-1][1]+a[i]+a[i]});
        f[i][1]=max({f[i][1],f[i-1][0]+a[i]});
    }
    cout<<max({f[n][0],f[n][1]})<<'\n';
}

E

考虑先跑 \(n\) 遍 dijkstra 求出两两点之间的最短路,然后对于 \(Q\) 组询问,考虑枚举每一个桥梁的顺序,然后枚举每一个桥梁的走向,暴力计算对答案的贡献即可。时间复杂度为 \(O(能过)\)。

const int N=1000100;
VII z[N];
struct qwq{
    int u,v,w;
};
struct no{
    int u,d;
    bool operator<(const no&r)const{
        return d>r.d;
    }
};
qwq ed[N];
int mp[2010][2010];
void dijk(int s){
    priority_queue<no>q;
    q.push({s,0});mp[s][s]=0;
    while(q.size()){
        auto t=q.top();q.pop();
        if(mp[s][t.u]>=t.d)
            for(auto &[g,w]:z[t.u])
                if(mp[s][g]>mp[s][t.u]+w)q.push({g,mp[s][g]=mp[s][t.u]+w});
    }
}
signed main(){
    int n,m;cin>>n>>m;
    F(i,1,m){
        int u,v,w;cin>>u>>v>>w;
        ed[i]={u,v,w};
        addew(u,v,w);
        addew(v,u,w);
    }
    memset(mp,1,sizeof mp);
    F(i,1,2005)
        dijk(i);
    int q;cin>>q;
    while(q--){
        int k;cin>>k;
        int x[10];F(i,0,k-1)cin>>x[i];
        sort(x,x+k);
        int mi=1e18;
        do{
            //枚举每一座桥是往哪个方向走的
            F(i,0,(1ll<<k)-1){
                int cost=0;
                //x>>i&1==1 : 选择u[i]-->v[i]
                //即 ed[x[i]].u-->x[i]+n-->ed[x[i]].v
                //x>>i&1==0 : 选择v[i]-->u[i]
                //即 ed[x[i]].v-->x[i]+n+n-->ed[x[i]].u
                VI bridge;
                F(j,0,k-1){
                    if(i>>j&1)bridge.eb(ed[x[j]].u),bridge.eb(ed[x[j]].v),cost+=ed[x[j]].w;
                    else bridge.eb(ed[x[j]].v),bridge.eb(ed[x[j]].u),cost+=ed[x[j]].w;
                }
                cost+=mp[1][bridge[0]]+mp[bridge.back()][n];
                F(i,2,(int)bridge.size()-1){
                    cost+=mp[bridge[i-1]][bridge[i]];
                    ++i;
                    if(cost>3e18)break;
                }
                mi=min(mi,cost);
            }
        }while(next_permutation(x,x+k));
        cout<<mi<<'\n';
    }
}

F

二维偏序套路的对 \(x\) 为第一关键字 \(y\) 为第二关键字均从小到大排序,则此时 \(x\) 对答案毫无贡献,只需要考虑 \(y\) 的贡献,变为 LIS 板子。因为要输出路径所以再设 \(g_i\) 表示以 \(i\) 结尾的最大答案是从 \(g_i\) 转移过来的,倒序遍历答案即可。时间复杂度为 \(O(n\log n)\) 瓶颈在于线段树维护最大值和最大值所处的位置。


const int N=600100;
PII z[N];
int f[N];
#define x first
#define y second
//可爱班花yhb天下第一可爱qwq
namespace yhb{
struct qwq{
    int l,r,mx,id;
    void init(int p){
        l=r=p;mx=id=0;
    }
}z[N<<2];
qwq operator+(const qwq&l,const qwq&r){
    qwq t;
    t.l=l.l,t.r=r.r;
    if(l.mx<=r.mx)t.mx=r.mx,t.id=r.id;
    else t.mx=l.mx,t.id=l.id;
    return t;
}
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 modify(int l,int r,int rt,int p,int v,int id){
    if(l==r){
        if(z[rt].mx<v){
            z[rt].mx=v;
            z[rt].id=id;
        }
        return;
    }
    int mid=l+r>>1;
    if(p<=mid)modify(l,mid,rt<<1,p,v,id);
    else modify(mid+1,r,rt<<1|1,p,v,id);
    z[rt]=z[rt<<1]+z[rt<<1|1];
}
qwq query(int l,int r,int rt,int ll,int rr){
    if(ll<=l&&r<=rr)
        return z[rt];
    int mid=l+r>>1;
    if(ll<=mid&&mid<rr)
        return query(l,mid,rt<<1,ll,rr)+query(mid+1,r,rt<<1|1,ll,rr);
    if(ll<=mid)
        return query(l,mid,rt<<1,ll,rr);
    return query(mid+1,r,rt<<1|1,ll,rr);
}
}
#define ro 0,200001,1
int g[N];
signed main(){
    set<PII>se;
    int n,m,k;cin>>n>>m>>k;
    F(i,1,k){
        int x,y;cin>>x>>y;
        se.insert({x,y});
        z[i]={x,y};
    }
    sort(z+1,z+k+1);
    f[0]=0;
    yhb::build(ro);
    F(i,1,k){
        f[i]=1;
        auto tk=yhb::query(ro,1,z[i].second);
        f[i]=max(f[i],tk.mx+1);
        g[i]=tk.id;
        yhb::modify(ro,z[i].second,f[i],i);
    }
    cout<<*max_element(f+1,f+k+1)<<'\n';
    VII pai;
    pai.eb(1,1);
    VII t;
    int la=-1,mx=*max_element(f+1,f+k+1);
    F(i,1,k)if(mx==f[i])la=i;
    while(la){
        t.eb(z[la]);
        la=g[la];
    }
    reverse(rng(t));
    for(auto &x:t)pai.eb(x);
    pai.eb(n,m);
    F(i,1,pai.size()-1){
        int dx=pai[i].first-pai[i-1].first;
        int dy=pai[i].second-pai[i-1].second;
        F(i,0,dx-1)cout<<"D";
        F(i,0,dy-1)cout<<"R";
    }
    cout<<'\n';
}

G

长剖板子。容易发现一定只会选不同的叶子结点才能对答案产生最大的贡献。因此暴力长剖设 \(g_i\) 表示从 \(Top_i\) 到 \(i\) 结点所有遍的权值的和,其中 \(Top_i\) 表示 \(i\) 所属长链的顶端元素编号。记录所有可能对答案产生贡献的叶子结点,把所有的叶子结点的 \(g_i\) 从大到小排序然后求一遍前缀和即可。时间复杂度为 \(O(n\log n)\),使用基数排序可以做到 \(O(n)\)。

const int N=600100;
VII z[N];
int a[N],vis[N],deg[N],son[N],val[N];
void dfs_(int u,int fa){
    for(auto &[v,w]:z[u])
        if(v!=fa){
            a[v]=w;
            dfs_(v,u);
        }
}
void dfs(int u,int fa){
    for(auto &[v,w]:z[u])
        if(v!=fa){
            dfs(v,u);
            if(val[v]>val[son[u]])son[u]=v;
        }
    val[u]=val[son[u]]+a[u];
}
int g[N];
signed main(){
    int n;cin>>n;
    F(i,1,n-1){
        int u,v,w;cin>>u>>v>>w;
        Addew(u,v,w);
        ++deg[u],++deg[v];
    }
    dfs_(1,0);
    dfs(1,0);
    VI v;
    F(i,1,n)vis[son[i]]=1;
    F(i,1,n)if(!vis[i])v.eb(val[i]);
    sort(rng(v),greater<int>());
    int s=0;
    F(i,0,n-1){
        if(i<=min(761145141413ll,(int)v.size()-1))s+=v[i];
        cout<<s*2<<'\n';
    }
}

标签:AtCoder,const,Beginner,bridge,int,ed,cin,补题,mp
From: https://www.cnblogs.com/yhbqwq/p/18390900

相关文章

  • AtCoder Beginner Contest 369 A~D
    封面原图画师かにょこAtCoderBeginnerContest369我愿称之为等差数列场A-369题意给两个数,问能和他们构成等差数列的数有多少个代码#include<bits/stdc++.h>#definemod998244353usingnamespacestd;typedeflonglongll;typedefdoubledb;type......
  • Atcoder Beginner Contest 369
    AtcoderBeginnerContest369唯一的一发罚时吃在A题,消息了。A挂一发的原因是以为\(A,B\)都是一位数,然后循环范围开了\([-10,20]\)。#include<bits/stdc++.h>usingnamespacestd;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr);// int_;cin>>_;while......
  • AtCoder Beginner Contest 053
    A-ABC/ARC#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); intx; cin>>x; if(x<1200)cout<<"ABC"; elsecout<<"ARC&q......
  • cf_补题计划_Edu_163_DE
    D.TandemRepeats?呃从复杂度来说,可以进行\(n^2\)的操作,呃因为是子串数量级也是\(n^2\),考虑是否子串之间可以相互转移,这个很类似求最长回文串(对于最长回文串我们枚举中点,向外延申即可,因为对于同一个中心可以转移),而对于串联重复串,前一部分等于后一部分,我们可以考虑固定长......
  • Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)F - Dividing
    https://atcoder.jp/contests/abc368/tasks/abc368_f#include<bits/stdc++.h>#definexfirst#defineysecondusingnamespacestd;typedeflonglongll;typedefpair<ll,char>pii;constintN=2e5+10,inf=1e9;lln,m,k;intb[N],sg[N],a[N];vector......
  • Atcoder [AGC006D] Median Pyramid Hard 题解 [ 紫 ] [ 二分 ] [ adhoc ]
    MedianPyramidHard:二分trick加上性质观察题。trick我们可以二分值域,然后把大于等于它的数标记成\(1\),其他标记为\(0\)(有些题需要标记成\(-1\)),然后根据这个来check方案是否可行,这通常通过判断某个数是否是\(1\)来实现。本质上其实就是check大于等于它的数能否成为......
  • AtCoder Beginner Contest 368
    A-Cut题意签到题思路代码#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,k;scanf("%d%d",&n,&k);vector<int>v(n);for(inti=0;i<n;i++){scanf("%d",&v[i......
  • SDKD 2024 Summer Training Contest E2补题
    SDKD2024SummerTrainingContestE2A-PaperWatering题意对x进行至多k次操作(平方或开方后向下取整),求可以得到多少不同的数。思路平方完一定不同,且平方完后一定能开方出整数,所以只用额外考虑开方后平方的情况。若开方再平方与原来不同,则答案加上当前变化数的次数,直到变......
  • AtCoder Beginner Contest 052
    A-TwoRectangles#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); intA,B,C,D; cin>>A>>B>>C>>D; cout<<max(A*B,C*D); ......
  • AtCoder Beginner Contest 051
    A-Haiku直接模拟。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); strings; cin>>s; stringa,b,c; a=s.substr(0,5); b=s.substr(6,7); c=s.substr(......