「模拟8.13」任(liu_runda的神题，性质分析)-白红宇

「模拟8.13」任(liu_runda的神题，性质分析)

阅读量：5337 次

发布时间：2019-06-15

本文共 5826 字，大约阅读时间需要 19 分钟。

考场时没有发现性质，用了个前缀和优化暴力，结果写WA了

我们发现其实联通块的个数就是点的个数-边的个数

然后我们需要维护横向上和纵向上的边的前缀和

前缀和的查询形式稍改一下

暴力

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 #define int long long 11 #define MAXN 6001 12 using namespace std; 13 int read() 14 { 15 int x=0;char cc=getchar(); 16 while(cc<'0'||cc>'9')cc=getchar(); 17 while(cc>='0'&&cc<='9'){x=(x<<1)+(x<<3)+(cc^48);cc=getchar();} 18 return x; 19 } 20 char a[MAXN][MAXN]; 21 int sum[MAXN][MAXN]; 22 int c[MAXN][MAXN]; 23 int vis[MAXN][MAXN]; 24 int n,m; queue
               
                q_x;queue
                
                 q_y; 25 void BFS(int top_x,int top_y) 26 { 27 int maxn_x=top_x,maxn_y=top_y; 28 29 q_x.push(top_x);q_y.push(top_y); 30 vis[top_x][top_y]=1; 31 //belong[top_x][top_y]=cntt; 32 while(!q_x.empty()) 33 { 34 int x=q_x.front();int y=q_y.front();q_x.pop();q_y.pop(); 35 //belong[x][y]=cntt; 36 if(a[x-1][y]=='1'&&vis[x-1][y]==0) 37 { 38 q_x.push(x-1);q_y.push(y); 39 vis[x-1][y]=1; 40 maxn_x=max(maxn_x,x-1);maxn_y=max(maxn_y,y); 41 } 42 if(a[x][y-1]=='1'&&vis[x][y-1]==0) 43 { 44 q_x.push(x);q_y.push(y-1); 45 vis[x][y-1]=1; 46 maxn_x=max(maxn_x,x);maxn_y=max(maxn_y,y-1); 47 } 48 if(a[x+1][y]=='1'&&vis[x+1][y]==0) 49 { 50 q_x.push(x+1);q_y.push(y); 51 vis[x+1][y]=1; 52 maxn_x=max(maxn_x,x+1);maxn_y=max(maxn_y,y); 53 } 54 if(a[x][y+1]=='1'&&vis[x][y+1]==0) 55 { 56 q_x.push(x);q_y.push(y+1); 57 vis[x][y+1]=1; 58 maxn_x=max(maxn_x,x);maxn_y=max(maxn_y,y+1); 59 } 60 } 61 sum[maxn_x][maxn_y]++; 62 //mex[cntt]=maxn_x; 63 //mey[cntt]=maxn_y; 64 } 65 int q;int cnt; 66 int ans=0; 67 int get_sum(int x1,int y1,int x2,int y2) 68 { 69 return sum[x2][y2]+sum[x1-1][y1-1]-sum[x2][y1-1]-sum[x1-1][y2]; 70 } 71 int judge(int x,int y,int x1,int y1,int x2,int y2) 72 { 73 if(x
                 
                  x2)return 0;if(y
                  
                   y2)return 0; 74 return 1; 75 } 76 void BFS_S(int top_x,int top_y,int x1,int y1,int x2,int y2) 77 { 78 79 q_x.push(top_x);q_y.push(top_y); 80 vis[top_x][top_y]=1; 81 while(!q_x.empty()) 82 { 83 int x=q_x.front();int y=q_y.front();q_x.pop();q_y.pop(); 84 if(a[x-1][y]=='1'&&vis[x-1][y]==0&&judge(x-1,y,x1,y1,x2,y2)) 85 { 86 q_x.push(x-1);q_y.push(y); 87 vis[x-1][y]=1; 88 } 89 if(a[x][y-1]=='1'&&vis[x][y-1]==0&&judge(x,y-1,x1,y1,x2,y2)) 90 { 91 q_x.push(x);q_y.push(y-1); 92 vis[x][y-1]=1; 93 } 94 if(a[x+1][y]=='1'&&vis[x+1][y]==0&&judge(x+1,y,x1,y1,x2,y2)) 95 { 96 q_x.push(x+1);q_y.push(y); 97 vis[x+1][y]=1; 98 } 99 if(a[x][y+1]=='1'&&vis[x][y+1]==0&&judge(x,y+1,x1,y1,x2,y2))100 {101 q_x.push(x);q_y.push(y+1);102 vis[x][y+1]=1;103 }104 }105 }106 void work(int x1,int y1,int x2,int y2)107 {108 ans=0;109 for(int i=x1;i<=x2;++i)110 {111 //printf("i=%lld y1=%lld\n",i,y1);112 for(int j=y1;j<=y2;++j)113 {114 if(vis[i][j]==0&&a[i][j]=='1')115 {116 BFS_S(i,j,x1,y1,x2,y2);117 ans++;118 }119 }120 //printf("ans=%lld\n",ans);121 } 122 for(int i=x1;i<=x2;++i)for(int j=y1;j<=y2;++j)vis[i][j]=0;123 }124 signed main()125 {126 scanf("%lld%lld%lld",&n,&m,&q);127 for(int i=1;i<=n;++i)128 {129 scanf("%s",a[i]+1);130 }131 for(int i=1;i<=n;++i)132 {133 for(int j=1;j<=m;++j)134 {135 if(a[i][j]=='1'&&vis[i][j]==0)136 {137 BFS(i,j);138 }139 }140 }141 for(int i=1;i<=n;++i)142 {143 for(int j=1;j<=m;++j)144 {145 sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];146 }147 }148 memset(vis,0,sizeof(vis));149 for(int i=1;i<=q;++i)150 {151 int x1,y1,x2,y2;152 ans=0;153 x1=read();y1=read();x2=read();y2=read();154 //printf("x1=%lld y1=%lld x2=%lld y2=%lld\n",x1,y1,x2,y2);155 work(x1,y1,x2,y2);156 printf("%lld\n",ans);157 }158 }

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #define int long long11 #define MAXN 600112 using namespace std;13 int sum[MAXN][MAXN];14 int vis[MAXN][MAXN];15 int n,m;16 char a[MAXN][MAXN];17 int sum_lie[MAXN][MAXN],sum_hang[MAXN][MAXN];18 int q_x[MAXN],q_y[MAXN];19 void BFS(int top_x,int top_y)20 {21 int head,tail;22 head=1;tail=1;q_x[1]=top_x;q_y[1]=top_y;23 vis[top_x][top_y]=1;24 while(head<=tail)25 {26 int x=q_x[head];int y=q_y[head];head++;27 sum[x][y]++;//printf("add sum[%lld][%lld]=%lld\n",x,y,sum[x][y]);28 if(a[x][y-1]=='1')sum_hang[x][y]++;29 if(a[x-1][y]=='1')sum_lie[x][y]++;30 if(a[x][y+1]=='1'&&vis[x][y+1]==0)31 {32 vis[x][y+1]=1;q_x[++tail]=x;q_y[tail]=y+1;33 }34 if(a[x][y-1]=='1'&&vis[x][y-1]==0)35 {36 vis[x][y-1]=1;q_x[++tail]=x;q_y[tail]=y-1;37 }38 if(a[x-1][y]=='1'&&vis[x-1][y]==0)39 {40 vis[x-1][y]=1;q_x[++tail]=x-1;q_y[tail]=y;41 }42 if(a[x+1][y]=='1'&&vis[x+1][y]==0)43 {44 vis[x+1][y]=1;q_x[++tail]=x+1;q_y[tail]=y;45 }46 }47 } 48 int q;49 signed main()50 {51 scanf("%lld%lld%lld",&n,&m,&q);52 for(int i=1;i<=n;++i)53 {54 scanf("%s",a[i]+1);55 }56 for(int i=1;i<=n;++i)57 {58 for(int j=1;j<=m;++j)59 {60 if(vis[i][j]==0&&a[i][j]=='1')61 BFS(i,j);62 }63 } 64 for(int i=1;i<=n;++i)65 {66 for(int j=1;j<=m;++j)67 {68 sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];69 //printf("sum[%lld][%lld]=%lld\n",i,j,sum[i][j]);70 }71 } 72 for(int i=1;i<=n;++i)73 {74 for(int j=1;j<=m;++j)75 {76 sum_hang[i][j]+=sum_hang[i][j-1]+sum_hang[i-1][j]-sum_hang[i-1][j-1];77 sum_lie[i][j]+=sum_lie[i][j-1]+sum_lie[i-1][j]-sum_lie[i-1][j-1];78 }79 }80 for(int i=1;i<=q;++i) 81 {82 int x1,x2,y1,y2;83 scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);84 int tt=sum[x2][y2]+sum[x1-1][y1-1]-sum[x2][y1-1]-sum[x1-1][y2];85 int ttt=sum_hang[x2][y2]+sum_hang[x1-1][y1]-sum_hang[x2][y1]-sum_hang[x1-1][y2];86 int tttt=sum_lie[x2][y2]+sum_lie[x1][y1-1]-sum_lie[x2][y1-1]-sum_lie[x1][y2];87 //printf("tt=%lld ttt=%lld\n",tt,ttt);88 printf("%lld\n",tt-ttt-tttt);89 }90 }