一个n*m的矩阵，有四种操作：
1.（i，j）处变1；
2.（i，j）处变0；
3.第i行的所有位置1，0反转；
4.回到第k次操作以后的状态；
问每次操作以后整个矩阵里面有多少个1。
其实不好处理的操作只有第四个，但是这题的思路很巧妙，123三种操作全部建立顺边，第四种操作将k和这次操作的序号建边，然后dfs进行操作即可，遇到尽头，则退回到前一个分岔点，并且回溯的过程中将操作反转。
具体见代码：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <vector> 5 using namespace std; 6 const int N = 100000 + 5; 7 8 int n,m,q,op[N],x[N],y[N],a[1000+5][1000+5]; 9 vector<int> G[N]; 10 int cnt = 0,ans[N]; 11 12 void dfs(int u) 13 { 14 bool have_changed = 0; 15 if(op[u]==1 && a[x[u]][y[u]]==0) {have_changed = true;a[x[u]][y[u]] = 1;cnt++;} 16 if(op[u]==2 && a[x[u]][y[u]]==1) {have_changed = true;a[x[u]][y[u]] = 0;cnt--;} 17 if(op[u]==3) 18 { 19 have_changed = true; 20 for(int i=1;i<=m;i++) 21 { 22 if(a[x[u]][i] == 1) {cnt--;a[x[u]][i] = 0;} 23 else {cnt++;a[x[u]][i] = 1;} 24 } 25 } 26 ans[u] = cnt; 27 for(int i=0;i<G[u].size();i++) dfs(G[u][i]); 28 if(!have_changed) return; 29 if(op[u]==1) {a[x[u]][y[u]] = 0;cnt--;} 30 if(op[u]==2) {a[x[u]][y[u]] = 1;cnt++;} 31 if(op[u]==3) 32 { 33 for(int i=1;i<=m;i++) 34 { 35 if(a[x[u]][i] == 1) {cnt--;a[x[u]][i] = 0;} 36 else {cnt++;a[x[u]][i] = 1;} 37 } 38 } 39 } 40 41 int main() 42 { 43 scanf("%d%d%d",&n,&m,&q); 44 for(int i=1;i<=q;i++) 45 { 46 scanf("%d",op+i); 47 if(op[i]<=2) scanf("%d%d",x+i,y+i); 48 else scanf("%d",x+i); 49 if(op[i] == 4) G[x[i]].push_back(i); 50 else G[i-1].push_back(i); 51 } 52 for(int i=0;i<G[0].size();i++) dfs(G[0][i]); 53 for(int i=1;i<=q;i++) printf("%d ",ans[i]); 54 }