【SDOI2016Round1】【解题报告】

Day1

T1：

题意：求∑n?1i=0∑m?1j=0max((ixorj)?k，0)
因为是抑或操作，每一位都是独立的，所以可以一位一位的算贡献。
f[i][a][b][c]表示第i位时，每个数跟n,m,k的大小关系，0表示小于，1表示i位之前都相等，2表示大于。转移的时候美剧当前这一位的数是什么，从高位向低位转移就行了。
复杂度是O(nlogn)
code:

#include
#include
#include
#include
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;ini[i+1]) continue;
                    if(o0==ni[i+1]) x=1;
                    if(o0mi[i+1]) continue;
                        if(o1==mi[i+1]) y=1;
                        if(o1ki[i+1]) z=2;
                        if(o==ki[i+1]) z=1;
                        if(o>=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>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：

题意：给出n种数字，第i个是ai，个数是bi，权值是ci。如果ai|aj而且aiaj是一个质数，那么这两个数字就能获得ci?cj的价值，要求总价值不小于0的情况下求最多的配对数。
配对关系是一个二分图，所以建出费用流的图来，当跑到费用小于0的时候，处理一下当前的流量，退出就行了。
code:

#include
#include
#include
#include
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;i1) 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;i0&&dis[aa[i].en]

T3：

题意：给出一棵树，有点权和边权，有两种操作，一种是将一条路径上的点权修改成min(v[x],a?dis[x]+b)，dis[x] 表示x到起点的距离（只算边权）。另一种是询问a到b路径中最小的点权。
第一种修改可以看成是往树上的一段区间中加入一个线段。这个东西可以用线段树维护。用线段树维护这个区间的线段的斜率和截距。每次向这个区间中加入一条新的线段的时候，看一下这段区间中原来的线段和新加入的线段哪一个对这段区间的影响更大，将影响小的线段下放到它有影响的子树，每次一直这样下放到叶子节点。这样每次插入的复杂度是O(log2n)。
每次查询的时候只需要看一下这段区间中的最小值和这段区间中所保存的线段的两个端点的情况就行了，复杂度是O(logn)。
这道题每次的dis数组还是不知道的，可以在加入线段的时候顺便将lca传进去（常数大了好多。。。）
再加上链剖，总的复杂度就是O(nlog3n)
code:

#include
#include
#include
#include
using namespace std;
#define mid (l+r)/2
#define L k'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&chsiz[son[u]]) son[u]=aa[j].en;
          }
    }
    int now=1;
    for(i=1;i=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.bmid) insert(R,x,y,now);
    tr[k].minn=min(tr[k].minn,min(tr[k=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(xmid) 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

Day2：

T1：

题意：每次向一个字符串的结尾加一个字符，输出当前有多少种不同的非空子串。
先将这个字符串全读进来，然后把字符串反过来建后缀数组。总的答案就是n?(n+1)2?∑n?1i=1height[i]
因为要动态的查询，所以维护一个rank的权值线段树，每次加入一个之后查询一下前驱和后继，每次更新的答案就是：n?i?lcp(now,pre)?lcp(now,sub)+lcp(pre,sub)
code:

#include
#include
#include
#include
using namespace std;
#define LL long long
#define inf 0x7fffffff
const int N=100010;
struct S{int minn,maxn;}tr[N'9') ch=getchar();
    while(ch>='0'&&ch=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=k) y[p++]=sa[i]-k;
        for(i=0;i=n) break;
    }
}
inline void build_height(){
    int i,j,k=0;
    for(i=0;i=r) return tr[k];
    if(xmid) 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

T2：

题意：求有多少长度为n的序列，满足1~n只出现过一次，而且恰好有m个数满足a[i]=i。
答案就是C(n,m)?f[n?m]
C(n,m)表示m个满足条件的数怎样选的方案数，再乘上剩下的所有n?m个数都不在多对应的位置上的方案数，也就是错排。
错拍的公式就是：f[i]=(i?1)?(f[i?1]+f[i?2])
求c的时候预处理一下阶乘。
code:

#include
#include
#include
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'9') ch=getchar();
    while(ch>='0'&&ch>=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;in){
            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：

题意：有一个长度为n的序列，每个节点都有一个权值，分成m份，求m份的最小的方差是多少。答案要求?m2。
ans=m?∑mi=1(xi?xˉ)2
=m?∑mi?1(xi2+xˉ2?2xi?xˉ)
把∑拆开之后，后面两项都是常数，就相当于求每段的平方和的最大。这个东西可以斜率优化。
code:

#include
#include
#include
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