首页 > 代码库 > CodeForces #368 div2 D Persistent Bookcase DFS
CodeForces #368 div2 D Persistent Bookcase DFS
题目链接：D Persistent Bookcase
题意：有一个n*m的书架，开始是空的，现在有k种操作：
1 x y 这个位置如果没书，放书。
2 x y 这个位置如果有书，拿走。
3 x 反转这一行，即有书的位置拿走，没书的位置放上书。
4 x 返回到第x步操作之后的书架。
现在给出q个操作，询问每次操作之后书架上书的数量。
思路：
开始没有思路。后来被告知dfs。
【词不达意。参考：http://blog.csdn.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 100100using 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;}确实很巧妙。
CodeForces #368 div2 D Persistent Bookcase DFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。