Go to Luogu to read my blog
Ideas
The first thing that comes to mind is violence, because the words in the same line do not affect each other, so the words in the first line
1
1
1 must be operated, then update the subsequent status, and then operate all the operations in the second line
1
1
1, but unfortunately it is
O
(
n
4
)
O(n^4)
The complexity of O(n4) will inevitably be TLE.
So think about other methods, considering that you can count how many operations have changed the status of this location, so you can use a method similar to prefix sum.
As shown in the picture above, you can find that the status of the black box will be affected by the operation of the red box.
So find a way to count the total number of operations performed by the red box.
make
b
i
,
j
b_{i,j}
bi,j? represents the grid
(
i
,
j
)
(i,j)
(i,j) Whether operations have been performed,
c
i
,
j
c_{i,j}
ci,j? means everything will affect the grid
(
i
,
j
)
(i,j)
The total number of operations in the state (i, j), including the operations in this grid.
Let’s draw a simple picture:
Green is
c
i
?
1
,
j
?
1
c_{i-1,j-1}
ci?1,j?1? Individually involved areas, yellow
c
i
?
1
,
j
+
1
c_{i-1,j + 1}
ci?1,j + 1? The area involved alone, blue is
c
i
?
1
,
j
?
1
c_{i-1,j-1}
ci?1,j?1? and
c
i
?
1
,
j
+
1
c_{i-1,j + 1}
ci?1,j + 1? Commonly involved areas.
So it can be inferred that the formula is
c
i
,
j
=
c
i
?
1
,
j
?
1
+
c
i
?
1
,
j
+
1
?
c
i
?
2
,
j
+
b
i
?
1
,
j
c_{i,j}=c_{i-1,j-1} + c_{i-1,j + 1}-c_{i-2,j} + b_{i-1,j}
ci,j?=ci?1,j?1? + ci?1,j + 1ci?2,j? + bi?1,j?.
Then judge the status of this grid after so many operations, then judge whether operations are needed, and then change it.
c
i
,
j
c_{i,j}
ci,j? and
b
i
,
j
b_{i,j}
bi,j?.
Then I found that the samples were all wrong. After debugging, I found that it was the
j
=
1
j=1
j=1 or
j
=
m
j=m
An error occurred when j=m, so only special judgment is needed. This situation is simpler and the formula is:
c
i
,
j
=
c
i
?
1
,
j
+
1
+
b
i
?
1
,
j
c_{i,j}=c_{i-1,j + 1} + b_{i-1,j}
ci,j?=ci?1,j + 1? + bi?1,j? or
c
i
,
j
=
c
i
?
1
,
j
?
1
+
b
i
?
1
,
j
c_{i,j}=c_{i-1,j-1} + b_{i-1,j}
ci,j?=ci?1,j?1? + bi?1,j?.
AC code
#include<bits/stdc + + .h>
using namespace std;
int T,n,a[3005][3005],b[3005][3005],c[3005][3005],ans;
char ch[3005];
int main()
{<!-- -->
scanf("%d", & amp;T);
while(T--)
{<!-- -->
scanf("%d", & amp;n),ans=0;
for(int i=1;i<=n; + + i)
{<!-- -->
scanf("%s",ch + 1);
for(int j=1;j<=n; + + j)
{<!-- -->
b[i][j]=0,a[i][j]=ch[j]-'0';
}
}
for(int i=1;i<=n; + + i)
{<!-- -->
for(int j=1;j<=n; + + j)
{<!-- -->
if(j==1) c[i][j]=c[i-1][j + 1] + b[i-1][j];
else if(j==n) c[i][j]=c[i-1][j-1] + b[i-1][j];
else c[i][j]=c[i-1][j-1] + c[i-1][j + 1]-((i>=2)?c[i-2][j] :0) + b[i-1][j];
if((c[i][j]%2)^a[i][j]) + + c[i][j], + + ans,b[i][j]=1;
}
}
printf("%d\
",ans);
}
return 0;
}