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

阅读量：6908 次

发布时间：2019-06-27

本文共 6091 字，大约阅读时间需要 20 分钟。

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

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

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是奇数，那么中位数为 $C[\frac{k+1}{2}]$ 。假如k为偶数，中位数为 $C[\frac{k}{2}]$ 。

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

题解

这个题一看就很套路了。

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

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

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

代码

#include
         
          #include
          
           #include
           
            using namespace std;const int N=100000+5;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=1;i<=n;i++){        scanf("%d",&a[i]);        r=max(r,a[i]);    }    l=0;    while(l<=r){        int mid=(l+r)>>1;        for(int i=1;i<=n;i++){            if(a[i]>=mid) b[i]=1;            if(a[i]
            
             0) {                fl=true;break;            }            mi=min(mi,sum[i-len+1]);        }        if(fl) ans=mid,l=mid+1;        else r=mid-1;    }    printf("%d",ans);    return 0;}

中位数

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

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

类似的题目：

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

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

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

注意边界情况等。

T2：数数字

题目描述

小N对于数字的大小一直都有两种看法。第一种看法是，使用字典序的大小（也就是我们常用的判断数字大小的方法，假如比较的数字长度不同，则在较短一个前面补齐前导0，再比较字典序），比如43<355,10<11。第二种看法是，对于一个数字 $a_ka_{k-1}\cdots a_0$ ，定义他的权值为 $a_k\times a_{k-1} \times \cdots \times a_0$ ，也就是各个数位的乘积。

现在给定两个区间，[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
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;const int N=20;const int M=34980;const int mod=34981;typedef long long ll;ll f[2][2][M][2];//gun dongll num[M],cnt;ll L,R,L1,R1;ll shu[N],tot;struct ha{    ll val[mod+10],tot;    int id[mod+10];    int nxt[mod+10],hd[mod+10];    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 0;      }}HA;ll c2[70],c3[40],c5[40],c7[40];ll wrk(){    memset(f,0,sizeof f);    int tmp=0;    f[tmp][0][1][0]=1;    for(int i=tot;i>=1;i--){        //cout<<" iii "<
                <<" ------------------- "<
                 
                  <
                  
                   =0) { ++cnt; ll now=c2[i]*c3[j]*c5[k]*c7[l]; num[cnt]=now; } } } } } num[++cnt]=0; sort(num+1,num+cnt+1); cnt=unique(num+1,num+cnt+1)-num-1; //cout<<" Cnt "<
                   
                    <

数数字

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
           
            #define mid ((l+r)>>1)using namespace std;const int N=200000+5;int n,m,q;struct node{    int nxt,to;     }e[2*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][22];int dep[N];int dfn[N];int dfn2[N],df;int fdfn[N];vector
            
             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][0]) continue;        fa[y][0]=x;        dfs(y,d+1);    }    dfn2[x]=df;}int lca(int x,int y){    if(dep[x]
             
              =0;j--){        if(dep[fa[x][j]]>=dep[y]) x=fa[x][j];    }    if(x==y) return x;    for(int j=20;j>=0;j--){        if(fa[x][j]!=fa[y][j]){            x=fa[x][j],y=fa[y][j];        }    }    return fa[x][0];}struct tr{    int ls,rs;    int sum;}t[N*50];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+1;    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+1,r,c);}int query(int x,int y,int l,int r,int k){    //cout<<" kth "<
              
               <
               
                =k){        return query(t[x].ls,t[y].ls,l,mid,k);    }    else{        k-=u;        return query(t[x].rs,t[y].rs,mid+1,r,k);    }}int main(){    scanf("%d%d",&n,&m);    int x,y;    for(int i=1;i<=n-1;i++){        scanf("%d%d",&x,&y);        add(x,y);add(y,x);    }    dep[0]=-1;    dfs(1,1);         /*cout<<" on the tree"<
                
                 =dep[x]) printf("%d\n",0); else printf("%d\n",dep[x]-ans); } return 0;}