牛客NOIP模拟赛第一场

前言

100+90+100=290 Rk10

第一题想复杂了,浪费了将近一个小时,最后还是写复杂了。

第二题细节没处理好,数据不强,能得到90。

第三题两个log卡过,稍微想一下就可以写到一个log了。

 

1.中位数

Description

有$n$个数字,要从中选出一个长度$\ge len$的连续子序列,满足中位数最大,输出中位数。偶数长度的序列的中位数定义为第$\frac{len}2$个数,奇数长度的中位数为$\frac{len+1}2$。

$1\le n \le 10^5,1\le A_i\le 10^9$

Solution

由于子序列长度不一定,没有什么方法能直接维护一个端点固定的最大中位数。

考虑二分答案。假设当前二分出来的为$x$,那么我们要判断最大的中位数是否可以大于等于$x$。

对于一个区间,我们考虑它什么时候会满足中位数大于等于$x$。

设这个区间内大于等于$x$的数有$A$个,小于$x$的数有$B$个。

那么对于奇数长度,有$B\lt \frac{A+B+1}2$,可以得到$A\gt B-1$,即$A\ge B$,而$A+B$为奇数,那么$A$肯定不等于$B$。$A\ge B$也就等价于$A\gt B$。

对于偶数长度的区间,有$B\lt \frac{A+B}2$,可以直接得到$A\gt B$。

因此,只需要找到一个$L$和$R$,满足$[L,R]$的$A\gt B$,就可以说明最大中位数大于等于$x$。

把大于等于$x$的数看做1,小于$x$的数看做-1,维护一个前缀和$sum_i$。枚举右端点,只需要存在$x\in [0,len]$满足$sum_i\gt sum_x$即可。

用一个前缀最小值就可以完成判断。

$O(nlogn)$

一开始我在奇数长度的讨论中没有注意到$A\neq B$,于是要奇偶分类讨论,还莫名其妙套了个BIT,可能是不太在状态。还好是过了。

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,K,A[N],B[N],sum[N],C[N];
bool check(int Tar){
    int i;
    for (i=1;i<=n;i++){
        if (A[i]>=Tar){
            sum[i]=sum[i-1]+1;
        }else{
            sum[i]=sum[i-1]-1;
        }
        C[i]=min(sum[i],C[i-1]);
    }
    for (i=K;i<=n;i++){
        if (sum[i]>C[i-K]){
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&K);
    int i;
    for (i=1;i<=n;i++){
        scanf("%d",&A[i]);
    }
    memcpy(B+1,A+1,sizeof(int)*1*n);
    sort(B+1,B+1+n);
    int tot=unique(B+1,B+1+n)-B-1;
    int L=1,R=tot,res=0;
    while (L<=R){
        int mid=(L+R)>>1;
        if (check(B[mid])){
            L=mid+1;
            res=B[mid];
        }else{
            R=mid-1;
        }
    }
    printf("%d\n",res);
    return 0;
}

2.中位数

Description

定义$f(x)$为$x$各数位的乘积(无前导0),求有多少$x \in [L,R]$满足$f(x)\in [L1,R1]$。

$0\le L \le R \le 10^{18},0\le L1 \le R1 \le 10^{18}$

Solution

显然的数位DP模型,但是状态不好定义。很容易发现,$10^{18}$内可以被18个0到9的数相乘得到的数并不多,可以直接枚举质因子幂次预处理出来,大概为36000个。

那么就是一个裸的数位DP了。

注意0边界的判断。

#include<bits/stdc++.h>
using namespace std;
const int N=36000,M=21;
const long long G=1000000000000000000LL;
long long L,R,L1,R1,B[N];
int tot,num[N];
long long dp[M][N];
int Find(long long x){
    int L=1,R=tot,res=tot+1;
    while (L<=R){
        int mid=(L+R)>>1;
        if (B[mid]==x){
            return mid;
        }else if (B[mid]<x){
            L=mid+1;
        }else{
            R=mid-1;
        }
    }
    return res;
}
long long Tar;
long long DP(int x,long long sum,bool limit,bool lead){
    if (x==0){
        if (sum<=Tar){
            return 1;
        }else{
            return 0;
        }
    }
    int t=Find(sum);
    if (!limit && !lead && ~dp[x][t]){
        return dp[x][t];
    }
    long long res=0;
    int i,Up=(limit?num[x]:9);
    for (i=0;i<=Up;i++){
        if (lead && i==0){
            res+=DP(x-1,1,limit && i==num[x],1);
        }else{
            res+=DP(x-1,sum*i,limit && i==num[x],0);
        }
    }
    if (!limit && !lead){
        dp[x][t]=res;
    }
    return res;
}
long long Calc(long long x,long long y){
    if (x<0 || y<0){
        return 0;
    }
    Tar=y;
    int h=0;
    while (x>0){
        num[++h]=x%10;
        x/=10;
    }
    memset(dp,-1,sizeof(dp));
    long long res=DP(h,1,1,1);
    if (y==0){
        res++;
    }
    return res;
}
void init(){
    B[++tot]=0;
    int i,j,k,l;
    long long p2=1;
    for (i=0;i<=54 && (i+2)/3<=18;i++,p2*=2){
        long long p3=p2;
        for (j=0;j<=36 && (i+2)/3+(j+1)/2<=18 && p3<=G;j++,p3*=3){
            long long p5=p3;
            for (k=0;k<=18 && (i+2)/3+(j+1)/2+k<=18 && p5<=G;k++,p5*=5){
                long long p7=p5;
                for (l=0;l<=18 && (i+2)/3+(j+1)/2+k+l<=18 && p7<=G;l++,p7*=7){
                    B[++tot]=p7;
                }
            }
        }
    }
    sort(B+1,B+1+tot);
}
int main(){
    cin>>L>>R>>L1>>R1;
    init();
    long long Ans=Calc(R,R1)-Calc(R,L1-1)-Calc(L-1,R1)+Calc(L-1,L1-1);
    printf("%lld\n",Ans);
    return 0;
}

3.保护

Description

有一棵$n$个点,以1为根的树。有$m$条线段,$q$个询问,每次询问在$x$到根的路径上,能够被至少$k$条线段完全覆盖的深度最小的点,输出$x$到这个点的距离。

$1\le n,m,q \le 2*10^5$

Solution

显然不能直接解。二分转化为判定性问题。

二分到一个点$y$,满足$y$是$x$的祖先。那么也就是询问完全覆盖$(x,y)$的路径数量。

没有修改操作,所以这是个静态的二维偏序问题。只需要询问$x$子树内到$y$的下一个点(接近于$x$的一个点)的子树外的线段数量即可。用dfs序建主席树即可。

$O(nlog^2n)$

据说出题人本来不想放$nlog^2n$过的?

线段树合并的方法也很简单。

把一个线段拆成两个,分别为两个端点到LCA处。在端点处把这个线段插入线段树。$x$点的线段树维护从$x$的子树里的线段出发,到$x$的某个高度的祖先,能被多少条线段完整覆盖。先合并预处理,然后询问的时候在线段树上二分即可。

$O(nlogn)$

由于我比较懒就没有补线段树合并的写法= =

#include<bits/stdc++.h>
using namespace std;
void rd(int &x){
    static char c; x=0;
    while (c=getchar(),c<48);
    do x=(x<<3)+(x<<1)+(c^48);
    while (c=getchar(),c>47);
}
const int N=200010;
struct edge{
    int nxt,t;
}e[N<<1];
int head[N],edge_cnt;
void add_edge(int x,int y){
    e[edge_cnt]=(edge){head[x],y};
    head[x]=edge_cnt++;
}
struct Segment_Tree{
    #define Lc lson[p]
    #define Rc rson[p]
    #define Lc1 lson[pre]
    #define Rc1 rson[pre]
    int sum[N*40],lson[N*40],rson[N*40],T_cnt;
    void clear(){
        memset(sum+1,0,sizeof(int)*1*T_cnt);
        memset(lson+1,0,sizeof(int)*1*T_cnt);
        memset(rson+1,0,sizeof(int)*1*T_cnt);
        T_cnt=0;
    }
    void build(int l,int r,int &p){
        p=++T_cnt;
        sum[p]=0;
        if (l==r){
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,Lc);
        build(mid+1,r,Rc);
    }
    void Update(int l,int r,int &p,int pre,int x){
        if (p==0 || p==pre){
            p=++T_cnt;
            sum[p]=sum[pre];
            Lc=Lc1;
            Rc=Rc1;
        }
        if (l==r){
            sum[p]++;
            return;
        }
        int mid=(l+r)>>1;
        if (x<=mid){
            Update(l,mid,Lc,Lc1,x);
        }else{
            Update(mid+1,r,Rc,Rc1,x);
        }
        sum[p]=sum[Lc]+sum[Rc];
    }
    int Query(int l,int r,int p,int pl,int pr){
        if (l==pl && r==pr){
            return sum[p];
        }
        int mid=(l+r)>>1;
        if (pr<=mid){
            return Query(l,mid,Lc,pl,pr);
        }else if (pl>mid){
            return Query(mid+1,r,Rc,pl,pr);
        }else{
            return Query(l,mid,Lc,pl,mid)+Query(mid+1,r,Rc,mid+1,pr);
        }
    }
    #undef Lc
    #undef Rc
    #undef Lc1
    #undef Rc1
}T;
int fa[N],Tid[N],Ted[N],dfs_cnt;
void dfs(int x,int f){
    Tid[x]=++dfs_cnt;
    fa[x]=f;
    int i;
    for (i=head[x];~i;i=e[i].nxt){
        int to=e[i].t;
        if (to==f){
            continue;
        }
        dfs(to,x);
    }
    Ted[x]=dfs_cnt;
}
int n,m,q,Rt[N];
struct Que{
    int x,id;
};
vector<Que>Q[N];
int stk[N],stk_top,Ans[N];
int Query(int x,int y){
    int l1=1,r1=Tid[x]-1,l2=Ted[x]+1,r2=n,l0=Tid[y],r0=Ted[y];
    int res=0;
    if (l1<=r1){
        res+=T.Query(1,n,Rt[r0],l1,r1)-T.Query(1,n,Rt[l0-1],l1,r1);
    }
    if (l2<=r2){
        res+=T.Query(1,n,Rt[r0],l2,r2)-T.Query(1,n,Rt[l0-1],l2,r2);
    }
    return res;
}
void Answer(int x,int y,int id){
    int L=1,R=stk_top-1,res=0;
    while (L<=R){
        int mid=(L+R)>>1;
        if (Query(stk[mid+1],x)>=y){
            R=mid-1;
            res=stk_top-mid;
        }else{
            L=mid+1;
        }
    }
    Ans[id]=res;
}
void Solve(int x){
    stk[++stk_top]=x;
    int i;
    for (i=0;i<(int)Q[x].size();i++){
        Answer(x,Q[x][i].x,Q[x][i].id);
    }
    for (i=head[x];~i;i=e[i].nxt){
        int to=e[i].t;
        if (to==fa[x]){
            continue;
        }
        Solve(to);
    }
    stk_top--;
}
vector<int>A[N];
int main(){
    int i,j;
    rd(n),rd(m);
    memset(head+1,-1,sizeof(int)*1*n);
    for (i=1;i<n;i++){
        int x,y;
        rd(x),rd(y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs(1,0);
    for (i=1;i<=m;i++){
        int x,y;
        rd(x),rd(y);
        if (x==y){
            continue;
        }
        x=Tid[x],y=Tid[y];
        A[x].push_back(y);
        A[y].push_back(x);
    }
    T.build(1,n,Rt[0]);
    for (i=1;i<=n;i++){
        Rt[i]=Rt[i-1];
        for (j=0;j<(int)A[i].size();j++){
            T.Update(1,n,Rt[i],Rt[i-1],A[i][j]);
        }
    }
    rd(q);
    for (i=1;i<=q;i++){
        int x,y;
        rd(x),rd(y);
        Q[x].push_back((Que){y,i});
    }
    Solve(1);
    for (i=1;i<=q;i++){
        printf("%d\n",Ans[i]);
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注