首页 > 代码库 > CodeForces 707D Persistent Bookcase

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 \right]} \right)\% 2$。 这样记录的话可以$O(1)$效率进行状态改变。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}struct X{    int t,r,c,k,id;    bool f;}s[100010];int sz;int h[1010],r[1010],a[1010][1010];int ans,n,m,k;vector<int>G[100010];int Ans[100010];void work1(int op,int tag){    if(tag==0)    {        if((a[s[op].r][s[op].c]+r[s[op].r])%2==1) return;        s[op].f=1; a[s[op].r][s[op].c]++; h[s[op].r]++; ans++;    }    else    {        if(s[op].f==0) return ;        a[s[op].r][s[op].c]--; h[s[op].r]--; ans--; s[op].f=0;    }}void work2(int op,int tag){    if(tag==0)    {        if((a[s[op].r][s[op].c]+r[s[op].r])%2==0) return;        s[op].f=1; a[s[op].r][s[op].c]--; h[s[op].r]--; ans--;    }    else    {        if(s[op].f==0) return;        a[s[op].r][s[op].c]++; h[s[op].r]++; ans++; s[op].f=0;    }}void work3(int op,int tag){    if(tag==0)    {        s[op].f=1;        ans=ans-h[s[op].r]+(m-h[s[op].r]);        h[s[op].r]=m-h[s[op].r];        r[s[op].r]++;    }    else    {        ans=ans-h[s[op].r]+(m-h[s[op].r]);        h[s[op].r]=m-h[s[op].r];        r[s[op].r]--; s[op].f=0;    }}void dfs(int x){    if(s[x].t==1) work1(x,0);    else if(s[x].t==2) work2(x,0);    else if(s[x].t==3) work3(x,0);    for(int i=0;i<G[x].size();i++)        dfs(G[x][i]);    Ans[x]=ans;    if(s[x].t==1) work1(x,1);    else if(s[x].t==2) work2(x,1);    else if(s[x].t==3) work3(x,1);}int main(){    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=k;i++)    {        scanf("%d",&s[i].t); int from=i-1;        if(s[i].t==1) scanf("%d%d",&s[i].r,&s[i].c);        else if(s[i].t==2) scanf("%d%d",&s[i].r,&s[i].c);        else if(s[i].t==3) scanf("%d",&s[i].r);        else scanf("%d",&from);        G[from].push_back(i);    }    s[0].t=4; dfs(0);    for(int i=1;i<=k;i++) printf("%d\n",Ans[i]);    return 0;}

 

CodeForces 707D Persistent Bookcase