外贸网站怎么做关键词,建设电影网站赚钱,建网站报价明细表,网站自适应布局 html5I Like Matrix Forever!
题目大意#xff1a;
有一个01矩阵#xff0c;有一些操作#xff1a;反转一个位置的数#xff0c;反转一行的数#xff0c;反转一列的数#xff0c;回到第i次操作#xff0c;每一次操作还要输出1的个数
原题#xff1a;
题目描述
对一个 n…I Like Matrix Forever!
题目大意
有一个01矩阵有一些操作反转一个位置的数反转一行的数反转一列的数回到第i次操作每一次操作还要输出1的个数
原题
题目描述
对一个 n ∗ m 的零矩阵 A 进行 q 次操作 • 1 i j将 Ai,j 取反 • 2 i将矩阵 A 第 i 行的所有元素全部取反 • 3 j将矩阵 A 第 j 列的所有元素全部取反 • 4 k将矩阵 A 还原为第 k 次操作之后的状态。 进行每一次操作之后询问当前矩阵所有元素的和。
输入
第一行包含三个整数 nm 和 q。 之后 q 行每行包含两个或三个整数表示一次操作的所有参数。
输出
共 q 行每行包含一个整数 ans表示当前矩阵所有元素的和。
输入样例
2 2 4
2 1
1 1 2
4 1
3 2输出样例
2
1
2
2说明
对于 30% 的数据n, m ≤ 300q ≤ 1000 对于 60% 的数据n, m ≤ 1000q ≤ 5000 对于 100% 的数据n, m ≤ 1000q ≤ 100000
解题思路
实际上可以把它看作一棵树每一次操作为一个节点操作四为一个分支然后每次返回是再翻一遍 然后模拟即可
代码
#includecstdio
using namespace std;
int n,m,q,w,sum,l[100005],x[100005],y[100005],head[100005],ans[100005],a[1005][1005];
struct rec
{int to,next;
}e[100005];
int read()//快读
{char xxgetchar();int d1,ll0;while (xx0||xx9) {if (xx-) d-1; xxgetchar();}while (xx0xx9) ll(ll3)(ll1)xx-48,xxgetchar();return ll*d;
}
void writ(int c) {if (c9) writ(c/10); putchar(c%1048); return;}
void write(int s) {s0?putchar(45),writ(-s):writ(s); return;}
void lj(int xx,int yy)//连接
{e[w].toyy;e[w].nexthead[xx];head[xx]w;
}
void dfs(int dep)//深搜
{if (l[dep]1)//模拟{sum1-(a[x[dep]][y[dep]]1);//答案随这个数改变而改变a[x[dep]][y[dep]]^1;//取反}if (l[dep]2){for (int i1;im;i){sum1-(a[x[dep]][i]1);a[x[dep]][i]^1;}}if (l[dep]3){for (int i1;in;i){sum1-(a[i][x[dep]]1);a[i][x[dep]]^1;}}ans[dep]sum;for (int ihead[dep];i;ie[i].next) dfs(e[i].to);//深搜if (l[dep]1)//翻回来{sum1-(a[x[dep]][y[dep]]1);a[x[dep]][y[dep]]^1;}if (l[dep]2){for (int i1;im;i){sum1-(a[x[dep]][i]1);a[x[dep]][i]^1;}}if (l[dep]3){for (int i1;in;i){sum1-(a[i][x[dep]]1);a[i][x[dep]]^1;}}return;
}
int main()
{nread();mread();qread();for (int i1;iq;i){l[i]read();x[i]read();if (l[i]1) y[i]read();if (l[i]^4) lj(i-1,i);//分支else lj(x[i],i);}dfs(0);for (int i1;iq;i) write(ans[i]),putchar(10);//输出
}
