首页 > 代码库 > CodeForces 707D Persistent Bookcase ——（巧妙的dfs）
CodeForces 707D Persistent Bookcase ——（巧妙的dfs）
一个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\n",ans[i]);54 }
CodeForces 707D Persistent Bookcase ——（巧妙的dfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。