首页 > 代码库 > [SDOI2016Round1]解题报告

[SDOI2016Round1]解题报告

2024-11-20 23:11:02   202人阅读

Day1<script type="math/tex" id="MathJax-Element-1">Day 1</script>

T1：<script type="math/tex" id="MathJax-Element-2">T1：</script>

题意：求∑n?1i=0∑m?1j=0max((i xor j)?k，0)<script type="math/tex" id="MathJax-Element-3">\sum_{i=0}^{n-1}\sum_{j=0}^{m-1}max((i\ xor\ j)-k。0)</script>
由于是抑或操作。每一位都是独立的，所以能够一位一位的算贡献。


f[i][a][b][c]<script type="math/tex" id="MathJax-Element-4">f[i][a][b][c]</script>表示第i位时。每一个数跟n,m,k<script type="math/tex" id="MathJax-Element-5">n,m,k</script>的大小关系。0表示小于，1表示i位之前都相等，2表示大于。转移的时候美剧当前这一位的数是什么。从高位向低位转移即可了。


复杂度是O(nlogn)<script type="math/tex" id="MathJax-Element-6">O(nlogn)</script>
code:<script type="math/tex" id="MathJax-Element-7">code:</script>

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long 
const int N=100;
int T,Mod,ni[N],mi[N],ki[N],len;
LL n,m,K,f[N][2][2][3],g[N][2][2][3];
inline void calc(){
    int i,a,b,c,o0,o1,x,y,z,o;
    g[0][1][1][1]=1;
    for(i=0;i<len;++i)
      for(a=0;a<=1;++a)
        for(b=0;b<=1;++b)
          for(c=0;c<=2;++c)
            if(f[i][a][b][c]+g[i][a][b][c])
              for(o0=0;o0<=1;++o0){
                if(a){
                    if(o0>ni[i+1]) continue;
                    if(o0==ni[i+1]) x=1;
                    if(o0<ni[i+1]) x=0;
                }
                else x=0;
                for(o1=0;o1<=1;++o1){
                    if(b){
                        if(o1>mi[i+1]) continue;
                        if(o1==mi[i+1]) y=1;
                        if(o1<mi[i+1]) y=0;
                    }
                    else y=0;
                    o=o0^o1;
                    if(c==0||c==2) z=c;
                    if(c==1){
                        if(o>ki[i+1]) z=2;
                        if(o==ki[i+1]) z=1;
                        if(o<ki[i+1]) z=0;
                    }
                    g[i+1][x][y][z]=(g[i+1][x][y][z]+g[i][a][b][c])%Mod;
                    f[i+1][x][y][z]=(f[i+1][x][y][z]+f[i][a][b][c]*2LL+g[i][a][b][c]*(LL)o)%Mod;
                }
              }
}
int main(){
    scanf("%d",&T);
    while(T--){
        LL x;
        int i;
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        memset(ni,0,sizeof(ni));
        memset(mi,0,sizeof(mi));
        memset(ki,0,sizeof(ki));
        scanf("%lld%lld%lld%d",&n,&m,&K,&Mod);
        for(x=n;x;x>>=1) ni[++ni[0]]=x&1LL;
        for(x=m;x;x>>=1) mi[++mi[0]]=x&1LL;
        for(x=K;x;x>>=1) ki[++ki[0]]=x&1LL; 
        len=max(ni[0],max(mi[0],ki[0]));
        for(i=1;i<=(len>>1);++i){
            swap(ni[i],ni[len-i+1]);
            swap(mi[i],mi[len-i+1]);
            swap(ki[i],ki[len-i+1]);
        }
        calc();
        printf("%lld\n",(f[len][0][0][2]-(K%Mod*g[len][0][0][2])%Mod+Mod)%Mod);
    }
}

T2：<script type="math/tex" id="MathJax-Element-8">T2：</script>

题意：给出n种数字，第i个是ai，个数是bi，权值是ci。假设ai|aj<script type="math/tex" id="MathJax-Element-9">ai|aj</script>并且aiaj<script type="math/tex" id="MathJax-Element-10">\frac{ai}{aj}</script>是一个质数，那么这两个数字就能获得ci?cj<script type="math/tex" id="MathJax-Element-11">ci*cj</script>的价值，要求总价值不小于0的情况下求最多的配对数。


配对关系是一个二分图，所以建出费用流的图来，当跑到费用小于0的时候，处理一下当前的流量。退出即可了。
code:<script type="math/tex" id="MathJax-Element-12">code:</script>

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define T n+2
#define D 795
#define LL long long 
#define inf 1000000000
#define INF 10000000000000LL
const int N=800;
const int M=100000;
const int O=2000000;
bool flag[M+10],use[N],f[N];
struct S{int st,en,va;LL co;}aa[O];
int n,a[N],b[N],c[N],prime[M+10],d[N],va,point[N],pre[N],next[O],map[N][N],tot=1,co[N];
int l[N],to[N];
LL dis[N];
inline void prepare(){
    int i,j;
    for(i=2;i<=M;++i){
        if(!flag[i]) prime[++prime[0]]=i;
        for(j=1;j<=prime[0]&&i*prime[j]<=M;++j){
            flag[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}
inline void add(int x,int y,int z,LL co){
    next[++tot]=point[x];point[x]=tot;
    aa[tot].st=x;aa[tot].en=y;aa[tot].va=z;aa[tot].co=co;
    next[++tot]=point[y];point[y]=tot;
    aa[tot].st=y;aa[tot].en=x;aa[tot].va=0;aa[tot].co=-co;
}
inline bool check(int x,int y){
    int i,j,now,num=0;
    if((a[x]%a[y])||(a[x]==a[y])) return false;
    now=a[x]/a[y];
    for(i=1;i<=prime[0];++i){
        while(now%prime[i]==0) ++num,now/=prime[i];
        if(num>1) return false;
        if(now==1) return true;
    }
    if(now!=1) ++num;
    return num==1;
}
inline void paint(int x,int kind){
    int i;
    co[x]=kind;
    for(i=1;i<=n;++i)
      if(map[x][i]&&!co[i])
        paint(i,kind==1?2:1);
}
inline LL SPFA(int x,int y){
    int h=0,t=1,i,u;
    l[t]=x;
    for(i=1;i<=T;++i) dis[i]=-INF;
    dis[x]=0;
    while(h!=t){
        h=h%D+1;u=l[h];f[u]=true;
        for(i=point[u];i;i=next[i])
          if(aa[i].va>0&&dis[aa[i].en]<dis[u]+aa[i].co){
            dis[aa[i].en]=dis[u]+aa[i].co;
            pre[aa[i].en]=i;
            if(f[aa[i].en]){
                f[aa[i].en]=false;
                t=t%D+1;
                l[t]=aa[i].en;
            }
          }
    }
    return dis[y];
}
inline int ISAP(int x,int y){
    int minn=inf,i;
    for(i=y;i!=x;i=aa[pre[i]].st)
      minn=min(minn,aa[pre[i]].va);
    for(i=y;i!=x;i=aa[pre[i]].st){
        aa[pre[i]].va-=minn;
        aa[pre[i]^1].va+=minn;
    }
    return minn;
}
int main(){
    int i,j,o=0,num=0,maxn=0;
    prepare();
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&a[i]);
    for(i=1;i<=n;++i) scanf("%d",&b[i]);
    for(i=1;i<=n;++i) scanf("%d",&c[i]),o+=(c[i]==0);
    for(i=1;i<=n;++i)
      for(j=1;j<=n;++j)
        if(check(i,j)) map[i][j]=map[j][i]=1;
    for(i=1;i<=n;++i)
      if(!co[i]) paint(i,1);
    for(i=1;i<=n;++i)
      if(co[i]==1) add(1,i+1,b[i],0);
      else add(i+1,T,b[i],0);
    for(i=1;i<=n;++i)
      for(j=i+1;j<=n;++j)
        if(map[i][j]||map[j][i]){
            int x=i,y=j;
            if(co[x]==2) swap(x,y);
            add(x+1,y+1,inf,(LL)c[x]*c[y]);
        }
    memset(f,1,sizeof(f));
    LL minn,ans=0;
    while(minn!=-INF){
        minn=SPFA(1,T);
        if(minn!=-INF){
            int now=ISAP(1,T);
            ans=ans+minn*(LL)now;
            if(ans<0LL){
                ans-=minn*(LL)now;
                printf("%d\n",num+min(now,(int)(-ans/minn)));
                return 0;
            }
            num+=now;
        }
    }
    printf("%d\n",num);
}

T3：<script type="math/tex" id="MathJax-Element-13">T3：</script>

题意：给出一棵树，有点权和边权，有两种操作，一种是将一条路径上的点权改动成min(v[x],a?dis[x]+b)<script type="math/tex" id="MathJax-Element-14">min(v[x],a*dis[x]+b)</script>。dis[x]<script type="math/tex" id="MathJax-Element-15">dis[x]</script> 表示x到起点的距离（仅仅算边权）。还有一种是询问a到b路径中最小的点权。


第一种改动能够看成是往树上的一段区间中增加一个线段。这个东西能够用线段树维护。用线段树维护这个区间的线段的斜率和截距。每次向这个区间中增加一条新的线段的时候。看一下这段区间中原来的线段和新增加的线段哪一个对这段区间的影响更大，将影响小的线段下放到它有影响的子树，每次一直这样下放到叶子节点。这样每次插入的复杂度是O(log2n)<script type="math/tex" id="MathJax-Element-16">O(log^2n)</script>。


每次查询的时候仅仅须要看一下这段区间中的最小值和这段区间中所保存的线段的两个端点的情况即可了，复杂度是O(logn)<script type="math/tex" id="MathJax-Element-17">O(logn)</script>。


这道题每次的dis数组还是不知道的。能够在增加线段的时候顺便将lca传进去（常数大了好多。

。。）
再加上链剖，总的复杂度就是O(nlog3n)<script type="math/tex" id="MathJax-Element-18">O(nlog^3n)</script>
code:<script type="math/tex" id="MathJax-Element-19">code:</script>

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mid (l+r)/2
#define L k<<1,l,mid
#define R k<<1|1,mid+1,r
#define LL long long
#define D 123456789123456789LL
const int N=100010;
LL dis[N],a,b;
struct S{int st,en,va;}aa[N<<1];
struct T{int lca,st,kind;LL k,b,minn;}tr[N<<2];
int n,m,point[N],next[N<<1],tot,deep[N],siz[N],son[N],belong[N],fa[N][21],q[N],pos[N],dfsn,cur[N],lca,to[N],flag[N<<2];
inline int in(){
    int f=1,x=0;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){
        if(ch==‘-‘) f=-1;
        ch=getchar();
    }
    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return x*f;
}
inline int IN(){
    LL f=1,x=0;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){
        if(ch==‘-‘) f=-1;
        ch=getchar();
    }
    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return x*f;
}
inline void add(int x,int y,int z){
    next[++tot]=point[x];point[x]=tot;
    aa[tot].st=x;aa[tot].en=y;aa[tot].va=z;
    next[++tot]=point[y];point[y]=tot;
    aa[tot].st=y;aa[tot].en=x;aa[tot].va=z;
}
inline void prepare(){
    int h=1,t=1,u,i,j;
    q[h]=1;
    while(h<=t){
        u=q[h];
        for(i=point[u];i;i=next[i])
          if(aa[i].en!=fa[u][0]){
            q[++t]=aa[i].en;
            deep[aa[i].en]=deep[u]+1;
            fa[aa[i].en][0]=u;
            dis[aa[i].en]=dis[u]+(LL)aa[i].va;
            for(j=1;j<=20;++j)
              fa[aa[i].en][j]=fa[fa[aa[i].en][j-1]][j-1];
          }
        h+=1;
    }
    for(i=t;i;--i){
        u=q[i];siz[u]=1;
        for(j=point[u];j;j=next[j])
          if(aa[j].en!=fa[u][0]){
            siz[u]+=siz[aa[j].en];
            if(siz[aa[j].en]>siz[son[u]]) son[u]=aa[j].en;
          }
    }
    int now=1;
    for(i=1;i<=n;++i) cur[i]=point[i];
    while(now){
        if(!pos[now]){
            pos[now]=++dfsn;
            to[dfsn]=now;
            belong[now]=(now==son[fa[now][0]] ? belong[fa[now][0]] : now);
            now=(son[now] ?
 son[now] : fa[now][0]);
        }
        else{
            for(i=cur[now];i&&(aa[i].en==fa[now][0]||aa[i].en==son[now]);i=next[i]);
            cur[now]=next[i];
            belong[aa[i].en]=aa[i].en;
            now=(i ? aa[i].en : fa[now][0]);
        }
    }
}
inline int LCA(int x,int y){
    if(deep[x]<deep[y]) swap(x,y);
    int t=deep[x]-deep[y],i;
    for(i=0;i<=20;++i)
      if(t&(1<<i)) x=fa[x][i];
    for(i=20;~i;--i)
      if(fa[x][i]!=fa[y][i])
        x=fa[x][i],y=fa[y][i];
    return x==y?x:fa[x][0];
}
inline void build(int k,int l,int r){
    if(l==r){
        tr[k].k=0;
        tr[k].kind=-1;
        tr[k].lca=to[l];
        tr[k].b=tr[k].minn=D;
        return ;
    }
    build(L);build(R);
    tr[k]=tr[k<<1];
}
inline int LL calc(int x,int y,int z,int kind){
    x=to[x];
    if(kind==0) return dis[z]-dis[x];
    if(kind==1) return dis[z]-dis[y]+dis[x]-dis[y];
}
inline void insert(int k,int l,int r,int x,int y,T now){
    if(x<=l&&y>=r){
        LL minn=D;
        minn=min(minn,calc(l,now.lca,now.st,now.kind)*now.k+now.b);
        minn=min(minn,calc(r,now.lca,now.st,now.kind)*now.k+now.b);
        now.minn=tr[k].minn=min(tr[k].minn,minn);
        if(!flag[k]){
            flag[k]=1;
            tr[k]=now;
            return ;
        }
        int o1=calc(l,now.lca,now.st,now.kind)*now.k+now.b<calc(l,tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b;
        if(l==r){
            if(o1) tr[k]=now;
            return ;
        }
        int o2=calc(mid,now.lca,now.st,now.kind)*now.k+now.b<calc(mid,tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b;
        int o3=calc(r,now.lca,now.st,now.kind)*now.k+now.b<calc(r,tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b;
        if(o1&&o3){
            tr[k]=now;
            return ;
        }
        if(!o1&&!o3) return;
        if(o2){
            swap(tr[k],now);
            o1^=1;o3^=1;
        }
        if(o1) insert(L,x,y,now);
        if(o3) insert(R,x,y,now);
        return ;
    }
    if(x<=mid) insert(L,x,y,now);
    if(y>mid) insert(R,x,y,now);
    tr[k].minn=min(tr[k].minn,min(tr[k<<1].minn,tr[k<<1|1].minn));
}
inline LL query(int k,int l,int r,int x,int y){
    LL minn=D;
    if(x<=l&y>=r){
        LL o_l=calc(l,tr[k].lca,tr[k].st,tr[k].kind);
        LL o_r=calc(r,tr[k].lca,tr[k].st,tr[k].kind);
        return min(tr[k].minn,min(o_l*tr[k].k+tr[k].b,o_r*tr[k].k+tr[k].b));
    }
    minn=min(minn,calc(max(x,l),tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b);
    minn=min(minn,calc(min(y,r),tr[k].lca,tr[k].st,tr[k].kind)*tr[k].k+tr[k].b);
    if(x<=mid) minn=min(minn,query(L,x,y));
    if(y>mid) minn=min(minn,query(R,x,y));
    return minn;
}
inline void change(int x,int y,int st,int kind){
    int i,j;
    T now=(T){lca,st,kind,a,b,D};
    while(belong[x]!=belong[y]){
        insert(1,1,n,pos[belong[x]],pos[x],now);
        x=fa[belong[x]][0];
    }
    insert(1,1,n,pos[y],pos[x],now);
}
inline LL ask(int x,int y){
    LL minn=D;
    while(belong[x]!=belong[y]){
        minn=min(minn,query(1,1,n,pos[belong[x]],pos[x]));
        x=fa[belong[x]][0];
    }
    minn=min(minn,query(1,1,n,pos[y],pos[x]));
    return minn;
}
int main(){
    int i,j,x,y,t,z;
    n=in();m=in();
    for(i=1;i<n;++i){
        x=in();y=in();z=in();
        add(x,y,z);
    }
    prepare();
    build(1,1,n);
    while(m--){
        t=in();x=in();y=in();
        lca=LCA(x,y);
        if(t==1){
            a=IN();b=IN();
            change(x,lca,x,0);
            change(y,lca,x,1);
        }
        if(t==2) printf("%lld\n",min(ask(x,lca),ask(y,lca)));
    }
}

Day2：<script type="math/tex" id="MathJax-Element-20">Day2：</script>

T1：<script type="math/tex" id="MathJax-Element-21">T1：</script>

题意：每次向一个字符串的结尾加一个字符，输出当前有多少种不同的非空子串。
先将这个字符串全读进来，然后把字符串反过来建后缀数组。总的答案就是n?(n+1)2?∑n?1i=1height[i]<script type="math/tex" id="MathJax-Element-22">\frac{n*(n+1)}{2}-\sum_{i=1}^{n-1}height[i]</script>
由于要动态的查询。所以维护一个rank的权值线段树，每次增加一个之后查询一下前驱和后继。每次更新的答案就是：n?i?lcp(now,pre)?lcp(now,sub)+lcp(pre,sub)<script type="math/tex" id="MathJax-Element-23">n-i-lcp(now,pre)-lcp(now,sub)+lcp(pre,sub)</script>
code:<script type="math/tex" id="MathJax-Element-24">code:</script>

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define inf 0x7fffffff
const int N=100010;
struct S{int minn,maxn;}tr[N<<2];
int n,a[N],b[N],m,t1[N],t2[N],sa[N],rank[N],c[N],height[N],st[N][21],Log[N];
inline int in(){
    int x=0;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘) ch=getchar();
    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return x;
}
inline bool cmp(int *y,int p,int q,int k){
    int o0,o1;
    o0=(p+k>=n)?
-1:y[p+k];
    o1=(q+k>=n)?-1:y[q+k];
    return o0==o1&&y[p]==y[q];
}
inline void build_sa(){
    int i,k,p,*x=t1,*y=t2;
    for(i=0;i<m;++i) c[i]=0;
    for(i=0;i<n;++i) ++c[x[i]=a[i]];
    for(i=1;i<m;++i) c[i]+=c[i-1];
    for(i=n-1;~i;--i) sa[--c[x[i]]]=i;
    for(k=1;k<=n;k<<=1){
        for(p=0,i=n-k;i<n;++i) y[p++]=i;
        for(i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k;
        for(i=0;i<m;++i) c[i]=0;
        for(i=0;i<n;++i) ++c[x[y[i]]];
        for(i=1;i<m;++i) c[i]+=c[i-1];
        for(i=n-1;~i;--i) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        x[sa[0]]=0;m=1;
        for(i=1;i<n;++i) x[sa[i]]=(cmp(y,sa[i],sa[i-1],k)?m-1:m++);
        if(m>=n) break;
    }
}
inline void build_height(){
    int i,j,k=0;
    for(i=0;i<n;++i) rank[sa[i]]=i;
    for(i=0;i<n;++i){
        k=k?--k:k;
        j=sa[rank[i]-1];
        while(a[i+k]==a[j+k]) ++k;
        height[rank[i]]=k;
    }
    /*------------st------------*/
    memset(st,127/3,sizeof(st));    
    for(i=0;i<n;++i) st[i][0]=height[i];
    for(j=1;j<=20;++j)
      for(i=0;i+(1<<(j-1))<n;++i)
        st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    for(j=0,i=1;i<=n;++i){
        if((1<<(j+1))<=i) ++j;
        Log[i]=j;
    }
}
inline int LCP(int x,int y){
    int k=Log[y-x];++x;
    return min(st[x][k],st[y-(1<<k)+1][k]);   
}
#define mid (l+r)/2
#define L k<<1,l,mid
#define R k<<1|1,mid+1,r
inline S update(S x,S y){
    S ans;
    ans.maxn=max(x.maxn,y.maxn);
    ans.minn=min(x.minn,y.minn);
    return ans;
}
inline void build_tree(int k,int l,int r){
    if(l==r){
        tr[k].minn=inf;
        tr[k].maxn=-inf;
        return ;
    }
    build_tree(L);build_tree(R);
    tr[k]=update(tr[k<<1],tr[k<<1|1]);
}
inline void insert(int k,int l,int r,int x){
    if(l==r){
        tr[k].maxn=tr[k].minn=l;
        return ;
    }
    if(x<=mid) insert(L,x);
    else insert(R,x);
    tr[k]=update(tr[k<<1],tr[k<<1|1]);
}
inline S query(int k,int l,int r,int x,int y){
    S ans1,ans2;
    bool f1=false,f2=false;
    if(x<=l&&y>=r) return tr[k];
    if(x<=mid) ans1=query(L,x,y),f1=true;
    if(y>mid) ans2=query(R,x,y),f2=true;
    if(f1&&f2) return update(ans1,ans2);
    else return f1?ans1:ans2;
}
int main(){
    int i;
    n=in();
    for(i=n-1;~i;--i) a[i]=b[i]=in();
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    for(i=0;i<n;++i) a[i]=lower_bound(b+1,b+m+1,a[i])-b-1;
    build_sa();
    build_height();
    build_tree(1,0,n-1);
    for(LL ans=0,i=n-1;~i;--i){
        ans+=(LL)(n-i);
        int now=rank[i];
        int pre=now?query(1,0,n-1,0,now-1).maxn:-inf;
        int sub=(now==n-1)?
inf:query(1,0,n-1,now+1,n-1).minn;
        if(pre!=-inf) ans-=(LL)LCP(pre,now);
        if(sub!=inf) ans-=(LL)LCP(now,sub);
        if(pre!=-inf&&sub!=inf) ans+=(LL)LCP(pre,sub);
        insert(1,0,n-1,now);
        printf("%lld\n",ans);
    }
}

T2：<script type="math/tex" id="MathJax-Element-25">T2：</script>

题意：求有多少长度为n的序列，满足1~n仅仅出现过一次。并且恰好有m个数满足a[i]=i<script type="math/tex" id="MathJax-Element-26">a[i]=i</script>。
答案就是C(n,m)?f[n?m]<script type="math/tex" id="MathJax-Element-27">C(n,m)*f[n-m]</script>
C(n,m)<script type="math/tex" id="MathJax-Element-28">C(n,m)</script>表示m个满足条件的数如何选的方案数，再乘上剩下的全部n?m<script type="math/tex" id="MathJax-Element-29">n-m</script>个数都不在多相应的位置上的方案数。也就是错排。


错拍的公式就是：f[i]=(i?1)?(f[i?1]+f[i?2])<script type="math/tex" id="MathJax-Element-30">f[i]=(i-1)*(f[i-1]+f[i-2])</script>
求c的时候预处理一下阶乘。
code:<script type="math/tex" id="MathJax-Element-31">code:</script>

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
#define Mod 1000000007LL
const int M=1000000;
LL f[M+10],g[M+10];
int T,n,m;
inline int in(){
    int x=0;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘) ch=getchar();
    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return x;
}
inline LL quickpow(LL x,LL y){
    LL ans=1;
    while(y){
        if(y&1LL) ans=(ans*x)%Mod;
        y>>=1LL; x=(x*x)%Mod;
    }
    return ans;
}
int main(){
    int i;  
    T=in();
    for(f[1]=0LL,f[2]=1LL,f[0]=1LL,i=3;i<=M;++i) f[i]=(LL)(i-1)*((f[i-1]+f[i-2])%Mod)%Mod;
    for(g[1]=g[0]=1LL,i=2;i<=M;++i) g[i]=(g[i-1]*(LL)i)%Mod;
    while(T--){
        n=in();m=in();
        if(m>n){
            printf("0\n");
            continue;
        }
        LL ans=f[n-m]*((g[n]*quickpow(g[m],Mod-2)%Mod)*quickpow(g[n-m],Mod-2)%Mod)%Mod;
        printf("%lld\n",ans);
    }
}

T3：<script type="math/tex" id="MathJax-Element-32">T3：</script>

题意：有一个长度为n的序列。每一个节点都有一个权值，分成m份，求m份的最小的方差是多少。答案要求?m2<script type="math/tex" id="MathJax-Element-33">*m^2</script>。


ans=m?∑mi=1(xi?xˉ)2<script type="math/tex" id="MathJax-Element-34">ans=m*\sum_{i=1}^{m}(xi-\overline{x})^2</script>
      =m?∑mi?1(xi2+xˉ2?2xi?xˉ)<script type="math/tex" id="MathJax-Element-35">\ \ \ \ \ \ =m*\sum_{i-1}^{m}(xi^2+\overline{x}^2-2xi*\overline{x})</script>
把∑<script type="math/tex" id="MathJax-Element-36">\sum</script>拆开之后。后面两项都是常数。就相当于求每段的平方和的最大。这个东西能够斜率优化。
code:<script type="math/tex" id="MathJax-Element-37">code:</script>

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
const int N=3010;
LL f[N][N],a[N];
int n,m,h[N],t[N],q[N][N];
inline LL pow(LL x){return x*x;}
inline LL get_son(int x,int y,int z){
    return f[z][x]+pow(a[x])-f[z][y]-pow(a[y]);
}
inline LL get_fa(int x,int y){
    return a[x]-a[y];
}
inline LL calc(int x,int y,int z){
    return f[z][x]+pow(a[y]-a[x]);
}
int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i) 
      scanf("%lld",&a[i]),a[i]+=a[i-1];
    memset(f,127/3,sizeof(f));
    for(j=0;j<=m;++j) f[j][0]=0,q[j][h[j]=t[j]=1]=0;
    for(j=1;j<=m;++j)
      for(i=1;i<=n;++i){
        while(h[j-1]<t[j-1]&&get_son(q[j-1][h[j-1]+1],q[j-1][h[j-1]],j-1)<get_fa(q[j-1][h[j-1]+1],q[j-1][h[j-1]])*(LL)a[i]*2LL) ++h[j-1];
        f[j][i]=calc(q[j-1][h[j-1]],i,j-1);
        while(h[j]<t[j]&&get_son(i,q[j][t[j]],j)*get_fa(q[j][t[j]],q[j][t[j]-1])<get_son(q[j][t[j]],q[j][t[j]-1],j)*get_fa(i,q[j][t[j]])) --t[j];
        q[j][++t[j]]=i;
      }
    printf("%lld\n",f[m][n]*(LL)m-pow(a[n]));
}
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

[SDOI2016Round1]解题报告


联系
我们