2017.10.23 NOIP模拟赛

题解 套题

目录

• 2017.10.23 NOIP模拟赛
  • clique
    • 思路
    • 代码
  • mod
    • 思路
    • 代码
  • number
    • 思路
    • 代码

clique

思路

• 正解是将每个点看成区间$[x_i-w_i,x_i+w_i]$，求最多的不想交区间数，这个展开一下式子很好理解；
• 我的做法比较扯，但是也比较好理解；
• 考虑每个团中的点加入顺序不影响结果，我们将点按$x$升序排列；
• 这样式子里那个绝对值就可以去掉了，会方便很多；
• 那么对于当前点$i$，所有已经加入图中的$j$，如果$x_i-x_j \geq w_i+w_j$，那么$i,j$可以连边；
• 移项得$x_i-w_i \geq x_j+w_j$，我们发现，如果$i$满足某个团里最大的$x_j+w_j$，那它一定可以加入这个团；
• 那么，对于每个团$V$，我们维护一个$size$和$\max_{u \in V}\{x_v+w_v\}$；
• 对于当前点$i$，找一个符合要求的最大的团，将其加入即可；
• 为什么可以这样呢？因为$x_i-w_i \geq x_j+w_j,w_i \geq 0$，所以$x_i+w_i \geq x_j+w_j$，将$i$放入哪个团都会造成这个影响，我们贪心的放入最大的就好了；
• 至于怎么找最大的符合条件的团，我们用权值线段树维护一下就可以了；
• 复杂度和正解一样，也是$O(n \log n)$，不过常数啥的都没有那个优orz。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
using std::max;
using std::sort;
using std::unique;
using std::lower_bound;
const int MAXN=200005;
int n,tot;
int crete[MAXN<<1];
struct node{
    int pos,w;
    bool operator< (const node &that)const{return pos<that.pos;}
}d[MAXN];
class valSegT{
#define ls (u<<1)
#define rs (ls|1)
    private:
        int sz[MAXN<<3];
        int decrete(int x){
            return lower_bound(crete+1,crete+tot+1,x)-crete;
        }
        void upd(int u){
            sz[u]=max(sz[ls],sz[rs]);
        }
        int qry(int u,int l,int r,int lp,int rp){
            if(lp<=l && r<=rp) return sz[u];
            int mid=l+r>>1,ret=0;
            if(lp<=mid) ret=qry(ls,l,mid,lp,rp);
            if(rp>mid) ret=max(ret,qry(rs,mid+1,r,lp,rp));
            return ret;
        }
        void ist(int u,int l,int r,int pos,int x){
            if(l==r){
                sz[u]=max(sz[u],x);
                return;
            }
            int mid=l+r>>1;
            if(pos<=mid) ist(ls,l,mid,pos,x);
            else ist(rs,mid+1,r,pos,x);
            upd(u);
        }
    public:
        int qry(int rp){return qry(1,1,tot,1,decrete(rp));}
        void ist(int pos,int x){ist(1,1,tot,decrete(pos),x);}
#undef ls
#undef rs
}T;
inline void decrete(){
    sort(crete+1,crete+crete[0]+1);
    tot=unique(crete+1,crete+crete[0]+1)-crete-1;
}
int main(){
    setIO("clique");
    read(n);
    for(int i=1;i<=n;++i){
        read(d[i].pos),read(d[i].w);
        crete[++crete[0]]=d[i].pos-d[i].w;
        crete[++crete[0]]=d[i].pos+d[i].w;
    }
    decrete();
    sort(d+1,d+n+1);
    int ans=0;
    for(int i=1,tmp;i<=n;++i){
        tmp=1+T.qry(d[i].pos-d[i].w);
        ans=max(ans,tmp);
        T.ist(d[i].pos+d[i].w,tmp);
    }
    write(ans);
    return 0;
}

mod

思路

• 其实就是带剪枝的暴力。。。
• 考虑到$a \bmod b \leq \lfloor\frac{a}{2}\rfloor$，一个数最多被有意义的模$O(\log n)$次；
• 算上修改，均摊下来每个点也只需取模$O(\log n)$次，毕竟是单点修改；
• 那么我们只需记录区间最大值，每次取模都下去暴力修改，对于$max(u)<p$的点直接退出就好了；
• 这样均摊复杂度就是$O(n \log^2 n)$。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
using std::max;
const int MAXN=100005;
int n;
int a[MAXN];
class segT{
    private:
        struct node{
            int l,r,ls,rs,max;
            long long sum;
        }d[MAXN<<2];
        int new_nd(){
            static int cnt=1;
            return ++cnt;
        }
        void upd(int u){
            int ls=d[u].ls,rs=d[u].rs;
            d[u].max=max(d[ls].max,d[rs].max);
            d[u].sum=d[ls].sum+d[rs].sum;
        }
        void mdf(int u,int pos,int x){
            if(d[u].l==d[u].r){
                d[u].sum=d[u].max=x;
                return;
            }
            int mid=d[u].l+d[u].r>>1;
            if(pos<=mid) mdf(d[u].ls,pos,x);
            else mdf(d[u].rs,pos,x);
            upd(u);
        }
        long long qry(int u,int lp,int rp){
            if(lp<=d[u].l && d[u].r<=rp)
                return d[u].sum;
            int mid=d[u].l+d[u].r>>1;
            long long ret=0;
            if(lp<=mid) ret=qry(d[u].ls,lp,rp);
            if(rp>mid) ret+=qry(d[u].rs,lp,rp);
            return ret;
        }
        void mod(int u,int lp,int rp,int p){
            if(d[u].max<p) return;
            if(d[u].l==d[u].r){
                d[u].max=d[u].sum=d[u].max%p;
                return;
            }
            int mid=d[u].l+d[u].r>>1;
            if(lp<=mid) mod(d[u].ls,lp,rp,p);
            if(rp>mid) mod(d[u].rs,lp,rp,p);
            upd(u);
        }
        void build(int u,int l,int r){
            d[u].l=l,d[u].r=r;
            if(l==r){
                d[u].sum=d[u].max=a[l];
                return;
            }
            int mid=l+r>>1;
            d[u].ls=new_nd();
            build(d[u].ls,l,mid);
            d[u].rs=new_nd();
            build(d[u].rs,mid+1,r);
            upd(u);
        }
    public:
        void build(){build(1,1,n);}
        void mdf(int pos,int x){mdf(1,pos,x);}
        long long qry(int lp,int rp){return qry(1,lp,rp);}
        void mod(int lp,int rp,int p){mod(1,lp,rp,p);}
}T;
int main(){
    setIO("mod");
    int m;
    read(n),read(m);
    for(int i=1;i<=n;++i)
        read(a[i]);
    T.build();
    for(int i=1,opt,a,b,c;i<=m;++i){
        read(opt),read(a),read(b);
        if(opt==1) write(T.qry(a,b),'\n');
        else if(opt==3) T.mdf(a,b);
        else{
            read(c);
            T.mod(a,b,c);
        }
    }
    return 0;
}

number

思路

• 设$dp(i,k)$是$1$~$i$中二进制下有$k$个$1$的数的个数；
• 那么题目中的所求的$n$就是满足$dp(2n,k)-dp(n,k)=m$的$n$；
• 考虑到$dp(i,k)$是个前缀和，那么显然是单调不下降的，并且增长是连续的（每次最多加$1$），我们二分出满足条件的$n$的左右边界即可；
• 怎么求$dp(i,k)$呢？很好办，用组合数就好了；
• 枚举$i$的每一个为$1$的位$j$，让它为$0$，比它高的位中$1$的个数为$cnt$，则这一位的贡献为$C_{k-cnt}^{j-1}$，最后判断一下$i$是不是可行的就好了，$O(\log n)$即可求出；
• 注意特判$k=1,m=1$的情况，这种是唯一的无限多个的情况；
• 复杂度$O(t \log^2 n)$。

代码

#include <cstdio>
#include <climits>
const int MAXK=65;
int k;
long long m;
unsigned long long C_tab[MAXK][MAXK];
inline void pre_tab(){
    C_tab[0][0]=1;
    for(int i=1;i<=64;++i){
        C_tab[i][0]=1;
        for(int j=1;j<=i;++j)
            C_tab[i][j]=C_tab[i-1][j-1]+C_tab[i-1][j];
    }
}
inline unsigned long long C(int n,int m){
    if(n<0 || m<0) return 0;
    else return C_tab[n][m];
}
inline unsigned long long cal(unsigned long long x){
    unsigned long long ret=0;
    int cnt=0;
    for(int i=63;i>=0;--i){
        if(x&1ULL<<i){
            ret+=C(i,k-cnt);
            ++cnt;
        }
    }
    if(cnt==k) ++ret;
    return ret;
}
inline long long bin_chop_l(){
    unsigned long long l=1,r=LLONG_MAX,mid;
    while(l<=r){
        mid=l+r>>1;
        if(cal(mid<<1)-cal(mid)>=m)
            r=mid-1;
        else l=mid+1;
    }
    return l;
}
inline long long bin_chop_r(){
    unsigned long long l=1,r=LLONG_MAX,mid;
    while(l<=r){
        mid=l+r>>1;
        if(cal(mid<<1)-cal(mid)<=m)
            l=mid+1;
        else r=mid-1;
    }
    return r;
}
int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    pre_tab();
    int t;
    scanf("%d",&t);
    unsigned long long l,r;
    for(int i=1;i<=t;++i){
        scanf("%lld%d",&m,&k);
        if(m==1 && k==1) puts("-1");
        else{
            l=bin_chop_l();
            r=bin_chop_r();
            printf("%lld %lld\n",l,r);
        }
    }
    return 0;
}