首页 > 代码库 > [Codeforces]#179 div1-----295ABCDE

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

2024-10-10 08:24:39   213人阅读

摘自我的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[100100],l[100100],p,t[100100];
int n,m,k,x,y;
struct node{
    int l,r,d;
}c[100100];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    for(int i=0;i<m;i++)scanf("%d%d%d",&c[i].l,&c[i].r,&c[i].d);
    for(int i=0;i<k;i++){
        scanf("%d%d",&x,&y);
        t[x-1]++;t[y]--;
    }
    for(int i=0;i<m;i++){
        p+=t[i];
        l[c[i].l-1]+=p*c[i].d;l[c[i].r]-=p*c[i].d;
    }
    p=0;
    for(int i=0;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[501],x[501];
long long ans[501],a[501][501],f[501][501];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        scanf("%lld",&a[i][j]);f[i][j]=a[i][j];
    }
    for(int i=1;i<=n;i++)scanf("%d",&x[i]);
    for(int i=n;i>=1;i--){
        b[x[i]]=1;
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)f[j][k]=min(f[j][k],f[j][x[i]]+f[x[i]][k]);
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)if(b[j]&&b[k])ans[i]+=f[j][k];
        
    }
    for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
    return 0;
}

 

#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[51][51][2][51][51],q[500000][4],anx,aum,num5,num10,x,n,k,h,t;
long long f[51][51][2],c[100][100];
void push(int px,int py,int pz,int i,int j,int val){
    int x=px+i,y=py+j,z=pz^1;i=abs(i),j=abs(j);
    if(anx&&val>anx)return;
    if(b[px][py][pz][x][y])return;
    
    if(pz==0)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][0]=x;q[t][1]=y;q[t][2]=z;q[t][3]=val;b[px][py][pz][x][y]=1;
    if(x==num5&&y==num10&&z==1&&!anx)anx=val;
}
void getC(){
    c[0][0]=1;
    for(int i=1;i<=90;i++)
    for(int j=0;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
}
int main(){
    getC();
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        x==50?num5++:num10++;
    }
    f[0][0][0]=1;t++;
    q[t][0]=q[t][1]=q[t][2]=q[t][3]=0;b[0][0][0][0][0]=1;
    while(h<t){
        int x=q[++h][0],y=q[h][1],z=q[h][2],val=q[h][3];
        if(z==0){
            int xp=num5-x,yp=num10-y;
            for(int i=1;i<=min(yp,k/100);i++)push(x,y,z,0,i,val+1);
            for(int i=1;i<=min(xp,k/50);i++)
            for(int j=0;j<=min(yp,(k-i*50)/100);j++)
            push(x,y,z,i,j,val+1);
        }
        else{
            for(int i=1;i<=min(y,k/100);i++)push(x,y,z,0,-i,val+1);
            for(int i=1;i<=min(x,k/50);i++)
            for(int j=0;j<=min(y,(k-i*50)/100);j++)
            push(x,y,z,-i,-j,val+1);
        }
    }
    return anx==0?printf("%d\n%d",-1,0):printf("%d\n%d",anx,f[num5][num10][1]),0;
}

 

#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[2001][2001];
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)f[1][i]=1;
    for(int i=2;i<=n;i++){
        int s=0;f[i][1]=1;
        for(int j=2;j<=m;j++){
            s=(s+f[i-1][j])%MOD;
            f[i][j]=(f[i][j-1]+s)%MOD;
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=2;j<=m;j++)ans=(ans+(m-j+1)*(f[i][j]-f[i-1][j]+MOD)%MOD*f[n-i+1][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=0;
    }
}a[6000000],zero;
int n,j,p,x[100010],type,m,l,r,tot=1;
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=0;a[rt].cnt+=z;a[rt].sum+=z*val;return;
    }
    if(a[rt].ls==0)a[rt].ls=++tot;
    if(a[rt].rs==0)a[rt].rs=++tot;
    int m=(l+r)>>1;
    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)>>1;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=1;i<=n;i++){
        scanf("%d",&x[i]);
        update(x[i],1,root);
        //printf("%d %d\n",a[1].rs,a[1].ls);
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&type);
        if(type==1){
            scanf("%d%d",&j,&p);
            update(x[j],-1,root);x[j]+=p;update(x[j],1,root);
        }
        else{
            scanf("%d%d",&l,&r);
            printf("%lld\n",query(l,r,root).ans);
        }
    }
}

 

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


联系
我们