SSLOJ 1328 I Like Matrix Forever!
Description–
对一个 n ∗ m 的零矩阵 A 进行 q 次操作:
• 1 i j:将 Ai,j 取反;
• 2 i:将矩阵 A 第 i 行的所有元素全部取反;
• 3 j:将矩阵 A 第 j 列的所有元素全部取反;
• 4 k:将矩阵 A 还原为第 k 次操作之后的状态。
进行每一次操作之后,询问当前矩阵所有元素的和。
Input–
第一行包含三个整数 n,m 和 q。
之后 q 行每行包含两个或三个整数,表示一次操作的所有参数。
Output–
共 q 行每行包含一个整数 ans,表示当前矩阵所有元素的和。
Sample Input–
2 2 4
2 1
1 1 2
4 1
3 2
Sample Output–
2
1
2
2
说明–
对于 30% 的数据:n, m ≤ 300,q ≤ 1000
对于 60% 的数据:n, m ≤ 1000,q ≤ 5000
对于 100% 的数据:n, m ≤ 1000,q ≤ 100000
解题思路–
若是操作1~3就正常连,操作4的话就连到k。
代码–
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,o,t,s,a[100005],b[100005],tt[100005],ls[100005],ans[100005];
bool x[1005][1005];
struct hh
{
int x,next;
}f[100005];
int read()
{
int k=0;
char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9')
k=k*10+(c-'0'),c=getchar();
return k;
}
void op(int e)
{
if (e>9) op(e/10);
putchar(e%10+'0');
}
void fy(int ff,int y)
{
f[++t].x=y,f[t].next=ls[ff],ls[ff]=t;
}
void hhd(int l)
{
if (tt[l]==1)
{
x[a[l]][b[l]]=!x[a[l]][b[l]];
if (x[a[l]][b[l]]) s++;
else s--;
}
if (tt[l]==2)
for (int j=1;j<=m;++j)
{
x[a[l]][j]=!x[a[l]][j];
if (x[a[l]][j]) s++;
else s--;
}
if (tt[l]==3)
for (int j=1;j<=n;++j)
{
x[j][a[l]]=!x[j][a[l]];
if (x[j][a[l]]) s++;
else s--;
}
ans[l]=s;
for (int i=ls[l];i;i=f[i].next)
hhd(f[i].x);
if (tt[l]==1)
{
x[a[l]][b[l]]=!x[a[l]][b[l]];
if (x[a[l]][b[l]]) s++;
else s--;
}
if (tt[l]==2)
for (int j=1;j<=m;++j)
{
x[a[l]][j]=!x[a[l]][j];
if (x[a[l]][j]) s++;
else s--;
}
if (tt[l]==3)
for (int j=1;j<=n;++j)
{
x[j][a[l]]=!x[j][a[l]];
if (x[j][a[l]]) s++;
else s--;
}//回溯
}
int main()
{
n=read(),m=read(),o=read();
for (int i=1;i<=o;++i)
{
tt[i]=read();
if (tt[i]==1) a[i]=read(),b[i]=read();
else a[i]=read();
if (tt[i]==4) f[++t].x=i,f[t].next=ls[a[i]],ls[a[i]]=t;//连到a[i]
else f[++t].x=i,f[t].next=ls[i-1],ls[i-1]=t;//正常连
}
hhd(0);
for (int i=1;i<=o;++i)
op(ans[i]),putchar(10);
return 0;
}