[Educational Codeforces Round#22]

来自FallDream的博客，未经允许，请勿转载，谢谢。

晚上去clj博客逛来逛去很开心，突然同学提醒了一下，发现cf已经开始40分钟了，慌的一B，从B题开始写，写完了B到E最后收掉了A，结果太着急B题忘记写一个等号挂掉了。。。。D题瞎dp也挂了很难受。F题还剩5分钟的时候想出来了，如果没迟应该能写完。

你要做n道题每道题要花费时间ti，有m个可以提交的时间段，你在同一时刻可以交很多代码并且不耗时间，求最早什么时候可以把代码全部交完。

发现只要管最后一道题啥时候交就行了，扫一遍区间。

#include<iostream>

#include<cstdio>

#define MN 1000

#define INF 1000000000

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int n,m,mn=INF,tot=;

int main()

{

    n=read();

    for(int i=;i<=n;++i) tot+=read();

    m=read();

    for(int i=;i<=m;++i)

    {

        int l=read(),r=read();

        if(r>=tot) mn=min(mn,max(,l-tot));

    }

    printf("%d",mn==INF?-:mn+tot);

    return ;

}

B.给定一个区间[l,r]和x,y，定义特殊数字是可以被表示成x^a+y^b(a,b是非负整数）的数，求[l,r]中最长的连续的一段数字，满足这段数字区间内全是非特殊的数字。

l,r<=10^18 2<=x,y<=10^19

显然x^a和y^b只有log种，都拿出来排个序就行了。

#include<iostream>

#include<cstdio>

#include<algorithm>

#define ll long long

#define MN (ll)1e18

using namespace std;

ll s[],s2[],mx=,a[];int top1=,top2=,top=;

int main()

{

    ll x,y,l,r;

    scanf("%lld%lld%lld%lld",&x,&y,&l,&r);

    s[++top1]=;s2[++top2]=;

    for(ll i=x;;i*=x)

    {

        s[++top1]=i;

        if(i>MN/x)break;

    }

    for(ll i=y;;i*=y)

    {

        s2[++top2]=i;

        if(i>MN/y)break;

    }

    for(int i=;i<=top1;++i)

        for(int j=;j<=top2;++j)

            if(s[i]+s2[j]>=l&&s[i]+s2[j]<=r)

                a[++top]=s[i]+s2[j];

    if(!top) return *printf("%lld",r-l+);

    sort(a+,a+top+);

    mx=max(mx,a[]-l);

    mx=max(mx,r-a[top]);

    for(int i=;i<=top;++i)

        mx=max(mx,a[i]-a[i-]-);

    cout<<mx;

    return ;

}

给定一棵树，一个人在x(x!=1)号点，另一个在1号点，每次行动每个人可以移动到一个相邻节点或者不动，第一个人希望回合最多，第二个人希望最少，求最多有多少个回合。

n<=2*10^5

枚举目标点，一个点可行当且仅当x到它和x的lca的距离小于1号点到lca的距离。

#include<iostream>

#include<cstdio>

#include<algorithm>

#define MD 18

#define MN 200000

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

pair<int,int> p[MN+];

int cnt=,head[MN+],fa[MD+][MN+],dep[MN+],f[MN+],n;

struct edge{int to,next;}e[MN*+];

inline void ins(int f,int t)

{

    e[++cnt]=(edge){t,head[f]};head[f]=cnt;

    e[++cnt]=(edge){f,head[t]};head[t]=cnt;

}

bool cmp(pair<int,int> x,pair<int,int> y){return x.first>y.first;}

void Dfs(int x,int f)

{

    fa[][x]=f;p[x]=make_pair(dep[x],x);

    for(int i=head[x];i;i=e[i].next)

        if(e[i].to!=f)

            dep[e[i].to]=dep[x]+,Dfs(e[i].to,x);

}

inline int lca(int x,int y)

{

    if(dep[x]<dep[y]) swap(x,y);

    for(int k=dep[x]-dep[y],j=;k;k>>=,++j)

        if(k&)x=fa[j][x];

    if(x==y) return x;

    for(int i=MD;~i;--i)

        if(fa[i][x]!=fa[i][y])

            x=fa[i][x],y=fa[i][y];

    return fa[][x];

}

int main()

{

    n=read();int x=read();

    for(int i=;i<n;++i) ins(read(),read());

    Dfs(,);

    for(int i=;i<=MD;++i)

        for(int j=;j<=n;++j)

            fa[i][j]=fa[i-][fa[i-][j]];

    sort(p+,p+n+,cmp);

    for(int i=;i<=n;++i)

    {

        int z=lca(x,p[i].second);

        if(dep[x]-dep[z]>=dep[z]) continue;

        return *printf("%d\n",p[i].first*);

    }

    return ;

}

给定一个长度为n(<=5000)的序列ai，定义优秀的序列是满足相邻元素相差1或者在膜7意义下相等的序列，求这个序列的两个不相交的优秀子序列满足长度之和最大。

f[i][j]表示两个序列结尾分别在i，j的最长长度

枚举i，j，对于每个i，开两个数组分别表示最后一个数是k和最后一个数膜7等于k的最长长度，然后分别转移。

#include<iostream>

#include<cstdio>

#include<cstring>

#define MN 5000

using namespace std;

inline int read()

{

    int x = ,f = ; char ch = getchar();

    while(ch < '' || ch > ''){if(ch == '-') f = ;ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return f?x:-x;

}

int n,a[MN+],f[MN+],F[],D[MN+][MN+],ans=,ha[],cnt=;

inline void R(int&x,int y){y>x?x=y:;}

int main()

{

    n=read();

    for(int i=;i<=n;++i)!ha[a[i]=read()]?ha[a[i]]=++cnt:;

    for(int i=;i<=n;++i)

    {

        memset(F,,sizeof(F));

        memset(f,,sizeof(f));

        int Mx=D[i][];

        for(int j=;j<i;++j)

            R(F[a[j]%],D[i][j]),

            R(f[ha[a[j]]],D[i][j]);

        for(int j=i+;j<=n;++j)

        {

            R(D[i][j],Mx+);

            R(D[i][j],max(f[ha[a[j]]],F[a[j]%])+);

            if(ha[a[j]-]) R(D[i][j],f[ha[a[j]-]]+);

            if(ha[a[j]+]) R(D[i][j],f[ha[a[j]+]]+);

            R(F[a[j]%],D[i][j]);R(f[ha[a[j]]],D[i][j]);

            R(D[j][i],D[i][j]);R(ans,D[i][j]);

        }

    }

    cout<<ans;

    return ;

}

E. Army Creation

给定一个长度为n(<=100000)的序列ai,每次询问一段区间，满足每个数字出现次数不超过k(预先给定)次的情况下最多能保留几个数字。

从前往后扫一遍，找到每个数字前面的第k个相同的数字的位置pos，右区间>=i且左区间<=pos的时候答案减1，可持久化线段树维护即可。

复杂度nlogn

#include<iostream>

#include<cstdio>

#include<vector>

#define MN 100000

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

vector<int> v[MN+];

int n,k,num[MN+],rt[MN+],cnt=,last=,a[MN+];

struct Tree{int l,r,x;}T[];

void Modify(int x,int nx,int k)

{

    int l=,r=n,mid;T[nx].x=T[x].x+;

    while(l<r)

    {

        mid=l+r>>;

        if(k<=mid)T[nx].r=T[x].r,T[nx].l=++cnt,x=T[x].l,nx=T[nx].l,r=mid;

        else T[nx].l=T[x].l,T[nx].r=++cnt,x=T[x].r,nx=T[nx].r,l=mid+;

        T[nx].x=T[x].x+;

    }

}

int Query(int x,int k)

{

    int sum=,l=,r=n,mid;

    while(l<r)

    {

        mid=l+r>>;

        if(k<=mid) sum+=T[T[x].r].x,x=T[x].l,r=mid;

        else x=T[x].r,l=mid+;

    }

    return sum+T[x].x;

}

int main()

{

    n=read();k=read();

    for(int i=;i<=n;++i)

        v[a[i]=read()].push_back(i);

    for(int i=;i<=n;++i)

        if(++num[a[i]]>k)

            Modify(rt[i-],rt[i]=++cnt,v[a[i]][num[a[i]]-k-]);

        else rt[i]=rt[i-];

    for(int q=read();q;--q)

    {

        int l=(read()+last)%n+,r=(read()+last)%n+;

        if(l>r) swap(l,r);

        printf("%d\n",last=(r-l+)-Query(rt[r],l));

    }

    return ;

}

给你n个点，支持删边，加边，询问是否是二分图。

n,q<=10^5

考虑线段树分治避免删除操作，然后带权并差集+启发式合并维护答案即可。

复杂度nlog^2n

#include<iostream>

#include<cstdio>

#include<map>

#include<vector>

#define pa pair<int,int>

#define mp(x,y) make_pair(x,y)

#define MN 100000

using namespace std;

inline int read()

{

    int x = ,f = ; char ch = getchar();

    while(ch < '' || ch > ''){if(ch == '-') f = ;ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return f?x:-x;

}

bool Ans[MN+];

map<long long,int> mp;

int n,q,cnt=,fa[MN+],W[MN+],val[MN+],size[MN+],A[MN+],B[MN+];

struct Tree{int l,r;vector<pa> x;vector<int> v;}T[MN*+];

void Ins(int x,int l,int r,pa v)

{

    if(T[x].l==l&&T[x].r==r) {T[x].x.push_back(v);return;}

    int mid=T[x].l+T[x].r>>;

    if(r<=mid) Ins(x<<,l,r,v);

    else if(l>mid) Ins(x<<|,l,r,v);

    else Ins(x<<,l,mid,v),Ins(x<<|,mid+,r,v);

}

void build(int x,int l,int r)

{

    if((T[x].l=l)==(T[x].r=r))return;

    int mid=l+r>>;

    build(x<<,l,mid);

    build(x<<|,mid+,r);

}

inline int getfa(int x)

{

    if(fa[x]==x) return x;

    int F=getfa(fa[x]);

    return val[x]=val[fa[x]]^W[x],F;

}

void Solve(int k,bool flag)

{

    for(int i=;i<T[k].x.size();++i)

    {

        int x=T[k].x[i].first,y=T[k].x[i].second;

        int f1=getfa(x),f2=getfa(y);

        if(size[f1]>size[f2]) swap(f1,f2);

        if(f1==f2) flag|=(val[x]==val[y]);

        else

        {

            size[f2]+=size[f1];fa[f1]=f2;

            W[f1]=val[x]==val[y];

            T[k].v.push_back(f1);

        }

    }

    if(T[k].l==T[k].r) Ans[T[k].l]=flag;

    else Solve(k<<,flag),Solve(k<<|,flag);

    for(int i=;i<T[k].v.size();++i)

    {

        int x=T[k].v[i];fa[x]=x;

        size[fa[x]]-=size[x];W[x]=val[x]=;

    }

}

int main()

{

    n=read();q=read();build(,,q);

    for(int i=;i<=n;++i) fa[i]=i,size[i]=,val[i]=W[i]=;

    for(int i=;i<=q;++i)

    {

        int x=read(),y=read();

        if(mp[1LL*x*MN+y])

        {

            Ins(,mp[1LL*x*MN+y],i-,mp(x,y));

            mp[1LL*x*MN+y]=;

        }

        else mp[1LL*x*MN+y]=i;

        A[i]=x;B[i]=y;

    }

    for(int i=;i<=q;++i)

    {

        int x=mp[1LL*A[i]*MN+B[i]];

        if(x) mp[1LL*A[i]*MN+B[i]]=,Ins(,x,q,mp(A[i],B[i]));

    }

    Solve(,);

    for(int i=;i<=q;++i) puts(Ans[i]?"NO":"YES");

    return ;

}

巴特西

[Educational Codeforces Round#22]

最新文章

热门文章