D题 Olya and magical square
题目链接：http://codeforces.com/contest/1080/problem/D
题意：
对一个初始边长为2^n的正方形，执行若干次划分操作：选一个现有的完整正方形，讲其按“十字型”划分成4个相同的小正方形
要求判断是否能在k次划分操作之后，使得左下角的正方形能找到一条“路径”到达右上角的正方形，并输出左下角小正方型的边长
对路径的要求：路径上相邻的两个正方形的边长必须相同
思路：
首先可以将这条路径放置在整个区域的左上两条边上，如图所示
image.png
我们需要计算这两个值：当左下角正方形边长为2^k时，在保证这条路径存在的前提下最少要切多少次，以及最多可以切多少次
先计算最多需要的次数F(n)：
image.png
对于一个边长为2^n的矩形，最多的分割次数是最后都分割成边长为1的小正方形，需要的分割次数记为f[n]
由递推公式f[n]=4f[n-1]+1得到f[n]=(4^n-1)/3
而为了保证外侧边长为为2^k ,我们切最外侧两条边上这2(2^n) / (2^k) - 1个小正方形的“刀”都得“收回”，而每个小正方形的切割次数是f[k]
于是可以得到，最多的分割次数F(n)=f[n]-((2^(n-k+1)-1)*f[k]
再计算最少需要的次数G(n)：
image.png
由递推公式G(n)=G(n-1)+2^n-1 得到G(n)=2^(n+1)-(n+2)
由于g(n)与f(n)都是指数函数，增长的速度非常快，所以从小到大枚举左下角小正方形的边长，计算k是否满足G(n)<=k<=F(n)即可
E题 Sonya and Matrix Beauty
题目链接：http://codeforces.com/contest/1080/problem/E
题意：
给出一个字符矩阵，求有多少个子矩阵满足如下性质：
对于子矩阵的每一行（注意不是列），可以对字符任意排序，使得子矩阵的每一行每一列都是回文串
思路：
如果一个字符经过排序之后可以变成一个回文串，则要求它的字母中出现奇数次的数量<=1
而对于两行回文串，他们组成的矩阵的每一列都是回文，则要求他们每个字母出现的次数相同
于是可以枚举子矩阵的行的起止位置，将每一行看成一个整体，于是一个p行q列的矩阵就“退化“成一个q个元素的”字符串“
再对这个“字符串”求回文子串的个数即可
注意求字符串回文子串个数的朴素做法是O(n^2), 加上本身需要O(n^2) 枚举矩形，所以最后是O(n^4),肯定会超时
这时候就需要用马拉车算法来O(n)计算回文子串的个数了
F题 Katya and Segments Sets
题目链接：http://codeforces.com/contest/1080/problem/F
题意：
给出n个集合，每个集合有若干个区间(例如[2,3],[3,5]),询问m次，每次询问第a到第b个集合中，是否都至少含有一个区间在[l,r]内(即l<=x<=y<=r)
思路：
假设n个集合一共有k个区间，按左端点从小到大排序得到一个序列seg[]，将这k个区间按最左端点分类，最多可以构成k棵线段树
每棵线段树Tree[i]负责计算最左端点为seg[i]时，集合[a,b]内的最大右端点。
对于一次询问，首先找到x>=l的第一棵树，再判断其中[a,b]的最大y是否<=r即可
由于要保证第i棵树中不包含比seg[i]左端点小的区间，需要按从右到做的顺序依次添加区间，而这个过程可以通过可持久化线段树（主席树）来做
网友评论