cf707D. Persistent Bookcase(离线+dfs)

题目链接:http://codeforces.com/problemset/problem/707/D

 有一个n*m的书架,有K个操作,求每个操作后一共有多少本书;有4种操作;

1:x y 如果 x y 位置没有书,放一本书在上面;

2:x y如果 x y 位置有书,移走;

3:x,表示把第x行的所有又书的拿走,没书的放上去;

4:k,回到第k个操作后的状态;

离线处理k个操作;当操作不为 4 时,把操作i连在i-1后,=4时把操作 i 连在a[i].x后;

这样建一棵树,然后遍历即可,在回溯的时候注意更改书架的状态即可;

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define N 1005
#define PI 4*atan(1.0)
#define mod 1000000007
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL;

struct node
{
    int op, x, y, ans;
}a[N*N];///k个操作;

int cnt[N][N];///记录书架的状态;
int n, m, k;
vector<vector<int> > G;///操作形成的图;

void dfs(int u)
{
    if(a[u].op == 1)
    {
        int flag = 0;
        if(cnt[a[u].x][a[u].y] == 0)
        {
            flag = 1;
            a[u].ans ++;///在已有的基础上加上更改的值;
            cnt[a[u].x][a[u].y] = 1;///标记状态;
        }
        for(int i=0, len=G[u].size(); i<len; i++)
        {
            int v = G[u][i];
            a[v].ans = a[u].ans;///往下走的时候,v是u的儿子,所以拥有u的ans;
            dfs(v);
        }
        if(flag)///回溯时要重新更改状态;
            cnt[a[u].x][a[u].y] = 0;
    }
    else if(a[u].op == 2)
    {
        int flag = 0;
        if(cnt[a[u].x][a[u].y] == 1)
        {
            flag = 1;
            a[u].ans --;
            cnt[a[u].x][a[u].y] = 0;
        }
        for(int i=0, len=G[u].size(); i<len; i++)
        {
            int v = G[u][i];
            a[v].ans = a[u].ans;
            dfs(v);
        }
        if(flag)
            cnt[a[u].x][a[u].y] = 1;
    }
    else if(a[u].op == 3)
    {
        int num = 0;
        for(int i=1; i<=m; i++)
        {
            if(cnt[a[u].x][i] == 1)
                num ++;
            cnt[a[u].x][i] ^= 1;
        }
        a[u].ans = a[u].ans - num + (m-num);///更新ans;
        for(int i=0, len=G[u].size(); i<len; i++)
        {
            int v = G[u][i];
            a[v].ans = a[u].ans;
            dfs(v);
        }
        for(int i=1; i<=m; i++)
            cnt[a[u].x][i] ^= 1;
    }
    else
    {
        for(int i=0, len=G[u].size(); i<len; i++)
        {
            int v = G[u][i];
            a[v].ans = a[u].ans;
            dfs(v);
        }
    }
}

int main()
{
    while(scanf("%d %d %d", &n, &m, &k)!=EOF)
    {
        met(a, 0);
        met(cnt, 0);
        G.clear();
        G.resize(k+5);

        for(int i=1; i<=k; i++)
        {
            scanf("%d", &a[i].op);
            if(a[i].op <= 2)
                scanf("%d %d", &a[i].x, &a[i].y);
            else
                scanf("%d", &a[i].x);

            if(a[i].op <= 3)
                G[i-1].push_back(i);
            else
                G[a[i].x].push_back(i);
        }

        for(int i=0, len=G[0].size(); i<len; i++)
            dfs(G[0][i]);

        for(int i=1; i<=k; i++)
            printf("%d\n", a[i].ans);
    }
    return 0;
}

时间: 08-20

cf707D. Persistent Bookcase(离线+dfs)的相关文章

【Codeforces-707D】Persistent Bookcase DFS + 线段树

D. Persistent Bookcase Recently in school Alina has learned what are the persistent data structures: they are data structures that always preserves the previous version of itself and access to it when it is modified. After reaching home Alina decided

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/5227949

lca 欧拉序+rmq(st) 欧拉序+rmq(线段树) 离线dfs

https://www.luogu.org/problemnew/show/P3379 1.欧拉序+rmq(st) 1 /* 2 在这里,对于一个数,选择最左边的 3 选择任意一个都可以,[left_index,right_index],深度都大于等于这个数的深度 4 */ 5 #include <cstdio> 6 #include <cstdlib> 7 #include <cmath> 8 #include <cstring> 9 #include &

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>

codeforces 707D:Persistent Bookcase

Description Recently in school Alina has learned what are the persistent data structures: they are data structures that always preserves the previous version of itself and access to it when it is modified. After reaching home Alina decided to invent

CodeForces 707D Persistent Bookcase

$dfs$,优化. $return$操作说明该操作完成之后的状态和经过操作$k$之后的状态是一样的.因此我们可以建树,然后从根节点开始$dfs$一次(回溯的时候复原一下状态)就可以算出所有状态的答案. 对于$1$和$2$操作,可以开一个数组$a[i][j]$记录每一格子被操作$1$和$2$操作了几次. 然后开一个数组$r[i]$记录每一行被操作$3$操作了几次. 每一个真正的状态为$\left( {a\left[ i \right]\left[ j \right] + r\left[ i \ri

【深搜】【数】Codeforces 707D Persistent Bookcase

题目链接: http://codeforces.com/problemset/problem/707/D 题目大意: 一个N*M的书架,支持4种操作 1.把(x,y)变为有书. 2.把(x,y)变为没书. 3.把x行上的所有书状态改变,有变没,没变有. 4.回到第K个操作时的状态. 求每一次操作后书架上总共多少书. 题目思路: [深搜][树] 现场有一点思路不过没敢写哈.还是太弱了. 总共只用保存一张图,把操作看成一棵树,一开始I操作连接在I-1操作后,如果遇到操作4的话,把I操作与I-1操作的

[SinGuLaRiTy] 动态规划题目复习

[SinGuLaRiTy-1026] Copyright (c) SinGuLaRiTy 2017. All Rights Reserved. [UVA 1025] A Spy in the Metro 题目描述 特工玛利亚被送到S市执行一个特别危险的任务.她需要利用地铁完成他的任务,S市的地铁只有一条线路运行,所以并不复杂. 玛利亚有一个任务,现在的时间为0,她要从第一个站出发,并在最后一站的间谍碰头.玛利亚知道有一个强大的组织正在追踪她,她知道如果一直呆在一个车站,她会有很大的被抓的风险,躲

Codeforces Round #368 (Div. 2) ABCD

A. Brain's Photos 题解: 水得不要不要的 代码: #include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define se second #define fs first #define LL long long #define CLR(x) memset(x,0,sizeof x) #define MC(x,y) memcpy(x,y,sizeof(x)