BZOJ4236~4247
YYY
posted @ 2016年2月25日 20:15
in 算法竞赛
with tags
分治 逆序对 二叉搜索树 莫队算法 分块 二分答案 并查集 DFS 最小生成树 倍增 BFS
, 778 阅读
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
赶脚这几道题都比较有意思，大概会慢慢把这几道都做完吧...（已立下flag）
以下是简单思路（还没做完，慢慢补全）
-----------------------------------------------------------------------
P4236:考虑对于位置x，求出离他最远的一个点y(y<x)满足[y+1,x]这个区间内的子串满足条件，设前x个字符j,o,i的个数分别为fj(x),fo(x),fi(x),那么对于y，一定满足fj(x)-fj(y)=fo(x)-fo(y)=fi(x)-fi(y)
这个等式实际上包含了两个等式：
fj(x)-fj(y)=fo(x)-fo(y)
fo(x)-fo(y)=fi(x)-fi(y)
化一下，下标相同的弄到同一侧：
fj(x)-fo(x)=fj(y)-fo(y)
fo(x)-fi(x)=fo(y)-fi(y)
可见只需x,y的fj-fo以及fo-fi相同就可以了
因此问题就变成的寻找这个点前面离他最远的fj-fo和fo-fi都与这个点相同的点
map搞一搞就好了
-----------------------------------------------------------------------
P4237:
按x坐标分治，两边的递归处理，现在只需考虑跨过了mid的答案
枚举左边的点，设对于点d,设d的纵坐标为g(d),设f(d)是比d的x坐标大（但是小于等于mid)的不低于g(d)最低点的y坐标（没有就是无穷大），
显然只需要对mid右边的纵坐标在[g(d),f(d)]之间的点维护一个下降序列就行了（这里是指，从第一个点开始，遇到比序列最后一个元素还低的点就加入序列），现在考虑如果g(d)或者f(d)改变了会怎么样，改变有两种：变紧或者变松，以f(d)变化为例
变紧也就是会有元素被删掉，如果一个元素被删掉了，那么他低的元素一定也被删掉了，因此序列的一个后缀会被删除
变松也就是有元素会加进来，如果一个元素加进来，考虑他会出现在序列的哪个位置，如果他低于序列中x比他小的最低元素，那么说明他应该被加入序列，因此把他加入序列，而序列中他后面所有比他高的元素都应该删除，因此序列会在中间插入一个值，会有一个区间被删掉
因此可以用splay维护一下这个序列
...
...
...
好吧其实这个思路是错的因为根本不能保证每个点的删除以及加入次数（可以用莫队，但是复杂度还是太高了），我写下来只是因为感觉都想了这么多了可惜了...
然后我就滚去看题解了...
标算是对y分治，每一层对上方维护一个单调上升栈，下层维护一个单调下降栈，元素处理顺序按x坐标排序，每个上层点的答案就是处理到他的时候（还没入栈的时候）下层单调栈里面x大于上层栈中栈顶元素的x的元素个数
时间复杂度O(n*log*log)
-----------------------------------------------------------------------
P4239:
简单题
首先按发车时间排序
设f(i)表示如果上了i号车，最早到达学校时间
设s[i],t[i],st[i],ed[i]分别表示i号车的出发点、到达点、出发时间、到达时间
倒着枚举边，如果t[i]=N，那么f(i)=ed[i]
否则f(i)=min{f(j)|s[j]=t[i]且st[j]>=ed[i]}
也就是t[i]这个点发车时间比ed[i]晚的点的f最小值（因为是按发车时间倒着搞的，所以这些车的f一定已经求出来了)
把以每个点为起点的车按发车时间排序，二分得到最早的发车时间比他晚的，然后询问一下f的后缀最小值就行了
最后统计答案的时候，先二分答案mid，考虑验证，也就是要求是否存在从1号点出发的st大于等于mid,f小于等于l的点
按st排序，二分答案，询问一下后缀最小值即可
-----------------------------------------------------------------------
P4240:
显然最后是一个上升再下降的序列
显然对于一个序列，他的最小元素有两种选择：放到最左边或者放到最右边
对元素从小到大处理，每个元素看他是放到最左边还是最右边（选择最近的一端），然后删掉这个元素，并记一下他在最终序列中的位置，对剩下的子序列递归处理。
这样就得到了最终序列，只需要求原序列和他的距离（变成他需要的步数），求个逆序对就可以了（方法①）
但是不用这样做，发现每次处理的时候当前数都是序列中最小的，因此向左移动的步数就是左边比他大的元素个数，向右移动的步数就是右边比他大的元素个数，因此每个元素对这两个值取个min就行了（方法②）
我本来以为方法①和方法②等价，但是并不，方法①是错的，原因就在于我们处理的时候是假设当前元素是当前最小的，但是因为有重复的元素存在，所以方法①处理的时候当前元素可能不是对于<=这个关系而言的极小元素，因此需要跳过和自己一样大的元素
-----------------------------------------------------------------------
P4241:
写了个莫队+线段树，本机不开O2 6s+,交上去T了...
心累..
后来神犇CZH听说这道题后，一眼秒出了标算：
首先莫队
考虑如何O(1)维护,O(n^0.5)询问
方法就是对答案分块
因为答案只有n种，先离散化
然后f[i]表示答案i处出没出现（出现了几次）
g[i]表示第i块内的答案出没出现（出现了几次）
这个是可以O(1)维护的
然后每一次询问的时候首先找到最大的出现过答案的块，然后在这个块里面找最大的值，这个过程是O(n^0.5)的
然后复杂度就是O(n^1.5)的
注意这里为了保证复杂度离散化的时候不能用map，要用哈希表（哪怕开了O2的map是O(1)的也不行）
然后这里哈希表的实现有个小技巧：
首先把原序列离散化,然后发现答案都是原序列元素的整数倍，所以f[i][j]表示原序列元素i的j倍这个答案的编号
然后要动态开内存保证空间不会爆
话说，bzoj的时限有毒，我在本机卡到2s+交上去还是T,卡到1s以内才过..
-----------------------------------------------------------------------
P4242:
首先只要跑一个最小生成树写出来就可以了
然后我就吓懵了，这是要我O(n)跑一个最小生成树出来？
首先想到的是Burovka算法，每次BFS找一个离每个个连通块最近的点出来
然后发现不用这样，每次BFS出来得到的最近点一定是BFS区域和这个点BFS区域相接的点，所以直接BFS，每当两块区域相遇的时候，把他们的中心点连边（记一下距离），那么最小生成树上的边一定是这些边中选出来的，然后只要跑一个kruskal就好了
边数不会超过矩形大小
然后倍增什么的搞一搞就好了
-----------------------------------------------------------------------
P4243:
发现如果原图是一棵树的话，那么只要一个点有兄弟或者已经被染色，那么他和他兄弟和他的的所有儿子也会被成和他同样的颜色（这里染色是指，在最后的答案中，同属一个完全图，这玩意儿可以用并查集维护一下）
于是按照这个思路去跑DFS就好了
但是图中是没有“兄弟”这个概念的
因此观察上一层，也就是说至少有两个儿子的节点，他的儿子们会被染成同色（但他不一定会）
每次从一个还没有访问过的且要么已经染色，要么至少有两个儿子的节点出发
如果他已经染色，那么把他的所有儿子染成和他同一个颜色
如果他没有染色但是至少有两个儿子，那么把他的两个儿子染成同色
然后DFS下去，不重复走访问过的节点
但是这样有个问题，一个点可能刚开始没被染色，因此他没和他的儿子们染成同色，后来被染色了，那么他就应该和他的儿子们染成同色，但是已经访问过了（换句话说，由染过色的点更新和由至少两个儿子的点更新，在树上是差了一层的，因此可能有最多一层的错位<-这句话我也不知道我在说什么，但大概就是这个意思）解决方法就是每次一个节点被染色的时候，他就把他的儿子们和他染成同色
时间复杂度O((n+m)*α)，其中α来源于并查集
-----------------------------------------------------------------------
评论 (0)
