2017.10.26 NOIP模拟赛

题解 套题

目录

• 2017.10.26 NOIP模拟赛
  • string
    • 思路
    • 代码
  • matrix
    • 思路
    • 代码
  • big
    • 思路
    • 代码

string

思路

• 这是我练线段树时做过的一道题（CF上的...），非常巧妙；
• 考虑字母只有$26$个，我们使用[计数排序][1]进行处理；
• 建一棵线段树，每个节点维护这个区间里每种字母的个数，同时还有一个$tag$表示还没有将子区间排序（$tag$正负代表升序或降序）；
• 每次对一个区间排序时，我们先对整个区间的字母个数统计出来；
• 之后，我们从左到右对小区间（即操作区间在线段树上被分成的$O(\log n)$段）进行修改就好了；
• 输出时遍历一遍，把$tag$都推下去就好了，复杂度$O(26(n+m)\log 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 <cstring>
const int MAXN=100005;
int n;
char s[MAXN];
class segT{
    private:
        struct data{
            int tag;
            int c[26];
            void clear(){
                tag=0;
                memset(c,0,sizeof(c));
            }
            data(){clear();}
            int& operator [](int i){return c[i];}
            void operator ()(int cnt,data &that){
                clear();
                tag=that.tag;
                //1 up,-1 dwn
                for(int i= tag>0 ? 0:25;0<=i && i<26;i+=tag){
                    if(that[i]>=cnt){
                        c[i]=cnt;
                        that[i]-=cnt;
                        return;
                    }
                    else{
                        c[i]=that[i];
                        cnt-=that[i];
                        that[i]=0;
                    }
                }
            }
            data operator +(const data &that)const{
                data ret;
                for(int i=0;i<26;++i)
                    ret[i]=c[i]+that.c[i];
                return ret;
            }
            data& operator +=(const data &that){
                *this=*this+that;
                return *this;
            }
        };
        struct node{
            int l,r,ls,rs;
            data c;
            int len(){return r-l+1;}
        }d[MAXN<<2];
        int new_nd(){
            static int cnt=1;
            return ++cnt;
        }
        void upd(int u){
            d[u].c=d[d[u].ls].c+d[d[u].rs].c;
        }
        void push_d(int u){
            if(!d[u].c.tag) return;
            int ls=d[u].ls,rs=d[u].rs;
            data tmp=d[u].c;
            d[ls].c(d[ls].len(),tmp);
            d[rs].c(d[rs].len(),tmp);
            d[u].c.tag=0;
        }
        data qry(int u,int lp,int rp){
            if(lp<=d[u].l && d[u].r<=rp)
                return d[u].c;
            push_d(u);
            int mid=d[u].l+d[u].r>>1;
            data ret;
            if(lp<=mid) ret=qry(d[u].ls,lp,rp);
            if(rp>mid) ret+=qry(d[u].rs,lp,rp);
            return ret;
        }
        void mdf(int u,int lp,int rp,data &sum){
            if(lp<=d[u].l && d[u].r<=rp){
                d[u].c(d[u].len(),sum);
                return;
            }
            push_d(u);
            int mid=d[u].l+d[u].r>>1;
            if(lp<=mid) mdf(d[u].ls,lp,rp,sum);
            if(rp>mid) mdf(d[u].rs,lp,rp,sum);
            upd(u);
        }
        void prt(int u){
            if(d[u].l==d[u].r){
                for(int i=0;i<26;++i){
                    if(d[u].c[i]){
                        s[d[u].l]=i+'a';
                        return;
                    }
                }
            }
            push_d(u);
            int mid=d[u].l+d[u].r>>1;
            prt(d[u].ls),prt(d[u].rs);
        }
        void build(int u,int l,int r){
            d[u].l=l,d[u].r=r;
            if(l==r){
                d[u].c[s[l]-'a']=1;
                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 sort(int lp,int rp,int type){
            type= type ? 1:-1;
            data sum=qry(1,lp,rp);
            sum.tag=type;
            mdf(1,lp,rp,sum);
        }
        void prt(){prt(1);}
}T;
int main(){
    setIO("string");
    int m;
    read(n),read(m);
    scanf("%s",s+1);
    T.build();
    for(int i=1,l,r,type;i<=m;++i){
        read(l),read(r),read(type);
        T.sort(l,r,type);
    }
    T.prt();
    printf("%s",s+1);
    return 0;
}

matrix

思路

• 这是一个神奇的DP题。。。我看了半天；
• 考虑按列做会好处理一些（每列最多一个$1$）；
• 设$dp(i,j)$表示处理了前$i$列，其中有$j$列是某些行的右区间范围内的，并且这$j$列都放了$1$的总合法方案数；
• 那么，$dp(i,j)$可以从$dp(i-1,j)$和$dp(i-1,j-1)$转移，其中$dp(i-1,j-1)$转移来就是在$cntr_i$里剩下的部分选一列放$1$（有$j-1$列已经放过了），$cntr_i$是前$i$列里有多少个右区间端点；
• 而每次如果第$i$列有左区间的端点，那么我们就要在$last\_l_i$~$i$之间选一列在这一行放$1$，我们枚举一下$j$乘一下方案就好了；
• 反正这题我要仔细想好久才能明白╮(╯_╰)╭

代码

#include <cstdio>
const int MAXN=3005,P=998244353;
int n,m;
int l[MAXN],r[MAXN],prel[MAXN],prer[MAXN];
inline int DP(){
    static int dp[MAXN][MAXN];
    dp[0][0]=1;
    for(int i=1;i<=m;++i){
        dp[i][0]=dp[i-1][0];
        for(int j=1;j<=i && prer[i]>=j-1;++j)
            dp[i][j]=(dp[i-1][j]+(long long)dp[i-1][j-1]*(prer[i]-(j-1))%P)%P;
        for(int j=prel[i-1];j<prel[i];++j){
            for(int k=0;k+j<=i;++k)
                dp[i][k]=(long long)dp[i][k]*(i-j-k)%P;
        }
    }
    return dp[m][n];
}
int main(){
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&l[i],&r[i]);
        ++prel[l[i]],++prer[r[i]];
    }
    for(int i=1;i<=m;++i){
        prel[i]+=prel[i-1];
        prer[i]+=prer[i-1];
    }
    printf("%d",DP());
    return 0;
}

big

思路

• 那个奇怪的操作写成位运算就明白了：
  $$(a<<1>>n)+(a<<1)\&(1<<n)-1\\ eg. n=7时:\\ \begin{eqnarray*} 1010110_2 &\to& 1_2+10101100_2\\ &\to& 10101101_2\\ &\to& 0101101_2 \end{eqnarray*}$$
• 就是将$a$的二进制下最高位（第$n$位）移到最后一位；
• 考虑异或运算每一位独立，所以我们选的数$x$可以先不管，即倒推，先求出$a_1 \bigoplus a_2 \bigoplus\cdots\bigoplus a_m$（中间又一次这个神奇操作）的结果$y$，然后我们构造一个$x$，使$x \bigoplus y$最大；
• 由于有对手的存在，我们枚举$m+1$种操作时间下的$y$，加到01字典树里；
• 接着我们遍历求解，如果一个节点$u$有两个儿子，那么意味着对手可以通过一次合适的操作在这一位上产生两种结果，那么对手一定可以进行操作使我们这一位为$0$，反之如果只有一个儿子，我们提前就可以构造使$x$这一位最终为$1$；
• 于是这样遍历统计答案即可，复杂度$O(nm)$。

代码

#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>
#include <functional>
using std::sort;
using std::greater;
const int MAXM=100005,MAXN=30;
int n,m;
int a[MAXM],xor_suf[MAXM],ans[MAXM];
class Trie{
    private:
        int c[MAXM*MAXN][2];
        int new_nd(){
            static int cnt;
            return ++cnt;
        }
        void trans(int u,int step,int num){
            if(step<0){
                ans[++ans[0]]=num;
                return;
            }
            if(!c[u][0] && c[u][1])
                trans(c[u][1],step-1,num|1<<step);
            else if(!c[u][1] && c[u][0])
                trans(c[u][0],step-1,num|1<<step);
            else if(c[u][0] && c[u][1]){
                trans(c[u][0],step-1,num);
                trans(c[u][1],step-1,num);
            }
        }
    public:
        void ist(int x){
            for(int u=0,i=n-1;i>=0;--i){
                if(!c[u][(bool)(x&1<<i)])
                    c[u][(bool)(x&1<<i)]=new_nd();
                u=c[u][(bool)(x&1<<i)];
            }
        }
        void trans(){trans(0,n-1,0);}
}T;
int main(){
    setIO("big");
    read(n),read(m);
    for(int i=1;i<=m;++i)
        read(a[i]);
    for(int i=m;i;--i)
        xor_suf[i]=a[i]^xor_suf[i+1];
    for(int i=0,xor_pre=0;i<=m;++i){
        xor_pre^=a[i];
        T.ist((xor_pre<<1>>n)+(xor_pre<<1)&(1<<n)-1^xor_suf[i+1]);
    }
    T.trans();
    sort(ans+1,ans+ans[0]+1,greater<int>());
    write(ans[1],'\n');
    int cnt=0;
    for(int i=1;ans[i]==ans[1] && i<=ans[0];++i)
        ++cnt;
    write(cnt);
    return 0;
}