牛客的这场比赛感觉真心不错！！

打得还是很过瘾的。水平也比较适合。

T1：中位数：

题目描述

小N得到了一个非常神奇的序列A。这个序列长度为N，下标从1开始。A的一个子区间对应一个序列，可以由数对[l,r]表示，代表A[l], A[l + 1], ..., A[r]这段数。对于一个序列B[1], B[2], ..., B[k]，定义B的中位数如下：

1. 先对B排序。得到新的序列C。

2. 假如k是奇数，那么中位数为牛客网NOIP赛前集训营-提高组（第一场）

。假如k为偶数，中位数为牛客网NOIP赛前集训营-提高组（第一场）

。

对于A的所有的子区间，小N可以知道它们对应的中位数。现在小N想知道，所有长度>=Len的子区间中，中位数最大可以是多少。

题解

这个题一看就很套路了。

二分一个mid，然后>=mid赋值1,否则赋值-1

有>0的长度大于等于len的区间，就可以。

从左到右扫，维护一个前缀的min，然后i前缀做差判断即可。

代码

#include<iostream>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int N=+;

const int inf=0x3f3f3f3f;

int n,len;

int a[N],b[N],sum[N];

int l,r;

int ans;

int main(){

    scanf("%d%d",&n,&len);

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

        scanf("%d",&a[i]);

        r=max(r,a[i]);

    }

    l=;

    while(l<=r){

        int mid=(l+r)>>;

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

            if(a[i]>=mid) b[i]=;

            if(a[i]<mid) b[i]=-;

            sum[i]=sum[i-]+b[i];

        }

        int mi=;

        bool fl=false;

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

            if(sum[i]-mi>) {

                fl=true;break;

            }

            mi=min(mi,sum[i-len+]);

        }

        if(fl) ans=mid,l=mid+;

        else r=mid-;

    }

    printf("%d",ans);

    return ;

}

中位数

关于区间中位数什么的题目，做了几道以后，可以考虑向二分答案，然后0/1或者-1/1 赋值判断。

当然还要注意，偶数长度中位数是取哪一个。

类似的题目：

中位数、国际集训队middle；（这两道是中位数）

还有一个 [HEOI2016/TJOI2016]排序（这个题也是二分然后0/1排序）

本质上都是利用绝对大小没有用，利用相对大小的关系，牺牲一个logn的复杂度，将序列变成0/1或者-1/1的序列，可以大大简化难度，也比较容易判断。

注意边界情况等。

T2：数数字

题目描述

小N对于数字的大小一直都有两种看法。第一种看法是，使用字典序的大小（也就是我们常用的判断数字大小的方法，假如比较的数字长度不同，则在较短一个前面补齐前导0，再比较字典序），比如43<355,10<11。第二种看法是，对于一个数字牛客网NOIP赛前集训营-提高组（第一场）

，定义他的权值为

，也就是各个数位的乘积。

现在给定两个区间，[L,R]与[L1,R1]。小N现在想知道，有多少使用字典序判大小法在[L,R]之间的数字，满足其第二种定义的权值也在[L1,R1]之间。

换句话说，对于一个数x，定义f(x)为x的各个数位的乘积。对于L<=x<=R，问有多少x满足，L1<=f(x)<=R1。

100%: 0<=L,R,L1,R1 <= 10^18, L <= R, L1 <= R1

题解：

一眼数位dp了。f（x）怎么处理？

gzz讲过一个<=n的，没有L1,R1上下界。

其实一样了。

发现，最多填18位数字（R=1e18特判即可），考虑质因数分解，数位乘积最多有54个2,36个3，18个5,18个7，

循环枚举一发，最终可能的情况只有34960个，状态压缩一下。

那么就可以dp了。

f[i][34960][0/1][0/1]表示，前i位填完，f(x)是所有的情况中第j个，有没有上限，有没有填过数（处理前导零）。

前导零还是挺坑的。

一般情况，每层i内，所有的循环都是转移填过数的（最后一个是1），i层最后再转移没填过->填过

还有坑点，L，L1可能是0

那么，由于前导零的处理，填数不会填出0的。

特判一下就好了。

代码：

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=;

const int M=;

const int mod=;

typedef long long ll;

ll f[][][M][];//gun dong

ll num[M],cnt;

ll L,R,L1,R1;

ll shu[N],tot;

struct ha{

    ll val[mod+],tot;

    int id[mod+];

    int nxt[mod+],hd[mod+];

    void ins(ll x,int d){

        int cur=x%mod;

        ++tot;nxt[tot]=hd[cur];

        id[tot]=d;

        val[tot]=x;

        hd[cur]=tot;

    }

    int query(ll x){

        int cur=x%mod;

        for(int i=hd[cur];i;i=nxt[i]){

            if(val[i]==x) return id[i];

        }

        return ;

    }

}HA;

ll c2[],c3[],c5[],c7[];

ll wrk(){

    memset(f,,sizeof f);

    int tmp=;

    f[tmp][][][]=;

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

        //cout<<" iii "<<i<<" ------------------- "<<shu[i]<<endl;

        tmp^=;

        memset(f[tmp],,sizeof f[tmp]);

        for(int j=;j<=cnt;j++){

            for(int k=;k<=;k++){

                if(!f[!tmp][][j][]&&!f[!tmp][][j][]) continue;

                int to=HA.query(num[j]*k);

                if(!to) continue;

                if(k<shu[i]){

                    //if(f[!tmp][0][j][1]||f[!tmp][1][j][1]) {

                        f[tmp][][to][]+=f[!tmp][][j][]+f[!tmp][][j][];

                    //}

                }

                else if(k==shu[i]){

                    //if(f[!tmp][1][j][1]) {

                        //int to=

                    //}

                    f[tmp][][to][]+=f[!tmp][][j][];

                    f[tmp][][to][]+=f[!tmp][][j][];

                }

                else{

                    f[tmp][][to][]+=f[!tmp][][j][];

                }

            }

        }

      if(i!=tot){

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

            f[tmp][][j+][]+=f[!tmp][][][];

        }

      }

      else{

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

            if(j<shu[i]){

                f[tmp][][j+][]+=f[!tmp][][][];

            }

            else if(j==shu[i]){

                f[tmp][][j+][]+=f[!tmp][][][];

            }

            else break;

        }

      }

      f[tmp][][][]+=f[!tmp][][][];

      /*for(int j=1;j<=20;j++){

        cout<<j<<" "<<num[j]<<" : "<<f[tmp][0][j][0]<<" "<<f[tmp][0][j][1]<<" "<<f[tmp][1][j][0]<<" "<<f[tmp][1][j][1]<<endl;

      }*/

    }

    ll ret=;

    ll le=;

    while(num[le]<L1) le++;

    while(num[le]<=R1) ret+=f[tmp][][le][]+f[tmp][][le][],le++;

    return ret;

}

int main()

{

    scanf("%lld%lld%lld%lld",&L,&R,&L1,&R1);

    c2[]=;for(int i=;i<=;i++) c2[i]=c2[i-]*;

    c3[]=;for(int i=;i<=;i++) c3[i]=c3[i-]*;

    c5[]=;for(int i=;i<=;i++) c5[i]=c5[i-]*;

    c7[]=;for(int i=;i<=;i++) c7[i]=c7[i-]*;

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

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

            for(int k=;k<=;k++){

                for(int l=;l<=;l++){

                    int re=-l-k;

                    re-=((j+)/);

                    re-=((i+)/);

                    if(re>=) {

                        ++cnt;

                        ll now=c2[i]*c3[j]*c5[k]*c7[l];

                        num[cnt]=now;

                    }

                }

            }

        }

    }

    num[++cnt]=;

    sort(num+,num+cnt+);

    cnt=unique(num+,num+cnt+)-num-;

    //cout<<" Cnt "<<cnt<<endl;

    //for(int i=1;i<=40;i++) cout<<num[i]<<" ";

    //cout<<endl;

    //cout<<" las "<<num[cnt]<<endl;

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

        HA.ins(num[i],i);

    }

    ll sub=;

    ll ansl=;

    ll ad=;

    if(R==(ll)1e18) {

        R--;

        if(L1==) ad++;

    }

    //cout<<R<<endl;

    if(L==){

        ansl=;

        if(L1==) ad++;

    }

    else if(L==){

        ansl=;

    }

    else{//only zero ??

        L--;

        tot=;

        while(L){

            shu[++tot]=L%;L/=;

        }

        ansl+=wrk();

    }

    //cout<<" ansl "<<ansl<<endl;

    tot=;

    while(R){

        shu[++tot]=R%;

        R/=;

    }

    ll ansr=wrk();

    //cout<<" ansr "<<ansr<<endl;

    printf("%lld",ansr-ansl+ad);

    return ;

    //don't forget to sub sub

}

数数字

T3：

题目描述

C国有n个城市，城市间通过一个树形结构形成一个连通图。城市编号为1到n，其中1号城市为首都。国家有m支军队，分别守卫一条路径的城市。具体来说，对于军队i，他守卫的城市区域可以由一对二元组(x_i,y_i)代表。表示对于所有在x_i到y_i的最短路径上的城市，军队i都会守卫他们。

现在有q个重要人物。对于一个重要人物j，他要从他的辖区v_j出发，去到首都。出于某些原因，他希望找到一个离首都最近的，且在v_j到首都路径上的城市u_j，使得至少有k_j支军队，能够全程保护他从v_j到u_j上所经过的所有城市。换句话说，至少有k_i支军队，满足在树上，x_i到y_i的路径能完全覆盖掉v_j到u_j的路径。

100%: n,m,q <= 200000

题解：

符合T3的难度。没有想出来。暴力也0分？》？？

每个询问从st出发，往上走，符合的军队必须完全覆盖路径。

所以，一个军队的路径可以拆成两条，xi到lca,和yi到lca。就成了2*m条不拐弯的路径了。

至于暴力，可以枚举哪一个u，然后查找所有m即可。

或者二分u也行。

发现，st是一直不变的，符合条件的军队，必须一端在st子树里，另一端在ui上面。

拆完路径之后，每个xi放进一个标记deep[lca]表示，从xi出发向上有一个深度在deep[lca]的端点。

然后，对于询问st，枚举u判断m个很麻烦，

所以，循环dfs序，用主席树维护dfs序为1~i的xi们的deep[lca]的值，即线段树的区间维护一个deep=l~r的dfn在i之前的xi有多少个，

前缀差分，就可以知道st子树里deep[xi]在u上面的xi有多少个了。

枚举u很麻烦，

可以二分。O（nlog^2）

但是，线段树就可以直接二分啊！！

两棵线段树，一边差分，一遍看左子树sum和k关系，自然越往左（deep越浅）越好了。

所以，类似一个区间第k大，就可以O（nlogn）解决了。

注意还有一个坑点：

当找不到的时候，可能情况是：最后整个子树的军队都没有k个，

或者，找到的最靠上的端点比st还深（因为这个WA了好多）

主席树还是敲得不熟练啊。

不用为了省一些空间就在一个rt上重复建造，

可以每次只建一条链，rt[i]要改多次，就每次从rt[i]接着造就好了。

反正传引用。

代码

#include<bits/stdc++.h>

#define mid ((l+r)>>1)

using namespace std;

const int N=+;

int n,m,q;

struct node{

    int nxt,to;

}e[*N];

int hd[N],cnt;

void add(int x,int y){

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    hd[x]=cnt;

}

int fa[N][];

int dep[N];

int dfn[N];

int dfn2[N],df;

int fdfn[N];

vector<int>mem[N];

void dfs(int x,int d){

    dfn[x]=++df;

    dep[x]=d;

    fdfn[df]=x;

    for(int i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa[x][]) continue;

        fa[y][]=x;

        dfs(y,d+);

    }

    dfn2[x]=df;

}

int lca(int x,int y){

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

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

        if(dep[fa[x][j]]>=dep[y]) x=fa[x][j];

    }

    if(x==y) return x;

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

        if(fa[x][j]!=fa[y][j]){

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

        }

    }

    return fa[x][];

}

struct tr{

    int ls,rs;

    int sum;

}t[N*];

int tot;

int rt[N];

int now;

void upda(int &x,int y,int l,int r,int c){

    x=++tot;

    t[x].ls=t[y].ls;

    t[x].rs=t[y].rs;

    t[x].sum=t[y].sum+;

    if(l==r){

        return;

    }

    if(c<=mid) upda(t[x].ls,t[y].ls,l,mid,c);

    else upda(t[x].rs,t[y].rs,mid+,r,c);

}

int query(int x,int y,int l,int r,int k){

    //cout<<" kth "<<k<<endl;

    ///cout<<" x "<<x<<" ls "<<t[x].ls<<" rs "<<t[x].rs<<endl;

    //cout<<" y "<<y<<" ls "<<t[y].ls<<" rs "<<t[y].rs<<endl<<endl;

    if(l==r){

        if(t[x].sum<k) return ;

        return l;

    }

    int u=t[t[x].ls].sum-t[t[y].ls].sum;

    //cout<<u<<" "<<endl;

    if(u>=k){

        return query(t[x].ls,t[y].ls,l,mid,k);

    }

    else{

        k-=u;

        return query(t[x].rs,t[y].rs,mid+,r,k);

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    int x,y;

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

        scanf("%d%d",&x,&y);

        add(x,y);add(y,x);

    }

    dep[]=-;

    dfs(,);

    /*cout<<" on the tree"<<endl;

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

        cout<<i<<" : "<<fa[i][0]<<" "<<dep[i]<<"   "<<dfn[i]<<" "<<dfn2[i]<<endl;

    }*/

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

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

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

        }

    }

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

        scanf("%d%d",&x,&y);

        int anc=lca(x,y);

    //  cout<<" anc "<<anc<<endl;

        mem[dfn[x]].push_back(dep[anc]);

        mem[dfn[y]].push_back(dep[anc]);

    }

    rt[]=++tot;

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

        //cout<<" updating "<<i<<" ------------------ "<<endl;

        rt[i]=rt[i-];

        for(int j=;j<mem[i].size();j++){

            upda(rt[i],rt[i],,n,mem[i][j]);

        }

        //cout<<" after "<<tot<<endl;

    }

    ///for(int i=1;i<=tot;i++){

    //  cout<<" id "<<i<<" : "<<t[i].ls<<" "<<t[i].rs<<" "<<t[i].sum<<endl;

    //}

    scanf("%d",&q);

    int k;

    while(q--){

        scanf("%d%d",&x,&k);

        int ans=query(rt[dfn2[x]],rt[dfn[x]-],,n,k);

        //cout<<" ans "<<ans<<endl;

        if(ans==||ans>=dep[x]) printf("%d\n",);

        else printf("%d\n",dep[x]-ans);

    }

    return ;

}

保护

还是说，路径拆分没有想到，

然后，对于把deep[lca]向xi打标记，也是一种转移处理了。

主席树怎么想到？

还是从要想到，如果知道子树标记的线段树就好了，n棵太多，-》主席树

怎么连续建造？dfs序！！！和子树也恰好相关！！

总结：

1.T2还是花的时间比较长。

也许可以考虑把数位dp往后放一放？

2.T3这种综合题还是要多积累。

200pts/300pts rank28

秒客网

牛客网NOIP赛前集训营-提高组（第一场）

题目描述

题目描述

题解：

代码：

T3：

题目描述

相关文章