2 条题解

  • 0
    @ 2018-11-05 13:38:14
    # include <bits/stdc++.h>
    # define int long long
    using namespace std;
    const int TT=10000;
    int n,m;
    int random(int x) { return rand()*rand()%x;}
    int Fun(int low,int high)
    { return random(10000000) % (high - low + 1) + low;} 
    void work1()
    {
        int x=random(n)+1,y=random(m)+1;
        printf("F %d %d\n",x,y); 
    }
    void work2()
    {
        int x1=random(n)+1,y1=random(m)+1;
        int x2=Fun(x1,n),y2=Fun(y1,m);
        printf("Q %d %d %d %d\n",x1,y1,x2,y2);
    }
    void work3()
    {
        int x1=random(n)+1,y1=random(m)+1;
        int x2=Fun(x1,n),y2=Fun(y1,m);
        int d=random(2*TT+1)-TT;
        printf("A %d %d %d %d %d\n",x1,y1,x2,y2,d);
    }
    void work4()
    {
        int x1=random(n)+1,y1=random(m)+1;
        int x2=Fun(x1,n),y2=Fun(y1,m);
        int d=random(2*TT+1)-TT;
        printf("D %d %d %d %d %d\n",x1,y1,x2,y2,d);
    }
    signed main()
    {
        srand((unsigned long long)time(NULL)*19260817);
        puts("宽长:"); scanf("%d%d",&n,&m);
        int F,Q,A,D,R,T;
        puts("输入操作个数:"); scanf("%d",&T);
        puts("输入F操作的几率:");scanf("%d",&F);
        puts("输入Q操作的几率:");scanf("%d",&Q);
        puts("输入A操作的几率:");scanf("%d",&A);
        puts("输入D操作的几率:");scanf("%d",&D); 
        puts("输入干扰操作个数:");scanf("%d",&R);
        freopen("7.in","w",stdout);
        printf("%d %d\n",n,m);
        for (int i=1;i<=n;i++) {
          for (int j=1;j<=m;j++)
           printf("%d ",random(2*TT+1)-TT);
           puts("");
        }
        while (T--) {
            int opt=random(100);
            if (opt<F) work1();
            else if (opt<F+Q) work2();
            else if (opt<F+Q+A) work3();
            else work4();
        }
        puts("E");
        while (R--) {
            int opt=random(100);
            if (opt<F) work1();
            else if (opt<F+Q) work2();
            else if (opt<F+Q+A) work3();
            else work4();
        } 
        return 0;
    }
    
  • 0
    @ 2018-11-05 13:37:49

    solution:
    #5 5%的数据 打卡数据
    #1-#4 20%数据
    不采用快速读入输出的模拟
    #11-#12 10%数据
    采用快速读入输出的模拟(不就是卡了常数嘛)
    暴力程序:

    # include <bits/stdc++.h>
    # define int long long 
    using namespace std;
    const int MAXN=5005;
    int a[MAXN][MAXN],n,m;
    inline int read()
    {
        int X=0,w=0;char c=0;
        while (!(c>='0'&&c<='9')) w|=c=='-',c=getchar();
        while ((c>='0'&&c<='9')) X=(X<<1)+(X<<3)+(c^48),c=getchar();
        return w?-X:X;
    }
    inline void write(int x)
    {
        if (x<0) { putchar('-'); x=-x;}
        if (x>9) write(x/10);
        putchar('0'+x%10);
    }
    inline void writeln(int x){write(x);putchar('\n');}
    inline void work1()
    {
        int ans=0;
        int x1,y1,x2,y2;
        x1=read(),y1=read(),x2=read(),y2=read();
        for (int i=x1;i<=x2;i++)
         for (int j=y1;j<=y2;j++)
          ans+=a[i][j];
        writeln(ans);
    }
    inline void work2()
    {
        int x1,y1,x2,y2,d;
        x1=read(),y1=read(),x2=read(),y2=read(),d=read();
        for (int i=x1;i<=x2;i++)
         for (int j=y1;j<=y2;j++)
          a[i][j]+=d;
    }
    inline void work3()
    {
        int x1,y1,x2,y2,d;
        x1=read(),y1=read(),x2=read(),y2=read(),d=read();
        for (int i=x1;i<=x2;i++)
         for (int j=y1;j<=y2;j++)
          a[i][j]-=d;
    }
    inline void work4()
    {
        int x,y;
        x=read();y=read();
        writeln(a[x][y]);
    }
    signed main()
    {
        n=read();m=read();
        for (int i=1;i<=n;i++)
         for (int j=1;j<=m;j++)
          a[i][j]=read();
        char opt;  
        while (true) {
            cin>>opt;
            switch (opt) {
                case 'Q':work1();break;
                case 'A':work2();break;
                case 'D':work3();break;
                case 'F':work4();break;
                case 'E':goto exit;break;
            }
        }  
        exit:;
        return 0;
    }
    

    #6-#7 10%的数据维护区间加区间求和考虑线段树

    #8-#10 15%的数据没有区间求和操作,维护一颗二维树状数组

    #13-#20 40%的数据正解

    
    # pragma G++ optimze(2)
    # include<bits/stdc++.h>
    # define int long long
    using namespace std;
    const int MAXN=5005;
    int a[MAXN][MAXN],d[MAXN][MAXN];
    int n,m;
    inline int read()
    {
        int X=0,w=0;char c=0;
        while (!(c>='0'&&c<='9')) w|=c=='-',c=getchar();
        while ((c>='0'&&c<='9')) X=(X<<1)+(X<<3)+(c^48),c=getchar();
        return w?-X:X;
    }
    inline void write(int x)
    {
        if (x<0) { putchar('-'); x=-x;}
        if (x>9) write(x/10);
        putchar('0'+x%10);
    }
    inline void writeln(int x){write(x);putchar('\n');}
    struct Tree{
        int c[MAXN][MAXN];
        Tree(){ memset(c,0,sizeof(c));}
        inline void update(int x,int y,int z){
            for (int i=x;i<=n;i+=i&(-i))
             for (int j=y;j<=m;j+=j&(-j)){
                c[i][j]+=z;
             }
        }   
    }T1,T2,T3,T4;
    # define A (x+1)
    # define B (y+1)
    inline int ask(int x,int y){
        int ret=0;
        for (int i=x;i;i-=i&(-i))
         for (int j=y;j;j-=j&(-j))
          ret+=A*B*T1.c[i][j]-B*T2.c[i][j]-A*T3.c[i][j]+T4.c[i][j];
        return ret;  
    }
    inline void add(int x,int y,int val){
        T1.update(x,y,val);   T2.update(x,y,val*x);
        T3.update(x,y,val*y); T4.update(x,y,val*x*y);
    }
    inline void work1()
    {
        int x1=read(),y1=read(),x2=read(),y2=read();
        int ans=ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);
        writeln(ans);
    }
    inline void work2()
    {
        int x1=read(),y1=read(),x2=read(),y2=read(),d=read();
        add(x1,y1,d); add(x1,y2+1,-d);
        add(x2+1,y1,-d); add(x2+1,y2+1,d);
    }
    inline void work3()
    {
        int x1=read(),y1=read(),x2=read(),y2=read(),d=read(); d=-d;
        add(x1,y1,d); add(x1,y2+1,-d);
        add(x2+1,y1,-d); add(x2+1,y2+1,d);
    }
    inline void work4()
    {
        int x1=read(),y1=read();
        int x2=x1,y2=y1;
        int ans=ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);
        writeln(ans);
    }
    signed main()
    {
        #ifdef LOCAL
            freopen("input.in","r",stdin);
            freopen("output.out","w",stdout);
        #endif
        n=read();m=read();
        for (int i=1;i<=n;i++)
         for (int j=1;j<=m;j++) {
            a[i][j]=read();
            d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];  
         }
         for (int i=1;i<=n;i++)
          for (int j=1;j<=m;j++)
            add(i,j,d[i][j]);
          char opt;
          while (true) {
            cin>>opt;
            switch (opt) {
                case 'Q':work1();break;
                case 'A':work2();break;
                case 'D':work3();break;
                case 'F':work4();break;
                case 'E':goto exit;break;   
            }
          }
          exit:;
        return 0;
    } 
    
  • 1

信息

难度
10
分类
(无)
标签
(无)
递交数
10
已通过
0
通过率
0%
上传者