2017.9.23 NOIP模拟赛

题解 套题

NOIP出啥主席树...

目录

• 2017.9.23 NOIP模拟赛
  • 平均数
    • 思路
    • 代码
  • 涂色游戏
    • 思路
    • 代码
  • 序列
    • 思路
    • 代码

平均数

思路

• 考虑到直接求不太现实，我们二分答案，那么只需考虑怎么验证；
• 显然，将每个$a_i$减去二分的答案$mid$后，若和小于$0$的连续子序列有$t$个，则说明$mid$是第$t$小的平均值；
• 现在只需要快速求出和非负的连续子序列个数就行了；
• 设$sum$为操作后$a$的前缀和，显然$\sum_{i=l}^r a_i \geq 0 \iff sum_r \geq sum_{l-1}$，右边的不等式很像什么？对，逆序对！；
• 所以，我们二分答案，之后求一下前缀和的逆序对即可验证，但是由于树状数组需要离散化，常数太大会T，需要用归并排序...

代码

#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstring>
using std::min;
using std::max;
const int MAXN=100005;
const double EPS=1e-5;
int n;
int a[MAXN];
long long k;
double sum[MAXN];
inline void pre_sum(double k){
    sum[0]=0;
    for(int i=1;i<=n;++i)
        sum[i]=sum[i-1]+a[i]-k;
}
template<typename type>
long long mge_sort(int l,int r,type a[]){
    static type tmp[MAXN];
    if(l==r) return 0;
    int mid=l+r>>1;
    long long ret=mge_sort(l,mid,a)+mge_sort(mid+1,r,a);
    int cur=l-1,lp=l,rp=mid+1;
    while(lp<=mid && rp<=r){
        if(a[lp]>a[rp]){
            tmp[++cur]=a[rp++];
            ret+=mid-lp+1;
        }
        else tmp[++cur]=a[lp++];
    }
    while(lp<=mid) tmp[++cur]=a[lp++];
    while(rp<=r) tmp[++cur]=a[rp++];
    memcpy(a+l,tmp+l,(r-l+1)*sizeof(type));
    return ret;
}
inline long long notp_cnt(){return mge_sort(0,n,sum);}
inline double bin_chop(double l,double r){
    double mid;
    while(r-l>EPS){
        mid=(l+r)/2;
        pre_sum(mid);
        if(notp_cnt()>=k) r=mid;
        else l=mid;
    }
    return (l+r)/2;
}
int main(){
    freopen("ave.in","r",stdin);
    freopen("ave.out","w",stdout);
    scanf("%d%lld",&n,&k);
    int l=INT_MAX,r=INT_MIN;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        l=min(l,a[i]),r=max(r,a[i]);
    }
    printf("%.4lf",bin_chop(l,r));
    return 0;
}

涂色游戏

思路

• 显然组合数学递推。。。
• 考虑逐列递推，因为转移只需考虑前一列有哪些颜色，所以设$g(i,j)$为第$i$列有$j$种颜色时，前$i$列总共的合法方案数；
• 那么我们还需要知道第$i$列有哪些颜色才行，因为需要满足第$i+1$列的颜色与其的并集大小不小于$q$；
• 显然，直接记录不太现实，我们先考虑另一个递推式$f(n,j)$，表示$n$个方格染$j$种颜色的排列数；
• 这样，对于每种$j$个颜色的组合，它对应的排列数有$\frac{f(n,j)}{C_p^j}$种；
• 考虑枚举第$i$与$i+1$列颜色并集大小，则对应的第$i+1$列种数有:
  $$\sum_{k=1}^p \sum_{l= \max(q,j,k)}^{\min(p,j+k)} C_{j}^{j+k-l}\times C_{p-j}^{l-j}\times\frac{f(n,k)}{C_p^k}$$
• 设这个为$trans(j,k)$，这样我们可以把它理解为一个邻接矩阵，$trans(i,j)$即为由有$i$种颜色的列转移到有$j$种颜色的列的方案数；
• 考虑到我们要转移$m-1$次，所以用矩阵快速幂优化求$trans^{m-1}$即可，最后我们还要将$trans^{m-1}(i,j)$乘上第一列初始方案数，即$f(n,i)$，由于我们统计的都是合法状态，所以直接求和即可；
• 现在，唯一的一个问题是求$f(n,i)$，这个显然递推；
• 考虑推广$f(n,i)$至$f(j,i)$，即有$j$个格子，染$i$种颜色的排列；
• 则转移有两种方式：
  $$f(j,i)=f(j-1,i)\times i+f(j-1,i-1)\times(p-i+1)$$
• 于是总复杂度为$O(p^3+p^2 \log m)$。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using std::max;
const int MAXN=105,P=998244353;
int n,m,p,q;
int f[MAXN][MAXN],C[MAXN][MAXN];
struct matrix{
    int c[MAXN][MAXN];
    matrix(){memset(c,0,sizeof(c));}
    int* operator[] (int i){return c[i];}
    matrix& operator*= (matrix a){
        matrix b=*this;
        memset(c,0,sizeof(c));
        for(int i=1;i<=p;++i){
            for(int j=1;j<=p;++j){
                for(int k=1;k<=p;++k)
                    c[i][j]=(c[i][j]+(long long)a[i][k]*b[k][j]%P)%P;
            }
        }
        return *this;
    }
    void be_unit(){
        for(int i=1;i<=p;++i)
            c[i][i]=1;
    }
}ans,trans;
inline int pow(int x,int y){
    int ret=1;
    for(;y;y>>=1,x=(long long)x*x%P){
        if(y&1) ret=(long long)ret*x%P;
    }
    return ret;
}
inline int inv(int x){return pow(x,P-2);}
inline matrix pow(matrix x,int y){
    matrix ret;
    ret.be_unit();
    for(;y;y>>=1,x*=x){
        if(y&1) ret*=x;
    }
    return ret;
}
inline void pre_tab(){
    C[0][0]=1;
    for(int i=1;i<=p;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
    }
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=p;++j)
            f[i][j]=((long long)f[i-1][j-1]*(p-j+1)%P+(long long)f[i-1][j]*j%P)%P;
    }
}
inline void deal_mat(){
    for(int i=1;i<=p;++i){
        for(int j=1;j<=p;++j){
            for(int k=max(q,max(i,j));k<=p;++k)
                trans[i][j]=(trans[i][j]+(long long)C[i][i+j-k]*C[p-i][k-i]%P)%P;
            trans[i][j]=(long long)trans[i][j]*f[n][j]%P*inv(C[p][j])%P;
        }
    }
    ans=pow(trans,m-1);
}
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&p,&q);
    pre_tab();
    deal_mat();
    int sum=0;
    for(int i=1;i<=p;++i){
        for(int j=1;j<=p;++j)
            sum=(sum+(long long)f[n][i]*ans[i][j]%P)%P;
    }
    printf("%d",sum);
    return 0;
}

序列

思路

• 乍一看显然主席树，但是，后来没修改一次就要回答一下所有询问，这个怎么办呢？
• 每次都算一遍就成暴力了，自然不现实，我们不如考虑先算出初始的$ans$，而后每次修改时更新好了；
• 考虑怎么更新，因为修改某个数的值只会影响到改在这个位置上的区间的询问，且影响的是询问的值在这个数的原值和新值之间的那部分，所以我们可以再建一颗主席树维护询问；
• 我们按询问的值作为不同版本，将每次询问的$l,r$在这个版本上区间加（当然不用打tag，我们查询某个点上覆盖的区间数只用一直向下遍历，就能不重不漏了）；
• 这样，每次修改某个值，若原值更大，则$ans$减去询问中值在新旧值之间且覆盖该位置的询问数，反之亦然，复杂度就是静态主席树的复杂度$O(n \log n)$。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using std::sort;
const int MAXN=100005;
int n,m,q;
int a[MAXN];
struct query{
    int l,r,x;
    friend bool operator< (const query &a,const query &b){
        return a.x<b.x;
    }
}qry[MAXN];
class CMT{
    private:
        int cnt;
        int rt[MAXN];
        struct node{int ls,rs,cnt;}d[MAXN*50];
        int cpy_nd(int u){
            d[++cnt]=d[u];
            return cnt;
        }
        void sgl_mdf(int pre,int &now,int l,int r,int val,int x){
            now=cpy_nd(pre);
            d[now].cnt+=x;
            if(l==r) return;
            int mid=l+r>>1;
            if(val<=mid) sgl_mdf(d[pre].ls,d[now].ls,l,mid,val,x);
            else sgl_mdf(d[pre].rs,d[now].rs,mid+1,r,val,x);
        }
        void rge_mdf(int pre,int &now,int l,int r,int lp,int rp,int x){
            now=cpy_nd(pre);
            if(lp<=l && r<=rp){
                d[now].cnt+=x;
                return;
            }
            int mid=l+r>>1;
            if(lp<=mid) rge_mdf(d[pre].ls,d[now].ls,l,mid,lp,rp,x);
            if(rp>mid) rge_mdf(d[pre].rs,d[now].rs,mid+1,r,lp,rp,x);
        }
        long long geq_cnt(int pre,int now,int l,int r,int val){
            if(val<=l) return d[now].cnt-d[pre].cnt;
            int mid=l+r>>1;
            long long ret=0;
            if(val<=mid) ret+=geq_cnt(d[pre].ls,d[now].ls,l,mid,val);
            if(val<=r) ret+=geq_cnt(d[pre].rs,d[now].rs,mid+1,r,val);
            return ret;
        }
        long long qry(int pre,int now,int l,int r,int val){
            if(l==r) return d[now].cnt-d[pre].cnt;
            int mid=l+r>>1;
            long long ret=d[now].cnt-d[pre].cnt;
            if(val<=mid) ret+=qry(d[pre].ls,d[now].ls,l,mid,val);
            else ret+=qry(d[pre].rs,d[now].rs,mid+1,r,val);
            return ret;
        }
    public:
        void clear(){
            cnt=0;
            memset(rt,0,sizeof(rt));
            memset(d,0,sizeof(d));
        }
        void ist(int pre,int now,int val){sgl_mdf(rt[pre],rt[now],1,n,val,1);}
        void ist(int pre,int now,int lp,int rp){rge_mdf(rt[pre],rt[now],1,n,lp,rp,1);}
        long long geq_cnt(int l,int r,int val){return geq_cnt(rt[l-1],rt[r],1,n,val);}
        long long qry(int l,int r,int val){return qry(rt[l-1],rt[r],1,n,val);}
        void cpy_his(int pre,int now){rt[now]=rt[pre];}
}T;
inline void deal_qry(){
    T.clear();
    sort(qry+1,qry+m+1);
    for(int i=1,j=1;i<=n;++i){
        T.cpy_his(i-1,i);
        while(qry[j].x==i && j<=m){
            T.ist(i,i,qry[j].l,qry[j].r);
            ++j;
        }
    }
}
int main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        T.ist(i-1,i,a[i]);
    }
    long long ans=0;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&qry[i].l,&qry[i].r,&qry[i].x);
        ans+=T.geq_cnt(qry[i].l,qry[i].r,qry[i].x);
    }
    printf("%lld\n",ans);
    deal_qry();
    long long p,v;
    for(int i=1;i<=q;++i){
        scanf("%lld%lld",&p,&v);
        p^=ans,v^=ans;
        if(a[p]<v) ans+=T.qry(a[p]+1,v,p);
        else if(a[p]>v) ans-=T.qry(v+1,a[p],p);
        a[p]=v;
        printf("%lld\n",ans);
    }
    return 0;
}