I Like Matrix Forever!

题目

对一个 n ∗ m 的零矩阵 A 进行 q 次操作：

i j：将 Ai,j 取反；i：将矩阵 A 第 i 行的所有元素全部取反；j：将矩阵 A 第 j 列的所有元素全部取反；k：将矩阵 A 还原为第 k 次操作之后的状态。

进行每一次操作之后，询问当前矩阵所有元素的和。

输入

第一行包含三个整数 n，m 和 q。 之后 q 行每行包含两个或三个整数，表示一次操作的所有参数。

输出

共 q 行每行包含一个整数 ans，表示当前矩阵所有元素的和。

输入样例

2 2 4 2 1 1 1 2 4 1 3 2

输出样例

2 1 2 2

数据范围

对于 30% 的数据：n, m ≤ 300，q ≤ 1000 对于 60% 的数据：n, m ≤ 1000，q ≤ 5000 对于 100% 的数据：n, m ≤ 1000，q ≤ 100000

思路

这道题提我们用$dfs$的搜索树来做。 把它看作一棵树，每一次操作为一个节点，操作四为一个分支，然后dfs这条树，就可以了。

代码

#include<cstdio> using namespace std; struct note { int x,y,z; }a[100001]; struct notte { int to,next; }f[100001]; int n,m,q,le[100001],b[1001][1001],ans[100001],k; int read()//快读 { int rr=0;char c=getchar(); while (c>='0'&&c<='9') { rr=rr*10+c-48; c=getchar(); } return rr; } void write(int x)//快输 { if(x>9) write(x/10); putchar(x%10+48); return; } void dfs(int x,int y)//dfs { ans[x]=y;//初始化 if (a[x].x==1)//操作1 { b[a[x].y][a[x].z]=(b[a[x].y][a[x].z]+1)%2;//取反 if (b[a[x].y][a[x].z]) ans[x]++;//统计元素和 else ans[x]--;//统计元素和 for (int i=le[x];i;i=f[i].next) dfs(f[i].to,ans[x]);//dfs此节点的每一个子节点 b[a[x].y][a[x].z]=(b[a[x].y][a[x].z]+1)%2;//回溯 } else if (a[x].x==2)//操作2 { for (int i=1;i<=m;i++) { b[a[x].y][i]=(b[a[x].y][i]+1)%2;//取反 if (b[a[x].y][i]) ans[x]++;//统计元素和 else ans[x]--;//统计元素和 } for (int i=le[x];i;i=f[i].next) dfs(f[i].to,ans[x]);//dfs此节点的每一个子节点 for (int i=1;i<=m;i++) b[a[x].y][i]=(b[a[x].y][i]+1)%2;//回溯 } else if (a[x].x==3)//操作3 { for (int i=1;i<=n;i++) { b[i][a[x].y]=(b[i][a[x].y]+1)%2;//取反 if (b[i][a[x].y]) ans[x]++;//统计元素和 else ans[x]--;//统计元素和 } for (int i=le[x];i;i=f[i].next) dfs(f[i].to,ans[x]);//dfs此节点的每一个子节点 for (int i=1;i<=n;i++) b[i][a[x].y]=(b[i][a[x].y]+1)%2;//回溯 } else for (int i=le[x];i;i=f[i].next)//操作4 dfs(f[i].to,ans[x]);//dfs此节点的每一个子节点 } int main() { n=read();m=read();q=read();//读入 for (int i=1;i<=q;i++) { a[i].x=read();a[i].y=read();//读入 if (a[i].x==1) a[i].z=read();//读入 if (a[i].x!=4) {f[++k]=(notte){i,le[i-1]};le[i-1]=k;}//建邻接表 else {f[++k]=(notte){i,le[a[i].y]};le[a[i].y]=k;}//建邻接表 } dfs(0,0);//dfs for (int i=1;i<=q;i++) {write(ans[i]);putchar('\n');}//输出 return 0; }