摘自我的github：https://github.com/Anoxxx

The Solution

Source: Codeforces Round #179 (Div. 1)

    VJudge链接：  https://cn.vjudge.net/contest/167920#problem

CodeForces链接：  http://codeforces.com/problemset/problem/295

#A Greg and Array

Time limit: 1500 ms

Memory limit: 262144 kB

Tags: 差分，线段树

题意

给你n个数，m个操作，每个操作包含l、r、d，表示区间[l,r]+d，再给你k个总操作，每个总操作包含x、y，表示做第x到第y个操作，问最后各个数的数值；

题解

两次打标记（就是两次差分

#include<cstdio>

#include<algorithm>

using namespace std;

long long a[],l[],p,t[];

int n,m,k,x,y;

struct node{

    int l,r,d;

}c[];

int main(){

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<n;i++)scanf("%lld",&a[i]);

    for(int i=;i<m;i++)scanf("%d%d%d",&c[i].l,&c[i].r,&c[i].d);

    for(int i=;i<k;i++){

        scanf("%d%d",&x,&y);

        t[x-]++;t[y]--;

    }

    for(int i=;i<m;i++){

        p+=t[i];

        l[c[i].l-]+=p*c[i].d;l[c[i].r]-=p*c[i].d;

    }

    p=;

    for(int i=;i<n;i++){

        p+=l[i];

        a[i]+=p;

        printf("%lld ",a[i]);

    }

}

#B Greg and Graph

Time limit： 3000 ms

Memory limit： 262144 kB

Tags： 最短路，逆向思维

题意

给你n个点，每两个不同的点间路的距离，n次操作，每次操作删除一个点，求每次操作前所有点对之间的最短路之和。

题解

可以把每次操作删除一个点，看做从后面的操作到前面的操作依次加点，然后对于每次加点对其他所有点进行松弛；然后每次的答案即为已加入各点目前为止间的最短路之和，倒着输出即可；

#include<cstdio>

#include<algorithm>

using namespace std;

int n,b[],x[];

long long ans[],a[][],f[][];

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++){

        scanf("%lld",&a[i][j]);f[i][j]=a[i][j];

    }

    for(int i=;i<=n;i++)scanf("%d",&x[i]);

    for(int i=n;i>=;i--){

        b[x[i]]=;

        for(int j=;j<=n;j++)

        for(int k=;k<=n;k++)f[j][k]=min(f[j][k],f[j][x[i]]+f[x[i]][k]);

        for(int j=;j<=n;j++)

        for(int k=;k<=n;k++)if(b[j]&&b[k])ans[i]+=f[j][k];

    }

    for(int i=;i<=n;i++)printf("%lld ",ans[i]);

    return ;

}

#C Greg and Friends

Time limit： 2000 ms

Memory limit： 262144 kB

Tags： dp，bfs

题意

有n个人在岸边，每个人不是50kg就是100kg，有一艘船，载重量为k，可以载人过河，但每次必须有人划船，问使所有人都到对岸的最少过河次数和这个次数的方案数。

题解

最少过河次数bfs无脑求就行（好像都不用bfs……，设f[i][j][k]表示有i个50kg的人和j个100kg的人在原岸，船在（k==1？原岸：对面）的最少次数的方案数，显然这可以在bfs的时候通过组合数维护，注意bfs的判重即可；

#include<cstdio>

#include<algorithm>

#define MOD 1000000007

using namespace std;

int b[][][][][],q[][],anx,aum,num5,num10,x,n,k,h,t;

long long f[][][],c[][];

void push(int px,int py,int pz,int i,int j,int val){

    int x=px+i,y=py+j,z=pz^;i=abs(i),j=abs(j);

    if(anx&&val>anx)return;

    if(b[px][py][pz][x][y])return;

    if(pz==)f[x][y][z]=(f[x][y][z]+(f[px][py][pz]*(c[num5-px][i]*c[num10-py][j])%MOD)%MOD)%MOD;

    else f[x][y][z]=(f[x][y][z]+(f[px][py][pz]*(c[px][i]*c[py][j])%MOD)%MOD)%MOD;

    q[++t][]=x;q[t][]=y;q[t][]=z;q[t][]=val;b[px][py][pz][x][y]=;

    if(x==num5&&y==num10&&z==&&!anx)anx=val;

}

void getC(){

    c[][]=;

    for(int i=;i<=;i++)

    for(int j=;j<=i;j++)c[i][j]=(c[i-][j]+c[i-][j-])%MOD;

}

int main(){

    getC();

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++){

        scanf("%d",&x);

        x==?num5++:num10++;

    }

    f[][][]=;t++;

    q[t][]=q[t][]=q[t][]=q[t][]=;b[][][][][]=;

    while(h<t){

        int x=q[++h][],y=q[h][],z=q[h][],val=q[h][];

        if(z==){

            int xp=num5-x,yp=num10-y;

            for(int i=;i<=min(yp,k/);i++)push(x,y,z,,i,val+);

            for(int i=;i<=min(xp,k/);i++)

            for(int j=;j<=min(yp,(k-i*)/);j++)

            push(x,y,z,i,j,val+);

        }

        else{

            for(int i=;i<=min(y,k/);i++)push(x,y,z,,-i,val+);

            for(int i=;i<=min(x,k/);i++)

            for(int j=;j<=min(y,(k-i*)/);j++)

            push(x,y,z,-i,-j,val+);

        }

    }

    return anx==?printf("%d\n%d",-,):printf("%d\n%d",anx,f[num5][num10][]),;

}

#D New Year Letter

Time limit: 2000 ms

Memory limit: 262144 kB

Tags: dp

题意

对于一个n行m列的黑白矩阵，存在cave当且仅当：

1、存在[l,r]使得第l行到第r行都有且仅有两个黑色格子，其他行没有；

2、存在一个行号t，使得：

1）对于任意存在黑色格子的行，设两个黑色格子的列号为x和y(x<y)，则设集合s(r)=[x,y]；

2）任意取t及t之上的两个有黑色格子行，令上方的行为u，下方的行为d，则s(u)属于s(d);

3）任意取t及t之下的两个有黑色格子行，令上方的行为u，下方的行为d，则s(d)属于s(u); 求n行m列的黑白矩阵存在cave的方案数;

题解

设f[i][j]表示前i行只让上面的行符合情况，第i行集合长度为j（可以看做两个黑色块一个在1，一个在j）的方案数，则：

1、f[i][j]=sigma(f[i-1]k)+f[i][j-1]; 前面的sigma是显然的，而f[i][j-1]是因为，f[i][j-1]的情况可以整体向右移一位并依然符合f[i][j]的定义；

2、ans=sigma((f[i][j]-f[i-1][j])f[n-i+1][j](m-j+1))(1<=i<=n,2<=j<=m); f[i][j]-f[i-1][j]是因为第i-1行长度为j且第i行长度为j的方案可能重复计算，需要避免 f[n-i+1][j]则是f[i][j]只算了上面符合情况的，我们需要和下面符合情况的方案数乘起来 m-j+1则是因为这个区间可以左右移啊

#include<cstdio>

#define MOD 1000000007

#define ll long long

using namespace std;

ll ans,n,m,s,f[][];

int main(){

    scanf("%lld%lld",&n,&m);

    for(int i=;i<=m;i++)f[][i]=;

    for(int i=;i<=n;i++){

        int s=;f[i][]=;

        for(int j=;j<=m;j++){

            s=(s+f[i-][j])%MOD;

            f[i][j]=(f[i][j-]+s)%MOD;

        }

    }

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)ans=(ans+(m-j+)*(f[i][j]-f[i-][j]+MOD)%MOD*f[n-i+][j])%MOD;

    printf("%lld",ans);

}

#E Yaroslav and Points

 Time limit: 2000 ms

 Memory limit: 262144 kB

 Tags: 动态开点线段树

题意

给你n个x轴上的坐标，给你两个操作： 1、把输入的第j个点的坐标右移d 2、给定区间，输出区间内点之间的距离和

题解

开一个-1e8到1e8的线段树，对于每一个点，就把含有这个点坐标的区间更新，cnt代表区间内的点数，sum是区间内的点的坐标和，ans就是答案：

c.sum=a.sum+b.sum;

c.cnt=a.cnt+b.cnt;

c.ans=a.ans+b.ans+a.cntb.sum-b.cnta.sum;

（为什么这样？？手动模拟合并两个区间你就知道啦最后因为空间开不下那么多点，于是动态开点，要用到再标号，就可以啦

#include<cstdio>

#include<algorithm>

#define root -1000000001,1000000001,1

#define lson l,m

#define rson m+1,r

#define ll long long

using namespace std;

struct node{

    ll cnt,sum,ans;

    int ls,rs;

    node(){

        cnt=sum=ans=ls=rs=;

    }

}a[],zero;

int n,j,p,x[],type,m,l,r,tot=;

node merge(node c,node a,node b){

    c.sum=a.sum+b.sum;

    c.cnt=a.cnt+b.cnt;

    c.ans=a.ans+b.ans+a.cnt*b.sum-b.cnt*a.sum;

    return c;

}

void update(int val,int z,int l,int r,int rt){

    if(val<l||val>r)return;

    if(l==r){

        a[rt].ans=;a[rt].cnt+=z;a[rt].sum+=z*val;return;

    }

    if(a[rt].ls==)a[rt].ls=++tot;

    if(a[rt].rs==)a[rt].rs=++tot;

    int m=(l+r)>>;

    if(m>=val)update(val,z,lson,a[rt].ls);

    if(m<val)update(val,z,rson,a[rt].rs);

    a[rt]=merge(a[rt],a[a[rt].ls],a[a[rt].rs]);

    //printf("%d %d %d %d %d\n",a[rt].ls,a[rt].rs,a[rt].ans,a[rt].cnt,a[rt].sum);

}

node query(int x,int y,int l,int r,int rt){

    if(y<l||x>r)return zero;

    if(x<=l&&r<=y)return a[rt];

    int m=(l+r)>>;node p,q;

    if(m>=x)p=query(x,y,lson,a[rt].ls);

    if(m<y)q=query(x,y,rson,a[rt].rs);

    return merge(a[rt],p,q);

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++){

        scanf("%d",&x[i]);

        update(x[i],,root);

        //printf("%d %d\n",a[1].rs,a[1].ls);

    }

    scanf("%d",&m);

    for(int i=;i<=m;i++){

        scanf("%d",&type);

        if(type==){

            scanf("%d%d",&j,&p);

            update(x[j],-,root);x[j]+=p;update(x[j],,root);

        }

        else{

            scanf("%d%d",&l,&r);

            printf("%lld\n",query(l,r,root).ans);

        }

    }

}

巴特西

[Codeforces]#179 div1-----295ABCDE