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

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

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

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

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

暴力

  1 #include<cstdio>

  2 #include<iostream>

  3 #include<cstdio>

  4 #include<cstring>

  5 #include<cmath>

  6 #include<algorithm>

  7 #include<set>

  8 #include<vector>

  9 #include<queue>

 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<int>q_x;queue<int>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<x1)return 0;if(x>x2)return 0;if(y<y1)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 }

 1 #include<cstdio>

 2 #include<iostream>

 3 #include<cstdio>

 4 #include<cstring>

 5 #include<cmath>

 6 #include<algorithm>

 7 #include<set>

 8 #include<vector>

 9 #include<queue>

10 #define int long long

11 #define MAXN 6001

12 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 }

巴特西

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

最新文章

热门文章