Educational Codeforces Round 23 补题小结

昨晚听说有教做人场，去补了下玩。

大概我的水平能做个5/6的样子？

（不会二进制Trie啊，我真菜）

傻逼题。大概可以看成向量加法，判断下就好了。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int x1,x2,yy1,y2,x,y;

int main(){

    scanf("%d%d%d%d%d%d",&x1,&yy1,&x2,&y2,&x,&y);

    int dx=abs(x1-x2),dy=abs(yy1-y2);

    if((abs(dx/x-dy/y)%==)&&(dx%x==)&&(dy%y==))puts("YES");

    else puts("NO");

}

找符合要求的最小三元组乘积出现次数。

sort一下随便搞搞就行了。

#include<bits/stdc++.h>

#define N 100010

typedef long long ll;

using namespace std;

ll a[N];int n;ll minv;

inline ll read(){

    ll f=,x=;char ch;

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

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

    return f*x;

}

int main(){

    n=read();

    for(int i=;i<=n;i++)a[i]=read();

    sort(a+,a+n+);ll cnt=;

    for(int i=;i<=n;i++)if(a[i]==a[])cnt++;

    if(a[]==a[])cout<<(cnt-)*(cnt-)*cnt/<<endl;

    else if(a[]==a[])cout<<(cnt-)*cnt/<<endl;

    else cout<<cnt<<endl;

}

第一反应数位dp，反正也可做。

数位记忆化搜索大概也行的样子。

但是可以显然地证明一个性质：x + 1 - sumd(x + 1) ≥ x - sumd(x)

这就满足了一个单调性，按照出题人的想法是可以二分答案。

但是可以直接枚举最大的范围嘛！干嘛非要写个二分答案

而且这么写跑得飞快。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,s;

inline bool check(ll x){

    ll res=x;

    while(res){x-=res%;res/=;}

    return x>=s;

}

int main(){

    cin>>n>>s;ll maxv=min(n,s+),sum=;

    for(ll i=s;i<=maxv;i++)if(check(i))++sum;

    cout<<n-maxv+sum<<endl;

}

用单调栈维护一个"一个数向左向右最大可以做max与min能管的距离"

好久不上语文课了表达能力=0

实在不行看官方题解吧。

#include<bits/stdc++.h>

#define N 1000005

#define inf 1000000007

typedef long long ll;

using namespace std;

int n,a[N];

ll ans1,ans2,ans;

stack<int>s1,s2;

inline int read(){

    int f=,x=;char ch;

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

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

    return f*x;

}

int main(){

    n=read();

    s1.push();s2.push();

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

        a[i]=read();a[]=;

        while(s1.top()&&a[i]<a[s1.top()]){

            int top=s1.top();s1.pop();

            ans1-=1LL*a[top]*(top-s1.top());

        }

        ans1+=1LL*a[i]*(i-s1.top());s1.push(i);

        a[]=inf;

        while(s2.top()&&a[i]>a[s2.top()]){

            int top=s2.top();s2.pop();

            ans2-=1LL*a[top]*(top-s2.top());

        }

        ans2+=1LL*a[i]*(i-s2.top());s2.push(i);

        ans+=ans2-ans1;

    }

    cout<<ans<<endl;

}

我太菜了，以前居然没见过这种在二进制字典树上的贪心……

建一个二进制的字典树，然后贪心一下看能不能搞成1就行了。

具体的我日后可能得写个blog介绍下Trie的贪心。

#include<bits/stdc++.h>

#define N 3000005

using namespace std;

int size[N],ch[N][],n,cnt,a,b,type;

inline void ins(int x,int add){

    int now=;

    for(int i=;i>=;i--){

        bool v=((x>>i)&);

        if(!ch[now][v])ch[now][v]=++cnt;

        now=ch[now][v];

        size[now]+=add;

    }

}

inline void query(int x,int y){

    int ans=,now=,val=;

    for(int i=;i>=&&now;i--){

        bool xbit=((x>>i)&),ybit=((y>>i)&);

        val+=val;

        if(ybit){

            ans+=size[ch[now][xbit]];now=ch[now][!xbit];

            val+=!xbit;

        }

        else{now=ch[now][xbit];val+=xbit;}

    }

    printf("%d\n",ans);

}

inline int read(){

    int f=,x=;char ch;

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

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

    return f*x;

}

int main(){

    cnt=;n=read();

    while(n--){

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

        if(opt==)ins(x,);

        if(opt==)ins(x,-);

        if(opt==){

            int y=read();

            query(x,y);

        }

    }

}

看到mex突然激动，感觉可能是个DS题。

果然是。

第一反应主席树求一下就好，后来想下，主席树也是没有必要的。

直接线段树维护就行。

类似于取反，求最左节点的操作。

值域过大可以选择动态开点或者离散化。

我就写了个离散化……

类似的分解的操作的题bzoj都有，如果一下子看不懂这篇

可以QQ找我问几个原题。

#include<bits/stdc++.h>

#define N 300005

#define lson (o<<1)

#define rson (o<<1|1)

using namespace std;

typedef long long ll;

ll a[N];

struct Query{ll l,r,opt;}Q[N];

int n,len;

struct Segment_Tree{

    int sumv[N<<],addv[N<<],rev[N<<];

    inline void pushup(int o){sumv[o]=sumv[lson]+sumv[rson];}

    inline void puttag(int o,int l,int r,int add,int re){

        if(re){

            if(addv[o]==-)rev[o]^=,sumv[o]=r-l+-sumv[o];

            else addv[o]^=,sumv[o]=r-l+-sumv[o];

        }

        else if(add!=-){

            rev[o]=;addv[o]=add;sumv[o]=(r-l+)*add;

        }

    }

    inline void pushdown(int o,int l,int r){

        int mid=(l+r)>>;

        puttag(lson,l,mid,addv[o],rev[o]);

        puttag(rson,mid+,r,addv[o],rev[o]);

        addv[o]=-;rev[o]=;

    }

    void build(int o,int l,int r){

        if(l==r){addv[o]=-;return;}

        int mid=(l+r)>>;

        build(lson,l,mid);build(rson,mid+,r);

        addv[o]=-;

    }

    int querymex(int o,int l,int r){

        if(l==r)return l;

        int mid=(l+r)>>;pushdown(o,l,r);

        if(sumv[lson]<mid-l+)return querymex(lson,l,mid);

        else return querymex(rson,mid+,r);

    }

    void change(int o,int l,int r,int ql,int qr,int add,int re){;

        if(ql<=l&&r<=qr){puttag(o,l,r,add,re);return;}

        int mid=(l+r)>>;pushdown(o,l,r);

        if(ql<=mid)change(lson,l,mid,ql,qr,add,re);

        if(qr>mid)change(rson,mid+,r,ql,qr,add,re);

        pushup(o);

    }

}T;

inline ll read(){

    ll f=,x=;char ch;

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

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

    return f*x;

}

int main(){

    n=read();

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

        Q[i].opt=read();Q[i].l=read();Q[i].r=read();

    }

    a[]=;

    for(int i=;i<=n;i++)a[*i-]=Q[i].l,a[*i]=Q[i].r,a[*i+]=Q[i].r+;

    sort(a+,a+n*+);

    len=;

    for(int i=;i<=*n+;++i)if(a[i]!=a[i-]) a[++len]=a[i];

    T.build(,,len);

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

        int x=lower_bound(a+,a+len+,Q[i].l)-a,y=lower_bound(a+,a+len+,Q[i].r)-a;

        if(Q[i].opt==)T.change(,,len,x,y,,);

        if(Q[i].opt==)T.change(,,len,x,y,,);

        if(Q[i].opt==)T.change(,,len,x,y,-,);

        printf("%lld\n",a[T.querymex(,,len)]);

    }

}

啊最后总结下吧。

姿势水平还不够，还得学习一个。

数据结构要学会活学活用，用现有的水平解决一些不是很常规的问题。

dp什么的思维还是不够，要学习一个。

不过这场的外国人居然出了两个DS？

但是可能外国的DS水平不如我国？这个Trie题讲道理可能在国内只有T2的难度吧。

最后一个Segment-Tree可以算奇奇怪怪的常规应用的组合。

所以还是要熟练呀~

巴特西

Educational Codeforces Round 23 补题小结

最新文章

热门文章