标签归档:BZOJ

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,那么任意子区间必然值域连续。所以预处理每个数字向右最远的合法距离即可。

BZOJ 5131: [CodePlus2017年12月]可做题2(矩阵快速幂+扩欧)

题目链接
假设我们选了一个数\(x\),那么我们可以把这个广义斐波那契数列变成\(i,x,i+x,i+2x,2i+3x…\)这样的形式,可以发现i和x的系数也是一个斐波那契数列。那么我们可以用矩阵快速幂加速求出第k项的\(i\)的系数和\(x\)的系数。得到一个\(a*i+b*x = m (mod p)\)的式子。 也就是\(b*x = m-a*i (mod p)\)这个式子直接扩欧解出来在\([l,r]\)的有多少个解就好了。。

BZOJ 5132: [CodePlus2017年12月]火锅盛宴

题目链接
就是个简单的需要用数据结构维护的模拟吧,但是一开始觉得set很爽在loj上一直T了两个点,然后改成堆才发现堆才好写啊!bzoj上交错踢了RE了无数次。。。。