美高梅网投网站-美高梅手机网投-美高梅官方网站
做最好的网站

您的位置:美高梅网投网址 > 美高梅官方网站 > 每一个操作蕴含l、r、d

每一个操作蕴含l、r、d

发布时间:2019-09-27 02:50编辑:美高梅官方网站浏览(62)

    自己是链接,点本人哟:)

    摘自己的github:

    如果任性行之间能够再度排序。
    问你最大的全部是1的子矩阵中1的个数

    The Solution

    Source: Codeforces Round #179 (Div. 1)
        VJudge链接:  https://cn.vjudge.net/contest/167920#problem   
    CodeForces链接:  http://codeforces.com/problemset/problem/295
    

    设cnt[i][j]
    意味着那个点往右一连的1的个数
    我们枚举列j
    下一场对于第j列的cnt[1..n][j]
    我们把那n个数字排个序
    接下来顺序枚举那n个数字
    设若我们枚举到了第i个数字,显明第i~n那n-i+1个数字是能构成一个宽为cnt[i][j]长为n-i+1的矩形的
    且那一个矩形的左边界都以i
    那就是那道题的本事所在了
    找到最短的幅度,让比它长的都和它适应
    秒啊

    #A Greg and Array

    Time limit: 1500 ms
    Memory limit: 262144 kB
    Tags: 差分,线段树
    
    import java.io.*;import java.util.*;public class Main {            static InputReader in;    static PrintWriter out;            public static void main(String[] args) throws IOException{        //InputStream ins = new FileInputStream("E:\rush.txt");        InputStream ins = System.in;        in = new InputReader;        out = new PrintWriter(System.out);        //code start from here        new Task().solve;        out.close();    }        static int N = 5000;    static class Task{                int n,m;        String s[] = new String[N+10];        int cnt[][] = new int[N+10][N+10];        int col[][] = new int[N+10][N+10];                public void solve(InputReader in,PrintWriter out) {            n = in.nextInt();m = in.nextInt();            for (int i = 1;i <= n;i++) {                s[i] = in.next();                StringBuilder sb = new StringBuilder;                sb.insert(0, ' ');                s[i] = sb.toString();            }            for (int i = 1;i <= n;i++) {                for (int j = m;j >= 1;j--) {                    if (s[i].charAt=='0') {                        cnt[i][j] = 0;                    }else {                        cnt[i][j] = cnt[i][j+1]+1;                    }                                    }            }                        for (int j = m;j >= 1;j--) {                for (int i = 1;i <= n;i++)                {                    col[j][i] = cnt[i][j];                }            }                        long ans = 0;            for (int i = 1;i <= m;i++) {                Arrays.sort(col[i],1,n+1);                for (int j = 1;j <= n;j++) {                    ans = Math.max(ans,col[i][j]*;                }            }            out.println;        }    }        static class InputReader{        public BufferedReader br;        public StringTokenizer tokenizer;                public InputReader(InputStream ins) {            br = new BufferedReader(new InputStreamReader;            tokenizer = null;        }                public String next(){            while (tokenizer==null || !tokenizer.hasMoreTokens {                try {                tokenizer = new StringTokenizer(br.readLine;                }catch(IOException e) {                    throw new RuntimeException;                }            }            return tokenizer.nextToken();        }                public int nextInt() {            return Integer.parseInt;        }                public long nextLong() {            return Long.parseLong;        }    }}
    

    题意

    给您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("%dn%d",-1,0):printf("%dn%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 %dn",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 %dn",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("%lldn",query(l,r,root).ans);
            }
        }
    }
    

     

    本文由美高梅网投网址发布于美高梅官方网站,转载请注明出处:每一个操作蕴含l、r、d

    关键词:

上一篇:在ubuntu中怎么样开荒终端,ls查看目录

下一篇:没有了