Codeforces #386 Ddfs+bitset

题目链接

相关知识

---

bitset使用 :http://blog.csdn.net/qll125596718/article/details/6901935

---

解析

---

本题的棘手之处在于题目中的第4个操作。在不能改变时间的情况下，状态只能随着时间的推进而转移（一维）。现在可以改变时间，那么状态的转移目的地就不唯一了，也就是说状态的转移会出现分叉。那么状态的转移的图示就从一个数轴变成了一棵树（二维）。如果我们能够构造出这棵树，就能在用 DFS 状态转移的同时计算出每个状态下的书本的数量了。

令询问 i 的时刻为 i ，并对每个时刻设立一个树节点。那么当操作编号为 1,2 或 3 的时候，我们就让 i−1 时刻到 i 时刻连一条单向边，当操作编号为 4 的时候相当于将时刻改变为 k ，那么我们就让 k 时刻到 i 时刻连一条单向边。这样就能构造出我们要的“状态转移树”了。

当然，要在状态转移的过程中计算出书本的数量也并非十分容易的事。关键就在于怎么表示状态。设时刻 i 书本的总数为 res ，我们定义一个 n×m 的矩阵，矩阵的每个元素代表书架的这个位置是否有书。在转移状态的过程中维护这个矩阵就能应付前两个操作（维护 res ），第三个操作要遍历一整行（修改，求和），能否避免这种遍历呢？bitset很好的节省了时间。

---

代码

#include<cstdio> #include<cstring> #include <iostream> #include <queue> #include <vector> #include <bitset> using namespace std; const int maxn = 1000+10; const int inf = 0x3f3f3f3f; typedef pair<int, int> P; int n, m, q; struct node { int com, i, j; }op[100000+10]; vector<int>g[100000+10]; int ans[100000+10]; int vis[100000+10]; bitset<maxn>bit[maxn]; int X[maxn]; int res; void dfs(int u) { ans[u] = res; for (int i=0; i<g[u].size(); i++) { int v = g[u][i]; int pre = res; bitset<1010>b; int tmp = X[op[v].i]; b = bit[op[v].i]; if (op[v].com == 1) { int x = op[v].i, y = op[v].j; if (!bit[x].test(y)) { res++; bit[x].set(y); } } else if (op[v].com == 2) { int x = op[v].i, y=op[v].j; if (bit[x].test(y)) { res--; bit[x].reset(y); } } else if (op[v].com == 3) { int x=op[v].i; if (X[x] % 2 == 0) { int num = b.count(); X[x]++; int ren = m-num; res += (ren-num); bit[x].flip(); } else { int num = bit[x].count()-1010+m; X[x]++; res += (m-2*num); bit[x].flip(); } } dfs(v); res = pre; bit[op[v].i] = b; X[op[v].i] = tmp; } } int main() { res = 0; scanf("%d%d%d", &n, &m, &q); for (int i=0; i<=q; i++) g[i].clear(); for (int i=1; i<=q; i++) { int com; scanf("%d", &com); if (com <= 2) { op[i].com = com; scanf("%d%d", &op[i].i, &op[i].j); g[i-1].push_back(i); } else if (com == 3) { op[i].com = com; scanf("%d", &op[i].i); g[i-1].push_back(i); } else if (com == 4) { int k; scanf("%d", &k); g[k].push_back(i); } } dfs(0); for (int i=1; i<=q; i++) printf("%d\n", ans[i]); return 0; }