【SCOI补全记】SCOI2016 bzoj4567-4572

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

T1:背单词(bzoj4567)

题解

关键词：trie树 贪心

题意有些难懂，简单解释一下。

对于在位置$x$的单词：

• 单词没有后缀，吃
  x
  
  $\mathrm{<br>\; x<br>}$
  

  $x$颗泡椒

  • 所有后缀在$1$~
    x−1
    
    $\mathrm{<br>\; x<br>}$
    
    −
    
    
    1
    
    

    $x-1$中出现，且后缀最靠后位置为$y$，吃
    x−y
    

    $\mathrm{<br>\; x<br>}$
    
    −
    
    
    y
    
    

    $x-y$颗泡椒

  • 有后缀出现在$x$以后，吃
    n2
    
    ${}^{}$
    
    n
    
    
    2
    
    
    

    $n^2$颗泡椒

  • 显然最后一种情况是不优的，那么保证所有单词出现在它的后缀以后即可。

    将单词reverse建立一颗“后缀”trie树，即从根出发的任意一条向下路径为某个单词的后缀。按深度遍历保证了不会出现第三种情况。

    剩下的就是贪心了，我们将trie树上代表单词终止点的结点取出来建一棵虚树，把每个点的子节点按子树大小排序，在dfs时先遍历子树size大的显然最优。

    一道看似简单的题，实际上代码还是有点技巧的(时间标记，前驱等等，打WA了几次)。

    代码

    #include<bits/stdc++.h>
    #define RI register
    using namespace std;
    typedef long long ll;
    const int N=510050;
    
    int n,cnt,len,sz[N],bel[N];
    int ch[N][26],ed[N],tim[N],bs;ll ans;
    vector<int>son[N];
    char s[N];
    
    inline bool cmp(const int&x,const int&y){
          
          return sz[x]>sz[y];}
    
    inline void build(int u)
    {
        if(ed[u]) {
            son[bel[u]].push_back(u);
            bel[u]=u;
        }
        for(RI int i=0;i<26;++i) if(ch[u][i]){
            bel[ch[u][i]]=bel[u];
            build(ch[u][i]);
        }
    
    }
    
    inline void getsz(int u)
    {
         sz[u]=ed[u];
         for(RI int i=son[u].size()-1;~i;--i){
            getsz(son[u][i]);
            sz[u]+=sz[son[u][i]];
         }
         sort(son[u].begin(),son[u].end(),cmp);
    }
    
    inline void dfs(int dep,int u,int pre)
    {
        if(ed[u]) {
            tim[u]=++bs;
            ans+= pre? tim[u]-tim[pre]:bs; 
            pre=u;
        }
        for(RI int i=son[u].size()-1;~i;--i)
         dfs(dep+1,son[u][i],pre);
    }
    
    int main(){
        RI int i,j,u,alp;
        scanf("%d",&n);
        for(i=1;i<=n;++i){
            scanf("%s",s+1);
            len=strlen(s+1);
            for(u=0,j=len;j>=1;--j){
                alp=s[j]-'a';
                if(!ch[u][alp]) ch[u][alp]=++cnt;
                u=ch[u][alp];
            }
            ed[u]=1;
        }
        build(0);
        getsz(0);
        dfs(0,0,0);
        printf("%lld\n",ans);
    }

    ---

    T2:幸运数字(bzoj4568)

    题解

    关键词：线性基 倍增LCA

    线性基是可以$O(logG_i)$建立和合并的。所以倍增LCA中同样可以存储节点$i$到第
    2j
    

    ${}^{}$
    
    2
    
    
    j
    
    
    

    $2^j$次幂个祖先的链上的线性基。

    熟悉线性基的话，很快就能码出来了。时间复杂度$O((n+m)log^2G_i)$。

    代码

    #include<bits/stdc++.h>
    #define RI register
    #define gc getchar()
    #define si isdigit(c)
    using namespace std;
    typedef long long ll;
    const int N=2e4+100;
    int n,m,F[N][16],d[N];
    int head[N],to[N<<2],nxt[N<<2],tot;
    ll bin[62],ans;
    
    struct P{
      ll bs[62];
    }f[N][16],tp,v[N];
    
    char c;
    template<class T>
    inline void rd(T &x)
    {
        c=gc;x=0;
        for(;!si;c=gc);
        for(;si;c=gc) x=x*10+(c^48);
    }
    
    inline void lk(int u,int v)
    {to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
    
    inline P merge(P a,P b)
    {
        RI int i,j;ll res;
        for(i=60;~i;--i){
            res=b.bs[i];
            for(j=i;~j && res;--j) if(res&bin[j]){
                if(!a.bs[j]) a.bs[j]=res;
                res^=a.bs[j];
            }
         }
        return a;
    }
    
    void dfs(int x)
    {
        RI int i,j;
        for(i=1;bin[i]<=d[x];++i) 
          F[x][i]=F[F[x][i-1]][i-1]; 
        for(i=1;bin[i]<=d[x];++i) 
          f[x][i]=merge(f[x][i-1],f[F[x][i-1]][i-1]);
        for(i=head[x];i;i=nxt[i]){
            j=to[i];if(j==F[x][0]) continue;
            F[j][0]=x;f[j][0]=merge(v[x],v[j]);
            d[j]=d[x]+1;dfs(j);
        }
    }
    
    inline P get(int x,int y)
    {
        tp=v[x];
        if(d[x]<d[y]) swap(x,y);
        RI int i,t=d[x]-d[y];
        for(i=0;bin[i]<=t;++i)
         if(t&bin[i]){
            tp=merge(tp,f[x][i]);
            x=F[x][i];
         }
        if(x==y) return tp;
        for(i=14;~i;--i)
         if(F[x][i]!=F[y][i]){
            tp=merge(tp,f[x][i]);
            tp=merge(tp,f[y][i]);
            x=F[x][i];y=F[y][i];
         }
        tp=merge(tp,merge(f[x][0],f[y][0]));
        return tp;
    }
    
    int main(){
        RI int i,j,k,x,y;ll val;
        bin[0]=1;
        for(i=1;i<=60;++i) bin[i]=bin[i-1]<<1;
        rd(n);rd(m);
        for(i=1;i<=n;++i){
          rd(val);for(j=60;~j;--j) if(val&bin[j]) {v[i].bs[j]=val;break;}
        }
        for(i=1;i<n;++i){rd(x);rd(y);lk(x,y);lk(y,x);}
        dfs(1);
        for(;m;--m){
            ans=0;
            rd(x);rd(y);
            get(x,y);
            for(i=60;~i;--i) 
              ans=max(ans,ans^tp.bs[i]);
            printf("%lld\n",ans);
        }
    }

    ---

    T3:萌萌哒(bzoj4569)

    关键词：倍增优化并查集
    传送门

    ---

    T4:妖怪(bzoj4570)

    关键词： 凸包
    传送门

    ---

    T5:美味(bzoj4571)

    题解

    关键词：主席树 拆位

    因为每次只需要选择最优的一道菜，所以可以拆二进制位对所有菜的评价值建主席树，$a_i<10^5$，建立范围为$[0,a_{i_{max}}]$每次往最优的区间走查询这段区间中是否能取到0/1，从高位到低位逐位选择即可。

    想到拆位就比较好做的一道题。时间复杂度$O(m\log^2n)$。

    代码

    #include<bits/stdc++.h>
    #define RI register
    #define gc getchar()
    #define si isdigit(c)
    #define mid (((l)+(r))>>1)
    using namespace std;
    const int N=2e5+10,mx=(1<<18)-1;
    int now,n,m,qb,qx,ql,qr,des,bin[25];
    int rt[N],ls[N*20],rs[N*20],sz[N*20],tot;
    
    char c;
    inline void rd(int &x)
    {
        c=gc;x=0;
        for(;!si;c=gc);
        for(;si;c=gc) x=x*10+(c^48);
    }
    
    inline void build(int pre,int &nw,int l,int r,int pos)
    {
        nw=++tot;sz[nw]=sz[pre]+1;
        if(l==r) return;
        if(pos<=mid){
           rs[nw]=rs[pre];
           build(ls[pre],ls[nw],l,mid,pos);
        }else{
           ls[nw]=ls[pre];
           build(rs[pre],rs[nw],mid+1,r,pos);
        }
    }
    
    inline bool get(int pre,int nw,int l,int r,int L,int R)
    {
        if(L<=l && r<=R) return (sz[nw]-sz[pre]>0);
        bool re=false;
        if(L<=mid) re=get(ls[pre],ls[nw],l,mid,L,R);
        if(!re && R>mid) re=get(rs[pre],rs[nw],mid+1,r,L,R);
        return re;
    }
    
    int main(){
        RI int i,j,l,r;
        bin[0]=1;for(i=1;i<=20;++i) bin[i]=bin[i-1]<<1;
        rd(n);rd(m);
        for(i=1;i<=n;++i){
           rd(j);
           build(rt[i-1],rt[i],0,mx,j);
        }
        for(;m;--m){
            rd(qb);rd(qx);rd(ql);rd(qr);
            des=mx&(~qb);now=0;
            for(i=17;~i;--i){
               if(!(qb&bin[i])) now^=bin[i];
               l=max(now-qx,0);r=(now|(bin[i]-1))-qx;
               if(r<0 || (!get(rt[ql-1],rt[qr],0,mx,l,r))) now^=bin[i];
            }
            printf("%d\n",now^qb);
        }
    }

    ---

    T6:围棋(bzoj4572)

    关键词：轮廓线DP
    传送门

    ---

    总结

    考点：
    字符串 $\times$ 1
    倍增$\times$ 2
    计算几何$\times$ 1
    线性基/二进制拆位$\times$ 2
    简单数据结构(简单主席树)$\times$ 1
    DP(轮廓线)$\times$ 1

    倍增/二进制位出现频率较高？
    数据结构较基础？
    $DP$普遍毒瘤？
    算几年年出现？

    T1,2,5不能错
    T3是一道不可多得的思维好题
    T4算几还需要多加练习
    T6轮廓线DP还不熟练，考试码不出来(似乎是道压轴题，雾)
    思维题偏少