[NOIP模拟测试11] 题解

A.string

和河北的一道省选题很像。考场上写的暴力桶排，正解其实就是优化一下这个思路。

开线段树维护字符串中每个字母出现的次数。对于每条询问，区间查询、区间赋值维护即可。

另外，本题卡常严重，正解能被卡到40到90不等。所以直接循环展开乱搞一波？

暴力40分代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=;
int a[N],bu[],n,m;
char str[N];
int read()
{
    int x=,f=;char ch=getchar();
    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
    while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
    return x*f;
}
void busort(int op,int l,int r)
{
    for(int i=l;i<=r;i++)
        bu[a[i]]++;
    int tot=;
    if(op)
    {
        for(int i=;i<=;i++)
            while(bu[i])a[l+(tot++)]=i,bu[i]--;
    }
    else
    {
        for(int i=;i>=;i--)
            while(bu[i])a[l+(tot++)]=i,bu[i]--;
    }
}
int main()
{
    n=read();m=read();
    scanf("%s",str+);
    for(int i=;i<=n;i++)
        a[i]=(int)str[i];
    while(m--)
    {
        int l=read(),r=read(),op=read();
        busort(op,l,r);
    }
    for(int i=;i<=n;i++)
    {
        char ch=(char)a[i];
        printf("%c",ch);
    }
    return ;
}

被卡的90分代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=;
int read()
{
    int x=,f=;char ch=getchar();
    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
    while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
    return x*f;
}
int n,m,len;
char str[N],ans[N];
#define ls(k) k<<1
#define rs(k) k<<1|1
int num[N<<][],lz[N<<],le[N<<],re[N<<];
int res[];
void up(int k)
{
    for(int i=;i<=;i++)
        num[k][i]=num[ls(k)][i]+num[rs(k)][i];
}
void build(int k,int l,int r)
{
    lz[k]=;le[k]=l,re[k]=r;
    if(l==r)
    {
        num[k][str[l]-'a'+]=;
        return ;
    }
    int mid=l+r>>;
    build(ls(k),l,mid);
    build(rs(k),mid+,r);
    up(k);
}
void down(int k)
{
    memset(num[ls(k)],,sizeof(num[ls(k)]));
    memset(num[rs(k)],,sizeof(num[rs(k)]));
    num[ls(k)][lz[k]]=re[ls(k)]-le[ls(k)]+;
    num[rs(k)][lz[k]]=re[rs(k)]-le[rs(k)]+;
    lz[ls(k)]=lz[rs(k)]=lz[k];
    lz[k]=;
}
void query(int k,int L,int R)
{
    if(le[k]>=L&&R>=re[k])
    {
        for(int i=;i<=;i++)
            res[i]+=num[k][i];
        return ;
    }
    int mid=le[k]+re[k]>>;
    if(lz[k])down(k);
    if(L<=mid)query(ls(k),L,R);
    if(R>mid)query(rs(k),L,R);
}
void change(int k,int L,int R,int val)
{
    if(le[k]>=L&&R>=re[k])
    {
        memset(num[k],,sizeof(num[k]));
        num[k][val]=re[k]-le[k]+;
        lz[k]=val;
        return ;
    }
    int mid=le[k]+re[k]>>;
    if(lz[k])down(k);
    if(L<=mid)change(ls(k),L,R,val);
    if(R>mid)change(rs(k),L,R,val);
    up(k);
}
void cacl(int k)
{
    if(le[k]==re[k])
    {
        for(int i=;i<=;i++)
            if(num[k][i])
            {
                ans[++len]=i-+'a';
                return ;
            }
    }
    if(lz[k])down(k);
    cacl(ls(k));
    cacl(rs(k));
}
int main()
{
    n=read();m=read();
    scanf("%s",str+);
    build(,,n);
    for(int i=;i<=m;i++)
    {
        int l=read(),r=read(),op=read();
        memset(res,,sizeof(res));
        query(,l,r);
        if(op)
        {
            for(int j=;j<=;j++)
                if(res[j])
                    change(,l,l+res[j]-,j),l+=res[j];
        }
        else
        {
            for(int j=;j>=;j--)
                if(res[j])
                    change(,l,l+res[j]-,j),l+=res[j];
        }
    }
    cacl();
    printf("%s\n",ans+);
    return ;
}

丧心病狂科学打表的循环展开代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#define rint  register int
using namespace std;
const int N=;
int read()
{
    int x=,f=;char ch=getchar();
    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
    while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
    return x*f;
}
int n,m,len;
char str[N],ans[N];
#define ls(k) k<<1
#define rs(k) k<<1|1
int num[N<<][],lz[N<<],le[N<<],re[N<<];
int res[];
void up(int k)
{
                                 num[k][]=num[ls(k)][]+num[rs(k)][];
                     num[k][]=num[ls(k)][]+num[rs(k)][];
                                                 num[k][]=num[ls(k)][]+num[rs(k)][];
                  num[k][]=num[ls(k)][]+num[rs(k)][];
                                                          num[k][]=num[ls(k)][]+num[rs(k)][];
                      num[k][]=num[ls(k)][]+num[rs(k)][];
                                                                   num[k][]=num[ls(k)][]+num[rs(k)][];
                              num[k][]=num[ls(k)][]+num[rs(k)][];
      num[k][]=num[ls(k)][]+num[rs(k)][];
                                      num[k][]=num[ls(k)][]+num[rs(k)][];
                                                                 num[k][]=num[ls(k)][]+num[rs(k)][];
                                          num[k][]=num[ls(k)][]+num[rs(k)][];
                                      num[k][]=num[ls(k)][]+num[rs(k)][];
                                                                          num[k][]=num[ls(k)][]+num[rs(k)][];
                                 num[k][]=num[ls(k)][]+num[rs(k)][];
                                                              num[k][]=num[ls(k)][]+num[rs(k)][];
                         num[k][]=num[ls(k)][]+num[rs(k)][];
                                             num[k][]=num[ls(k)][]+num[rs(k)][];
                                                                     num[k][]=num[ls(k)][]+num[rs(k)][];
              num[k][]=num[ls(k)][]+num[rs(k)][];
                                                                  num[k][]=num[ls(k)][]+num[rs(k)][];
                                  num[k][]=num[ls(k)][]+num[rs(k)][];
          num[k][]=num[ls(k)][]+num[rs(k)][];
                                                                 num[k][]=num[ls(k)][]+num[rs(k)][];
                              num[k][]=num[ls(k)][]+num[rs(k)][];
                                 num[k][]=num[ls(k)][]+num[rs(k)][];
}
void build(int k,int l,int r)
{
    lz[k]=;le[k]=l,re[k]=r;
    if(l==r)
    {
        num[k][str[l]-'a'+]=;
        return ;
    }
    int mid=l+r>>;
    build(ls(k),l,mid);
    build(rs(k),mid+,r);
    up(k);
}
void down(int k)
{
    memset(num[ls(k)],,sizeof(num[ls(k)]));
    memset(num[rs(k)],,sizeof(num[rs(k)]));
    num[ls(k)][lz[k]]=re[ls(k)]-le[ls(k)]+;
    num[rs(k)][lz[k]]=re[rs(k)]-le[rs(k)]+;
    lz[ls(k)]=lz[rs(k)]=lz[k];
    lz[k]=;
}
void query(int k,int L,int R)
{
    if(le[k]>=L&&R>=re[k])
    {
                                                                res[]+=num[k][];
                                                    res[]+=num[k][];
            res[]+=num[k][];
                        res[]+=num[k][];
                        res[]+=num[k][];
            res[]+=num[k][];
                            res[]+=num[k][];
                                    res[]+=num[k][];
                res[]+=num[k][];
                                    res[]+=num[k][];
                        res[]+=num[k][];
                                                res[]+=num[k][];
                    res[]+=num[k][];
                                                            res[]+=num[k][];
                                res[]+=num[k][];
                                                res[]+=num[k][];
                                            res[]+=num[k][];
                                                        res[]+=num[k][];
                                res[]+=num[k][];
                                            res[]+=num[k][];
                res[]+=num[k][];
        res[]+=num[k][];
                    res[]+=num[k][];
                                        res[]+=num[k][];
                                                            res[]+=num[k][];
                                    res[]+=num[k][];
        return ;
    }
    int mid=le[k]+re[k]>>;
    if(lz[k])down(k);
    if(L<=mid)query(ls(k),L,R);
    if(R>mid)query(rs(k),L,R);
}
void change(int k,int L,int R,int val)
{
    if(le[k]>=L&&R>=re[k])
    {
        memset(num[k],,sizeof(num[k]));
        num[k][val]=re[k]-le[k]+;
        lz[k]=val;
        return ;
    }
    int mid=le[k]+re[k]>>;
    if(lz[k])down(k);
    if(L<=mid)change(ls(k),L,R,val);
    if(R>mid)change(rs(k),L,R,val);
    up(k);
}
void cacl(int k)
{
    if(le[k]==re[k])
    {
        if(num[k][]){ans[++len]=-+'a';return ;}
                        if(num[k][]){ans[++len]=-+'a';return ;}
                if(num[k][]){ans[++len]=-+'a';return ;}
                            if(num[k][]){ans[++len]=-+'a';return ;}
                                        if(num[k][]){ans[++len]=-+'a';return ;}
    if(num[k][]){ans[++len]=-+'a';return ;}
                if(num[k][]){ans[++len]=-+'a';return ;}
                                    if(num[k][]){ans[++len]=-+'a';return ;}
                                            if(num[k][]){ans[++len]=-+'a';return ;}
    if(num[k][]){ans[++len]=-+'a';return ;}
                                        if(num[k][]){ans[++len]=-+'a';return ;}
                        if(num[k][]){ans[++len]=-+'a';return ;}
    if(num[k][]){ans[++len]=-+'a';return ;}
    if(num[k][]){ans[++len]=-+'a';return ;}
            if(num[k][]){ans[++len]=-+'a';return ;}
                        if(num[k][]){ans[++len]=-+'a';return ;}
                                    if(num[k][]){ans[++len]=-+'a';return ;}
    if(num[k][]){ans[++len]=-+'a';return ;}
                                if(num[k][]){ans[++len]=-+'a';return ;}
                        if(num[k][]){ans[++len]=-+'a';return ;}
                                                    if(num[k][]){ans[++len]=-+'a';return ;}
                            if(num[k][]){ans[++len]=-+'a';return ;}
                if(num[k][]){ans[++len]=-+'a';return ;}
    if(num[k][]){ans[++len]=-+'a';return ;}
            if(num[k][]){ans[++len]=-+'a';return ;}
                                    if(num[k][]){ans[++len]=-+'a';return ;}
    }
    if(lz[k])down(k);
    cacl(ls(k));
    cacl(rs(k));
}
int main()
{
    n=read();m=read();
    scanf("%s",str+);
    build(,,n);
    for(rint i=;i<=m;i++)
    {
        int l=read(),r=read(),op=read();
        memset(res,,sizeof(res));
        query(,l,r);
        if(op)
        {
                        if(res[])change(,l,l+res[]-,),l+=res[];
                    if(res[])change(,l,l+res[]-,),l+=res[];
                                if(res[])change(,l,l+res[]-,),l+=res[];
                    if(res[])change(,l,l+res[]-,),l+=res[];
                                                if(res[])change(,l,l+res[]-,),l+=res[];
                        if(res[])change(,l,l+res[]-,),l+=res[];
                                            if(res[])change(,l,l+res[]-,),l+=res[];
                            if(res[])change(,l,l+res[]-,),l+=res[];
                                                    if(res[])change(,l,l+res[]-,),l+=res[];
                        if(res[])change(,l,l+res[]-,),l+=res[];
                                            if(res[])change(,l,l+res[]-,),l+=res[];
                            if(res[])change(,l,l+res[]-,),l+=res[];
                                                if(res[])change(,l,l+res[]-,),l+=res[];
                                if(res[])change(,l,l+res[]-,),l+=res[];
                                                    if(res[])change(,l,l+res[]-,),l+=res[];
                if(res[])change(,l,l+res[]-,),l+=res[];
                                if(res[])change(,l,l+res[]-,),l+=res[];
                                        if(res[])change(,l,l+res[]-,),l+=res[];
                    if(res[])change(,l,l+res[]-,),l+=res[];
                                                if(res[])change(,l,l+res[]-,),l+=res[];
                        if(res[])change(,l,l+res[]-,),l+=res[];
                                                    if(res[])change(,l,l+res[]-,),l+=res[];
                        if(res[])change(,l,l+res[]-,),l+=res[];
                                        if(res[])change(,l,l+res[]-,),l+=res[];
                if(res[])change(,l,l+res[]-,),l+=res[];
                                   if(res[])change(,l,l+res[]-,),l+=res[];
        }
        else
        {
                                if(res[])change(,l,l+res[]-,),l+=res[];
        if(res[])change(,l,l+res[]-,),l+=res[];
                                            if(res[])change(,l,l+res[]-,),l+=res[];
                    if(res[])change(,l,l+res[]-,),l+=res[];
                                        if(res[])change(,l,l+res[]-,),l+=res[];
            if(res[])change(,l,l+res[]-,),l+=res[];
                                        if(res[])change(,l,l+res[]-,),l+=res[];
      if(res[])change(,l,l+res[]-,),l+=res[];
                                        if(res[])change(,l,l+res[]-,),l+=res[];
                            if(res[])change(,l,l+res[]-,),l+=res[];
                                                    if(res[])change(,l,l+res[]-,),l+=res[];
                        if(res[])change(,l,l+res[]-,),l+=res[];
                                            if(res[])change(,l,l+res[]-,),l+=res[];
                                        if(res[])change(,l,l+res[]-,),l+=res[];
                            if(res[])change(,l,l+res[]-,),l+=res[];
                                                        if(res[])change(,l,l+res[]-,),l+=res[];
                                        if(res[])change(,l,l+res[]-,),l+=res[];
                                    if(res[])change(,l,l+res[]-,),l+=res[];
                            if(res[])change(,l,l+res[]-,),l+=res[];
                    if(res[])change(,l,l+res[]-,),l+=res[];
                                        if(res[])change(,l,l+res[]-,),l+=res[];
                                if(res[])change(,l,l+res[]-,),l+=res[];
                                            if(res[])change(,l,l+res[]-,),l+=res[];
                                        if(res[])change(,l,l+res[]-,),l+=res[];
       if(res[])change(,l,l+res[]-,),l+=res[];
                            if(res[])change(,l,l+res[]-,),l+=res[];
        }
    }
    cacl();
    printf("%s\n",ans+);
    return ;
}

B.matrix

神dp。状态数组我估计一辈子都想不出来。

（虽然题意不明 似乎默认限制区间外必填0？）

我们把构造矩阵的过程看作往矩阵里填1的过程，设$f[i][j]$为填到第i列，有j个1在右侧限制区间里的方案数。

设$lnum[i]$为到i列时已结束的左限制区间的个数，$rnum[i]$为到i列时已开始的右限制区间的个数。

转移时左右区间分别考虑：

对于右区间，考虑到i列放与不放即可。如果不放的话就直接继承状态，即$f[i][j]+=f[i-1][j]$.如果放，则有$f[i][j+1]+=f[i-1][j]*(rnum[i]-j)$,解释一下：放1肯定得在已开始的右区间里放，但是还要除去已经放了的j个右区间。

对于左区间，我们只在恰好经过它的结束点时对它进行考虑。既然有j个1放在右限制区间，已经转移了i列，那么一定有i-j个1放在左限制区间，毕竟每列只放一个。又因为有$lnum[i-1]$个左区间已经结束并处理过了，所以留给恰在第i列结束的左区间的1只有$i-j-lnum[i-1]$个(当然，这些1也可以放在之前的某一列里)，那么对方案的贡献就要乘上$A_{i-j-lnum[i-1]}^{lnum[i]-lnum[i-1]}$了。

排列数打表或逆元求皆可。

//dp[i][j]:到第i列，j个1在各行的右区间
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=;
const ll mod=;
int L[N],R[N],numl[N],numr[N],n,m;
ll dp[N][N],A[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
    {
        scanf("%d%d",&L[i],&R[i]);
        numl[L[i]]++;numr[R[i]]++;
    }
    for(int i=;i<=m;i++)
        numl[i]+=numl[i-],numr[i]+=numr[i-];
    for(int i=;i<=m;i++)
    {
        A[i][]=;
        for(int j=;j<=i;j++)
            A[i][j]=A[i][j-]*1LL*(i-j+)%mod;
    }
    dp[][]=;A[][]=;
    for(int i=;i<=m;i++)
    {
        for(int j=;j<=n;j++)
        {
            if(i-j-numl[i-]<numl[i]-numl[i-])//左：在这一列结束的左区间能放几个1
            {
                dp[i][j]=;
                continue;
            }
            (dp[i][j]*=A[i-j-numl[i-]][numl[i]-numl[i-]])%=mod;
            (dp[i+][j]+=dp[i][j])%=mod;
            (dp[i+][j+]+=dp[i][j]*1LL*(numr[i+]-j))%=mod;
        //    cout<<dp[i][j]<<endl;
        }
    }
    cout<<dp[m][n]<<endl;
    return ;
}

C.

sb对手干的破事其实就是循环左移(最靠前的一位挪到后面，剩下全体左移一位)

异或满足交换律结合律，那么就可以先利用前后缀求出每次除了初值外的异或和，将它们插入一棵01Trie，并通过对它进行dfs得出结果。

如果儿子只有一个，我们选x时就能取与它相反的一位从而让这位成为1，所以在计答案时这一位为1；如果儿子有两个，不论我们这位选0还是1，对手都会取相同的一位使这一位成为0，所以答案中这一位只能为0。

复杂度$O(nm)$

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=;
int a[N],trie[N*][],xors[N],sxor[N];
int tot,ans,ansnum,n,m;
void ins(int num)
{
    int root=;
    for(int i=n-;i>=;i--)
    {
        int x=(num>>i)&;
        if(!trie[root][x])trie[root][x]=++tot;
        root=trie[root][x];
    }
}
void dfs(int x,int val,int pos)
{
    if(pos==)
    {
        if(val>ans)ans=val,ansnum=;
        else if(val==ans)ansnum++;
        return ;
    }
    if(!trie[x][]||!trie[x][])dfs(trie[x][]+trie[x][],val|(pos>>),pos>>);
    else dfs(trie[x][],val,pos>>),dfs(trie[x][],val,pos>>);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;i++)scanf("%d",&a[i]);
    sxor[]=a[];
    for(int i=;i<=m;i++)
        sxor[i]=sxor[i-]^a[i];
    xors[m]=a[m];
    for(int i=m-;i>=;i--)
        xors[i]=xors[i+]^a[i];
    for(int i=;i<=m;i++)
        ins(xors[i+]^(((sxor[i]<<)/(<<n)+(sxor[i]<<))%(<<n)));
    dfs(,,<<n);
    cout<<ans<<endl<<ansnum<<endl;
    return ;
}

UPD:之前说T3那个式子叫逻辑左移？不对不对，被亚历克斯鹅科普了一下，应该是循环左移（意会为主好吧）。