目录

---

2018.3.18 Test

时间：3.5h

得分：太zz不写了(T3 60暴力分就我没看。。)

T1 BZOJ.4868.[六省联考2017]期末考试

/*所有人都只与最大的bi有关系啊！所以可以枚举bi，现在就是计算选在bi这天 所有人等待的值、调整老师的值 第一部分显然可以直接递推啊，每过一天加上这天之前的人数 调整老师只需要看一下A与B，以及之前有多少bj可以和后面大的bk补 注意C很大的话特判一下(肯定不会有C的贡献)，否则人数*C爆longlong(unsigned longlong也能水过去？) */#include 
    
     #include 
     
      #include 
      
       #define gc() getchar()typedef long long LL;const int N=1e5+5;int n,m,tm[N],b[N],num[N],sum[N];LL A,B,C,pre[N],suf[N];inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}inline LL readll(){    LL now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}int main(){//  freopen("exam.in","r",stdin);//  freopen("exam.out","w",stdout);    A=read(),B=read(),C=readll(),m=read(),n=read();//n,m    int Max=0,Min=1e9;    for(int i=1; i<=m; ++i) tm[i]=read(),++num[tm[i]];    for(int i=1; i<=n; ++i) b[i]=read(),++sum[b[i]];    for(int i=1; i<=m; ++i) Min=std::min(Min,tm[i]),Max=std::max(Max,tm[i]);    for(int i=1; i<=n; ++i) Min=std::min(Min,b[i]),Max=std::max(Max,b[i]);    LL now=0;    for(int i=1; i<=Max; ++i) pre[i]=pre[i-1]+now, now+=sum[i];    now=0;    for(int i=Max; i; --i) suf[i]=suf[i+1]+now, now+=sum[i];    if(C==1e16)    {        Min=1e9;        for(int i=1; i<=m; ++i) Min=std::min(Min,tm[i]);        LL tmp;        if(A>=B) printf("%lld",B*suf[Min]);        else tmp=std::max(suf[Min]-pre[Min],0ll),printf("%lld",A*std::min(pre[Min],suf[Min])+B*tmp);        return 0;    }    LL res=1e15,tmp,peo=0; now=0;    for(int i=Min; i<=Max; ++i)    {        peo+=now;        if(A>=B) res=std::min(res,C*peo+B*suf[i]);        else tmp=std::max(suf[i]-pre[i],0ll),res=std::min(res,C*peo+A*std::min(pre[i],suf[i])+B*tmp);        now+=num[i];    }    printf("%lld",res);    return 0;}
      
     
    

T2

过段时间再写

T3 BZOJ.4870.[六省联考2017]组合数问题(DP 矩阵快速幂)

/*O(nk)可以直接递推60分，但不要被这个限制！题目所求仍然可以用组合数的定义描述，即在nk个物品中选模k等于r个物品的方案数，我们记为F(nk,r)。那么类似于组合数的C(n,m)=C(n-1,m-1)+C(n-1,m)，F(n,m)=F(n-1,(m-1+k)%k)+F(n-1,m).于是就可以用DP O(nk)做。注意到这是个线性递推式，可以用矩阵快速幂优化。具体: 把k做矩阵大小，元素F(i)看做一行k列的矩阵，要满足 F(i-1)*A[]=F(i)，不难得出当f[i-1][j]可转到f[i][k]时，A[j][k]=1 另外很容易爆longlong,直接开longlong吧 K=1时应是++A[K-1][0]而不是A[0][0]=1直接赋值。。*/#include 
    
     typedef long long LL;const int N=1e6+5;int n,p,K,r;struct Matrix{    LL A[53][53];    Matrix operator *(const Matrix a)const    {        Matrix res;        for(int i=0; i
     
      >=1,x=x*x)        if(k&1) t=t*x;    return t;}int main(){    scanf("%d%d%d%d",&n,&p,&K,&r);    for(int i=0; i
     
    

另一个做法：

/*还是DP，注意到F(2n,(i+j)%K)=F(n,i)*F(n,j),我们直接对DP数组快速幂(倍增)即可 复杂度O(k^2logn) */#include 
    
     #include 
     
      typedef long long LL;const int N=1e6+5;int n,p,K,r;struct Array{    LL A[53];    void Clear(){        memset(A,0,sizeof A);    }}F,tmp;void Mult(Array &res,Array a,Array b){    res.Clear();    for(int i=0; i
      
       >=1,Mult(tmp,tmp,tmp))        if(k&1) Mult(F,F,tmp);    printf("%lld",F.A[r]);    return 0;}
      
     
    

总结

T1 太费时间了。。正解思路很简单但一直没在正道上，关键的地方没重视。

T2 快速幂一看题目实际不能直接取模，就把取模删掉了。。mdzz。。然后20分暴力就没了。

T3 60暴力没写不说什么。。要注意转换思路，从组合数最本身的定义去考虑。

考试代码

T1

好像很厉害的暴力线段树+瞎贪心 70分

#include 
    
     #include 
     
      #include 
      
       #include 
       
        //#define gc() getchar()#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long LL;const int N=1e5+5,MAXIN=5e5;int n,m,A,B,tm[N],b[N],q[N],tt[N];LL C;char IN[MAXIN],*SS=IN,*TT=IN;struct Seg_Tree{    int mx[N<<2],mn[N<<2],tag[N<<2],sz[N<<2];    inline void PushUp(int rt)    {        mn[rt]=std::min(mn[rt<<1],mn[rt<<1|1]);        mx[rt]=std::max(mx[rt<<1],mx[rt<<1|1]);    }    inline void PushDown(int rt)    {        mn[rt<<1]+=tag[rt], mn[rt<<1|1]+=tag[rt];        mx[rt<<1]+=tag[rt], mx[rt<<1|1]+=tag[rt];        tag[rt<<1]+=tag[rt], tag[rt<<1|1]+=tag[rt];        tag[rt]=0;    }    void Build(int l,int r,int rt)    {        if(l==r) mx[rt]=mn[rt]=b[l], sz[rt]=1;        else        {            int m=l+r>>1;            Build(lson), Build(rson);            sz[rt]=sz[rt<<1]+sz[rt<<1|1], PushUp(rt);        }    }    int Query_Max_Num(int l,int r,int rt,int v)    {        if(l==r) return mx[rt]>=v;        if(tag[rt]) PushDown(rt);        int m=l+r>>1;        if(mn[rt<<1|1]>=v) return sz[rt<<1|1]+Query_Max_Num(lson,v);        return Query_Max_Num(rson,v);    }    int Query_Min_Num(int l,int r,int rt,int v)    {        if(l==r) return mx[rt]<=v;        if(tag[rt]) PushDown(rt);        int m=l+r>>1;        if(mx[rt<<1]<=v) return sz[rt<<1]+Query_Min_Num(rson,v);        return Query_Min_Num(lson,v);    }    void Modify(int l,int r,int rt,int L,int R,int v)    {        if(L<=l&&r<=R) tag[rt]+=v,mn[rt]+=v,mx[rt]+=v;        else        {            if(tag[rt]) PushDown(rt);            int m=l+r>>1;            if(L<=m) Modify(lson,L,R,v);            if(m
        
         >1;//          Print(l,m,rt<<1), printf("%d~%d %d:mn:%d mx:%d\n",l,r,rt,mn[rt],mx[rt]), Print(m+1,r,rt<<1|1);//      }//  }//  void Debug()//  {//      putchar('\n');//      Print(1,n,1);//      putchar('\n');//  }}t;inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}inline LL readll(){    LL now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}int Find(int x){    int l=0,r=m,mid,res=0;    while(l<=r)        if(tm[mid=l+r>>1]>=x) r=mid-1;        else res=mid,l=mid+1;    return res;}//#define D t.Debug()//#define D b[0]=0LL Can(){    int cnt=t.Query_Max_Num(1,n,1,t.mx[1]),k=Find(t.mx[1]),cnt2,k2;    LL cost1=1ll*B*cnt, cost2=1ll*A*cnt;//  printf("cnt:%d k:%d c1:%I64d c2:%I64d c:%I64d\n",cnt,k,cost1,cost2,1ll*k*C);    if(cost2>=cost1)    {        t.Modify(1,n,1,n-cnt+1,n,-1);        return 1ll*k*C-cost1;    }    int tmp=cnt,tot=0;    while((cnt2=t.Query_Min_Num(1,n,1,t.mn[1]))<=tmp&&cost2<=cost1)    {        tmp-=cnt2, k2=Find(t.mn[1]), cost2+=1ll*k2*C;        t.Modify(1,n,1,1,cnt2,1), q[++tot]=cnt2;    }    if(tmp) cnt2=t.Query_Min_Num(1,n,1,t.mn[1]), cost2+=1ll*tmp*C, t.Modify(1,n,1,cnt2-tmp+1,cnt2,1);    if(cost1<=cost2)    {        for(int i=1; i<=tot; ++i) t.Modify(1,n,1,1,q[i],-1);        if(tmp) t.Modify(1,n,1,cnt2-tmp+1,cnt2,-1);        t.Modify(1,n,1,n-cnt+1,n,-1);        return 1ll*k*C-cost1;    }    t.Modify(1,n,1,n-cnt+1,n,-1);    return 1ll*k*C-cost2;}LL Solve(int x){    LL res=0;    int cnt1=0,cnt2=0,tmp;    for(int i=1; i<=m; ++i)        if(tm[i]
         
          x) cnt2+=b[i]-x; else cnt1+=x-b[i]; if(A
          
           tt[mx1]) mx1=b[i]; else if(tt[b[i]]>tt[mx2]) mx2=b[i]; adj/=n; int lim=std::min(5000000/n,b[n]-adj); LL res=0,tmp; for(int i=1; i<=m; ++i) if(tm[i]
           
            =0) res-=tmp; for(int i=std::max(adj-lim,0); i<=adj+lim; ++i) { res=std::min(res,Solve(i)); if(clock()-tim>950) {printf("%I64d",res); return 0;} } res=std::min(res,std::min(Solve(mx1),Solve(mx2))); printf("%I64d",res); return 0;}/*100 100 24 55 1 2 31 1 2 3 3*/
           
          
         
        
       
      
     
    

T2

半小时写啥啊。。

#include 
    
     #include 
     
      #include 
      
       //#define gc() getchar()#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long LL;const int N=5e4+5,MAXIN=2e5;int n,m,p,c;LL A[N],pw[233];char IN[MAXIN],*SS=IN,*TT=IN;struct Ques{    int type,l,r;}q[N];struct Seg_Tree{    int sum[N<<2],tag[N<<2];    inline void PushUp(int rt)    {        sum[rt]=sum[rt<<1]+sum[rt<<1|1], sum[rt]>=p?sum[rt]-=p:0;    }    inline void PushDown(int rt)    {                tag[rt]=0;    }    void Build(int l,int r,int rt)    {        if(l==r) sum[rt]=A[l];        else        {            int m=l+r>>1;            Build(lson), Build(rson);            PushUp(rt);        }    }    void Build2(int l,int r,int rt)    {        if(l==r) sum[rt]=A[l]&1;        else        {            int m=l+r>>1;            Build2(lson), Build2(rson);            PushUp(rt);        }    }    int Query_Sum(int l,int r,int rt,int L,int R)    {        if(L<=l && r<=R) return sum[rt]%p;        int m=l+r>>1;        if(L<=m)            if(m
       
        0;        int m=l+r>>1;        if(L<=m)            if(m
        
         >1;            if(L<=m) Modify(lson,L,R,v);            if(m
         
          >=1,x=x*x) if(k&1) t=t*x; return t;}void Spec1(){ pw[0]=1, pw[1]=c, pw[2]=c*c, pw[3]=pw[2]*c, pw[4]=pw[3]*c; for(int i=1; i<=4; ++i) pw[i]%=p; t.Build2(1,n,1); int type,l,r; if(c&1) { while(m--) { type=read(),l=read(),r=read(); if(type) printf("%d\n",r-l+1-t.Query_Sum2(1,n,1,l,r)); else t.Modify(1,n,1,l,r,-1); } } else { while(m--) { type=read(),l=read(),r=read(); if(type) printf("%d\n",r-l+1-t.Query_Sum2(1,n,1,l,r)); else t.Modify(1,n,1,l,r,1); } } }void Spec2(){ int type,l,r; while(m--) { type=read(),l=read(),r=read(); if(type) { LL res=0; for(int i=l; i<=r; ++i) res+=A[i]; printf("%I64d\n",res%p); } else for(int i=l; i<=r; ++i) A[i]=FP(c,A[i]); }}void Spec3(){ for(int i=1; i<=m; ++i) { if(q[i].type) printf("%d\n",t.Query_Sum(1,n,1,q[i].l,q[i].r)); else t.Modify(1,n,1,q[i].l,q[i].r,-A[q[i].l]), t.Modify(1,n,1,q[i].l,q[i].r,A[q[i].l]=FP(c,A[q[i].l])); }}int main(){ freopen("verbinden.in","r",stdin); freopen("verbinden.out","w",stdout); n=read(),m=read(),p=read(),c=read(); for(int i=1; i<=n; ++i) A[i]=read(); if(p<=4) {Spec1(); return 0;} if(1ll*m*n<=10000000) {Spec2(); return 0;} t.Build(1,n,1); for(int i=1; i<=m; ++i) q[i].type=read(),q[i].l=read(),q[i].r=read(); bool f1=1,f2=1; for(int i=1; i<=m; ++i) if(!q[i].type) {f1=0; break;} if(f1) {Spec3(); return 0;} for(int i=1; i<=m; ++i) if(!q[i].type && q[i].l!=q[i].r) {f2=0; break;} if(f2) {Spec3(); return 0;} puts("2018,Bless All."); return 0;}
         
        
       
      
     
    

T3

补暴力：

#include 
    
     typedef long long LL;const int N=1e6+5;int n,p,k,r;void Exgcd(LL a,LL b,LL &x,LL &y){    if(!b) x=1ll,y=0ll;    else Exgcd(b,a%b,y,x),y-=a/b*x;}LL inv(LL a){    LL x,y; Exgcd(a,p,x,y);    return (x%p+p)%p;}int main(){//  freopen("problem.in","r",stdin);//  freopen("problem.out","w",stdout);    scanf("%d%d%d%d",&n,&p,&k,&r);    if(1ll*n*k<=1e7)    {        LL C=1,res=(r==0),nk=1ll*n*k;        for(int i=1; i<=nk; ++i)        {            C=C*(nk-i+1)%p*inv(i)%p;            if(!((i-r)%k)) res+=C,res>=p?res-=p:0;        }        printf("%lld",res);        return 0;    }    return 0;}