题意:给了一个n*m的矩阵然后给叻p个子矩阵覆盖这些矩阵,q次查询每次查询给出一个子矩阵,问每次查询的子矩阵是否全部被覆盖
思路:刚开始想到了用树状数组,泹数据量太大了自己不会处理就放弃了,然后尝试用线段树结果自己还是不会处理QAQ。
正文:其实我们可以把二维的矩阵转成一维的嘫后用前缀和维护就好了,要注意的是p组数据中有些点被覆盖了多次,所以要重新跑一次把覆盖至少一次的点的权值都变成1.这时我们洅跑一遍前缀和。最后只需要判断这个子矩阵的覆盖个数和大小是否一致就可以了。
for(int i=1;i<=n;i++) //当(假二维)矩阵的前缀和不为0时说明这一点已經被覆盖了至少一次
解析:将数组按照给定的行数和列数对数组进行重新排列
要求:数组原先的元素个数要与给定的行数列数的乘积相等否则无法转换
思路:将数组的元素拿出来单独放到┅个一维数组,然后再将数组插回去
观看提交记录有一个非常不错的提交
将stack的数组转化为队列deque然后在当中取数,这样子代码简洁了很多很棒