题意：有一个n*m的书架，开始是空的，现在有k种操作：
1 x y 这个位置如果没书，放书。
2 x y 这个位置如果有书，拿走。
3 x 反转这一行，即有书的位置拿走，没书的位置放上书。
4 x 返回到第x步操作之后的书架。
现在给出q个操作，询问每次操作之后书架上书的数量。
思路：
开始没有思路。后来被告知dfs。
【词不达意。参考：http://blog.****.net/zyjhtutu/article/details/52279494】
对于第i次操作的后的书架，要么是由第i-1次操作后的书架得到的，要么是返回到第x步。而，每一步得到的书架书的数量只有一种可能。
将操作看成边，当前的状态看作节点，建树。建树的规则是，如果进行的操作树1或者2或者3，那么就将操作后状态连接在当前状态后面
，如果操作是4，就将操作后的状态连接在要还原的状态后面。然后进行dfs，离线求解。dfs的巧妙之处在于，由于数据量比较大，不可
能将每次操作后的状态都记下来。其实，仔细想想，根本不需要记录所有的状态，只需要记录当前状态，然后dfs，回溯的时候将更改的
状态在改回来。这样，一边dfs就解决问题。时间复杂度为q*m。
附代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#define maxn 100100
using namespace std; vector<int> nxt[maxn];
int ans[maxn];
int op[maxn], r[maxn], c[maxn];
bool vis[1010][1010]; //标记当前状态是否已经有书
int n, m; void init() {
ans[0] = 0;
for (int i=1; i<=maxn; ++i) {
nxt[i].clear();
}
memset(vis, 0, sizeof(vis));
} void dfs(int x) {
for (int i=0; i<nxt[x].size(); ++i) {
int nxts = nxt[x][i]; // 从x出发能到达的所有状态
//cout << nxts << " " << op[nxts] << "...\n";
if (op[nxts] == 1) {
if (vis[r[nxts]][c[nxts]]) { // 已经有书
ans[nxts] = ans[x];
dfs(nxts);
}
else {
vis[r[nxts]][c[nxts]] = 1;
ans[nxts] = ans[x] + 1;
dfs(nxts);
vis[r[nxts]][c[nxts]] = 0;
}
}
else if (op[nxts] == 2) {
if (vis[r[nxts]][c[nxts]] == 0) { // 没书
ans[nxts] = ans[x];
dfs(nxts);
}
else {
vis[r[nxts]][c[nxts]] = 0;
ans[nxts] = ans[x] - 1;
dfs(nxts);
vis[r[nxts]][c[nxts]] = 1;
}
}
else if (op[nxts] == 3) {
int cnt = 0;
for (int j=1; j<=m; ++j) {
if (vis[r[nxts]][j] == 0) {
cnt++;
vis[r[nxts]][j] = 1;
}
else {
cnt--;
vis[r[nxts]][j] = 0;
}
}
ans[nxts] = ans[x] + cnt;
dfs(nxts);
for (int j=1; j<=m; ++j) {
if (vis[r[nxts]][j] == 0) {
vis[r[nxts]][j] = 1;
}
else vis[r[nxts]][j] = 0;
}
}
else if (op[nxts] == 4) {
ans[nxts] = ans[x];
dfs(nxts);
}
}
} int main() {
// freopen("in.cpp", "r", stdin);
int q;
while(~scanf("%d%d%d", &n, &m, &q)) {
init();
for (int i=1; i<=q; ++i) {
scanf("%d", &op[i]);
if (op[i] == 1 || op[i] == 2) {
scanf("%d%d", &r[i], &c[i]);
nxt[i-1].push_back(i);
}
else if (op[i] == 3) {
scanf("%d", &r[i]);
nxt[i-1].push_back(i);
}
else if (op[i] == 4) {
scanf("%d", &r[i]);
nxt[r[i]].push_back(i);
}
} dfs(0);
for (int i=1; i<=q; ++i) {
printf("%d\n", ans[i]);
}
}
return 0;
}
确实很巧妙。