BZOJ 5136 & 5127(两道类似的题)

这是最近做到的两个题,题目都是给出任意这个条件下的一些限制,从而发现一些容易check的条件,然后预处理出来信息。这么说可能不太明白还是看题吧。。
5136
题意:对于任何一个 n 阶方阵,若任意从其中选择 n 个不同行不同列的位置,其上的权值
之和均相等,则我们称这个矩阵是巧妙的。注意对于 n = 1 的任何矩阵都是巧妙的。例
如矩阵
1 2 3
4 5 6
7 8 9
是巧妙的,因为 1 + 5 + 9 = 1 + 6 + 8 = 2 + 4 + 9 = 2 + 6 + 7 = 3 + 5 + 7 =
3 + 4 + 8 = 15, 而矩阵 1 2
2 1
不巧妙,因为 1 + 1 , 2 + 2。
现在有一个 n × m 大小的矩阵 M 以及 T 个询问,每次询问其一个子方阵是否是巧
妙的。


可以发现一个矩阵是巧妙的等价于他的任何一个二阶子矩阵都是巧妙的,否则假如一个二阶子矩阵不满足这个性质那么我们换一下这个矩阵的选择方式就可以发现它不是巧妙的。。。
二阶矩阵巧妙满足每一行的差值相同,所以可以预处理出来每个二阶子矩阵是否可行。然后二维前缀和就可以统计k阶矩阵的答案了。具体看代码吧。

5127
题意:给出一个序列若干询问,check一段区间内的任意一个子区间都满足所有数字值域连续。
因为要任意,所以最小的子区间必须要满足就是相邻的两个数差值不能超过1,否则直接就不满足了。而假如一个区间所有相邻数差值都不超过1,那么任意子区间必然值域连续。所以预处理每个数字向右最远的合法距离即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注