月度归档:2018年02月

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

dsu on tree

在cf上学的一个trick,一直听别人说这个就去看了看。。。
主要是用来统计无修改的情况下,一棵树每个节点的某些特征信息:如颜色数,众数等等。
概括来说:先把树的重儿子通过dfs找到。然后我们先统计轻儿子子树信息,然后在全局维护的答案里在清除掉。然后在统计重儿子子树信息,注意这时候不再清除。然后开始统计这个节点为根子树的信息。然后再根据这个节点是否为父亲节点的轻儿子来判断是否清除信息。
看一个简单题:CF600E
题意:统计每个节点子树内的众数。
就是全局维护一个cnt数组统计次数,以及一个maxx表示众数,sum表示答案。直接贴一个代码分析一下复杂度吧。

我们发现如果要暴力的话应该是每个节点向各个儿子的子树dfs下去统计完子树的答案后都清空,然后在统计这棵子树的答案。而dsu
on tree则是启发式了这个过程,即重儿子不清空只清空轻儿子。而且这个复杂度很对:我们考虑每个节点在这个整体过程会被update多少次即可。我们发现只要有这个节点走到根的过程中有轻边,就会被update一次。那么学过树链剖分都知道轻边最多logn条。那么复杂度就是O(nlogn)。

Leetcode 790. Domino and Tromino Tiling(dp)

题目链接
题意:给出一个2*n的棋盘用2*1的矩形骨牌和L型骨牌覆盖,求方案数。
这是今天中午的leetcode最后一题,窝记错时间了只剩半个小时才开始,最后rush了一波这个题,结果死于模数写错。
因为这两种骨牌可能构成两种形态,所以可以考虑设计成两维dp。dp[i][0]表示完全覆盖第i列,dp[i][1]表示剩一个格子。那么就可以转移了。
据说有个递推式:A(n)=A(n-1)*2+A(n-3)。