联赛倒计时 [UPD 05.11.17]

发布于 2017-10-30  5.13k 次阅读


30.10.17

今天没有考试,从早上开始一直在刷OJ上的各种杂题,把DP的可做题搞掉后继续去搞达哥的最后一波题解。

bzoj2004 [Hnoi2010]Bus 公交线路

p的范围很小,提示我们可以考虑状压。n的范围很大,提示我们可以矩阵优化。

因为每个公交车都是一样的,所以我们可以直接压成二进制上的1,表示到当前位置距离为i的点上是否有公交车,可以预处理合法状态,然后枚举从哪一位转移到当前位置即可。

 

bzoj3307 雨天的尾巴

之前考试题的弱化版,对每个节点开个线段树,动态开点,DFS返回时合并线段树,完事之后查询一下就好了。

关于线段树的合并,假设有n次新建节点操作,我们需要把所有的新建操作合并,那么每次操作会新建O(logn)的节点。如果合并两棵树a、b,那么合并后的树c上,新建的节点数为两个节点共用的节点数,也就是sa+sb-sc个,那么最多只有新建节点数那么多,所以,在多次合并后,也可以保证总时间复杂度O(nlogn)。

对于这道题,由于根本不需要“新建”或者“删除”节点,只需要修改原有信息即可,所以非常好过。

 

bzoj2794[Poi2012]Cloakroom 

第一眼看还以为是个什么神奇的数据结构题,通过a[i]<=m和q的范围这两个条件可以猜到应该是排序+离线处理。看了题解知道是背包,继续想,只需要不断维护是否可达每个状态即可。由于没看完数据范围以为n*k是1e9,果断怂,后来发现n*k只有1e8,显然可过,所以我们只要设f[i]:达到c之和为i的最小b值的最大值。听起来很绕口,但是实际上就是找一个物品组,使得最小元素最大即可。实际上就是01背包,非常简单。

 

bzoj4602[SDOI2016]齿轮 

要求判断是否可行,看起来貌似没啥好办法,但是其实正解就是对于每对限制关系暴力判断是否能满足,DFS一遍,判断矛盾即可,不贴代码了。

 

bzoj3124[SDOI2013]直径 

第一问非常水,只要两次DFS即可求出树的直径,同时记录下直径上所有的点,直径上的点到达右端点的长度。

考虑第二问求所有直径的交集大小。画画图可以发现,交集必须是连续的一段(如果不是连续的,那么一定可以通过把中断的部分换成直径上的部分来增长另一条直径)。所以,找到一条直径后,可以找到左右端点,之间的部分全部符合要求。一点一点往中间缩,如果一个点不经过直径的最长链长度等于从这个点到直径端点的长度,那么这个点左边(或右边)的点显然不符合要求。代码写的很乱,不贴了。

 


31.10.17

上午考试第二题没看到后来下发的题目修正,结果根本没理解题意,连爆搜都不会写。。。

不过幸好第一题和第三题都A了,所以还不算太差。

31.10.17

T1 trans

一看见这样类型的模拟马上虚一波(虽然很不应该),先打了暴力,又周折了一番,才发现靠谱的做法,码了一半先看了一眼第二题,发现不理解,回来老老实实把正解码完拍上,才敢继续往后做。

其实只要考虑位置下标的奇偶性即可,只有少数情况会循环,所以线性扫一下就好了。

 

T2 snakevsblock

既然题意都没理解,考试的时候没得到分也是没啥可说的了,不过这道题的思路真的很好。

首先,明确题意,就是从第一行中间出发,到达一行后可以按照任意顺序走,只要生命值非负就可以继续。那么,看看数据范围,状态转移方程也就出来了。f[i][j][k]:前i行,走完第i行后还剩j生命值,从k离开第i行的最优解。维护g[i][j][k]:在当前行[j,k]之间任意移动,移动完还剩i点生命值的最优解。因为在同一行的移动次序和方向对答案有影响,而且与当前生命值也有关系,所以我们可以考虑使用区间DP来维护g。先用上一行离开的位置更新当前行长度为1的所有方案,接着用区间DP的惯用套路,先枚举区间长度,接着枚举左右端点,最后枚举生命值转移即可。只有a值为负的才能对当前答案产生影响,所以加上的是max(-a[i][j],0)。最后,既然我们知道在这个区间里任意移动的最优解,那么从区间里任意移动完成后每一个位置都是合法的转移点,直接更新所有对应的f值即可。

这道题非常综合,转移的细节也算比较多。

 

T3 ping

上周考过,之前就想出了正解,但是无奈树剖的边界打挂了,白白扔掉了60分,所以这次20分钟打完调完,之后认认真真静态查错一波,稳稳AC。

每条链“最晚”必须在其端点的LCA处得到覆盖。如果一条链在LCA的子树内部没有得到覆盖,那么在LCA处覆盖它一定是最优的。如果有“子树外”的链连进来,那么覆盖点的位置取在当前点一定比取在子树里更优,也就是说可以保证LCA深度更浅的链也能因为这个选择而保证最优。

说的很绕,但是理解起来好像没有太困难。第一次做也是很快想到这个做法的。

 

今天下午看了看虚树,一脸懵逼,虽然大致思路理解了,但是代码实现起来还是有困难。

达哥的杂题实在是切不动。。。默默去填坑,看了看01分数规划,发现理解了一些,但是还是不想打。。。

之后去看了看数位DP,做了道入门题(BZOJ1026),但是还是看了题解,最后发现没怎么掌握套路,只能针对这道题搞出做法。个人比较喜欢记忆化搜索,虽然代码好像是长一些,但是细节和边界的处理貌似要容易一些,明天再做一道吧。

最后来了个HDU4035,树形DP+期望,发现转移出环了,写了个式子,和题解对了对,之后就不会了。。。然而数据范围1e4,并不能高斯消元,于是彻底怂了。发现正解就是用树形DP从下往上算“同类项”的系数,而这些系数都与根节点的期望有关,所以到了根就可以手动解出方程。。。感觉思路好神(但是并没有码完),又不想弃坑,明天早上应该能继续写完。

 

1.11.17~3.11.17

前两天节奏比较紧张,每天考两次,所以并没有什么时间来写博客,就一起把这几天刷到的有意思的题写一写吧。

bzoj1016 [JSOI2008]最小生成树计数

对于一张图的多个最小生成树,他们的相同权值的边数一定相同。如果有多条相同权值的边,那么由这些边的得到的连通块连通情况一定相同。否则,不满足”最小生成树“。因此,我们可以先跑出来一个最小生成树,那么其他生成树的相同边权的边数一定和这棵树一致。在相同圈住边数较少的情况下,可以状压枚举选择情况,之后乘法原理计数即可。

 

bzoj3626 [LNOI2014]LCA

转换设问,对于一段区间查询可以差分成两个区间。接着,查询x、y的lca深度时,可以将x到根的路径上点权+1,之后查询y到根的点权和即为lca深度。这样,我们可以将询问离线,从1~n枚举每个节点,对于每个节点,将其到根路径上点权+1,查询时只要查询点到根路径上的权值之和即可。

 

这两天考了两套非常毒瘤的题,感觉思维含量非常高,但是代码实现都非常简单。

 

[ttl2v]

021117-A 021117-B

[/ttl2v]

set

在n个数中随便找一个非空子集,使得选中的和能被n整除。首先转换设问,等价于在模意义下同余于0,那么50分的DP就非常显然了。无奈出题人又卡内存,所以我的优化手段到此为止。考完才知道可以用链表搞掉空间限制,多骗10分。正解思路非常神奇,考虑到前缀和s[0].....s[n]在模意义下最多只有n种取值,但是却有m个数,也就是说必然存在两个数相同。那么,在模意义下相同,意味着中间的元素之和一定同余于0,直接输出中间所有元素即可。

 

read

给出5e7个数,要求在满足相邻的两个元素不相同的情况下,这些数最少浪费掉多少。

坑爹的是内存限制16MB。想到一个比较靠谱的做法,非常接近正解,但是想不到节省空间的方法,无奈打了k<=20的部分分,就是开个桶排个序扫一下,后来发现好像能骗至少50,但是怕炸数组于是对于其他部分开了map离散。最后MLE,只有25。。。直接删掉map亲测有58。其实浪费掉的一定是出现次数最多的元素,扫一遍进行一些”抵消“操作,可以得到剩下的元素个数,之后再扫一遍(时间复杂度刚好1e8),统计一下这个元素(其实就是出现次数最多的元素)出现了多少次,那么再用剩下的元素全部抵消这个即可。

 

tree

树形概率,发现转移出环,先转化到了从一个点到根的简单情况,大力手解方程,发现最后答案一定是整数。。。但是这种思路并不正确。正解应该是分别考虑每条边对期望次数的贡献,算出u->fa[u]和fa[u]->u的期望次数,也是通过式子推导,发现答案是整数,然后树规搞一搞,算出上面两个值,倍增LCA统计即可。最近一做这种类型的题就总是掉进套路里,不是光想树上差分就是直接定义状态,果然还是too young.

 

剩下三道不是非常想写了,具体看题解吧。

[ttl2v]

sol-021117A sol-021117B

[/ttl2v]

只剩一周了啊,一定不能松懈!

 


4.11.17

昨天考试题前两题一个半小时水掉了,受前一天做的"最小生成树计数"影响,第三题一直从集合的角度想,结果一直到考试结束都没有想出来。

4.11.17

weight

给一张带权无向图,在其他边权不变的情况下,求每条边出现在最小生成树的边权上限。

从最小生成树的实际意义考虑,先跑出来一个最小生成树,那么我们可以分两种情况来处理答案:

A:对于非树边,其作用是连接起树边的一些端点,出现在最小生成树的条件是其边权小于两端点构成的链上的最大边权(直接删去大于它的边,并加上这条边)。

B:对于树边,可能有非树边连接起其连接到的两个集合。画个图,可以知道一条非树边可以对其两端点到LCA的路径上的所有边起到限制作用(路径上任意一边权值大于改变,就可以直接换掉),因此我们需要维护线段树,不断进行“区间取min”操作,最后一遍DFS求出所有点的真正权值即可。

这道题思路非常好,但是出题人的数据却出了锅,据说后面的数据给出的图根本不连通。。。垃圾出题人回我青春。。。

 

 


5.11.17

今天考了两次,上午因为没看出来第三题是原题(3/4人都A了...)所以有点翻车,下午考的还算勉强。

5.11.17-A   5.11.17-B

sol-5.11.17-A   sol-5.11.17-B

 

attack

题目描述不全,问题其实是给定一个DAG,且保证1号点能到达其他所有点,给定一些点集,求1号点到这些点的必经点的交集大小。

通过部分分可以发现,在DAG退化成树的情况下,必经点是所有点的公共祖先。也就是说,我们只需求出所有点的LCA深度即可。对于一般情况,必经关系仍然是一棵树。我们考虑按照拓扑序加入所有的点,维护所有必经关系,首先,我们保证已经加入树中的点的必经关系已经处理完毕,那么我们只需要在考虑加入新点时,将该点的父亲设为所有入边终点为当前点的起点的LCA即可。因为上述点集的必经关系已经确定,那么所有依赖关系也已经处理完毕。

 

tree

前两天的原题,今天换用另一种做法。考虑直接维护答案,详细看题解,唯一需要注意的地方是“计算从当前点的父亲到当前点的兄弟或是父亲的父亲里乱逛等价于以在以当前点为根的子树中乱跑”,这句话不太好描述也不太好理解,但却是简化问题所必要的。

 

入阵曲

考试的时候先写了75分暴力之后把它弃了,但后来做T3前又回来搞了搞就出解了。考虑我们O(n^4)的暴力需要的那个前缀和差分的式子,只跟四个角有关,可以写成a+d-b-c=0,移项d-c=b-a。即在区间左右端点固定的情况下,我们从上到下扫每一行,只需在桶里查上面几行满足这样要求的项数即可,同时维护这个桶,即可O(n^3)解决这个问题。

 

星空

标题比较有趣,跟她QQ昵称一样。。。(喂喂喂我在想什么)

首先要用到“异或差分”,也就是搞个差分数组,保存原序列中相邻两项的异或值。这样,原序列中区间异或等价于在新序列中给两个端点异或。这样,需要操作的序列变为了有不超过2k个1(必为偶数个)的一个差分序列(下标0~n)。我们的目标是消掉所有的1,而观察一下区间取反后差分序列的变化。可以把0看作没有物品的位置,1看作有物品的位置,这样,画画图可以看出,问题转化为我们可以将1移动到某些位置,且有一定代价,当两个1相遇时消失,求消掉所有1的最小代价。这样,状压搞一搞即可。注意,由于每个点都会被删,所以可以减少一维,降低复杂度。

 


6.11.17

今天白天没考试,晚上再考,所以打算填填坑。上午先去搞了道点双缩点的题,之后去复习了KMP,又复习了会儿hash。

bzoj3331 [BeiJing2013]压力

跟昨天考的"attack"问法比较相似,不过这道题给的是无向图,而且每次询问一个点对,要求最后输出“一定经过该点的路径数”,这就需要用点双了。为什么?如果起点终点在同一个点双内,那么除了起点终点,其余没有必须经过的点。而如果不在同一个点双内,那么一定会经过一些割点,而这些割点就是必须经过的点。那么,我们就要考虑把原图“缩点”成一棵树,之后才能使用利用树的唯一路径性质,用倍增或者树剖来搞。

具体做法:先用Tarjan求出点双,注意,加入栈中的一定是边而不是点,在找到割点时不断弹栈即可。之后,将同属于同一个点双的且非割点的点缩起来,可以标号为当前点双的标号。而对于割点,属于多个点双,如果发现当前割点并未标号,则标号后和所在点双连边,否则直接连边。之后,树上差分算答案。注意,如果起点终点就是割点的话,不要重复计算答案。另外,数组应开的大一些(我开了2倍),因为每个割点都会额外占用空间。

 

bzoj4446 [Scoi2015]小凸玩密室

非常神的树形DP,而且因为是在二叉树上所以根本不用DFS。直接定义从哪里转移显然会挂掉,所以需要考虑减少状态数。因为只有遍历完一颗子树才能到兄弟节点,所以状态数非常少。考虑一下合法的转移方式:自己的子树->父亲->父亲的其他子树->父亲的父亲.......因此,对于每个点,只要计算出到某个祖先以及某个祖先的另一儿子的最优解,就能得到最终的结果。维护f[i][j]:在i的子树内跑完后跑到了深度为j的祖先的另一儿子的最优解(好绕口),g[i][j]:在i的子树内跑完后跑到了深度为j的祖先的最优解。其中取0时表示不限制停住的位置。那么,可以通过分三种情况讨论维护这两个数组。最后做完DP,枚举每个点作为起点,模拟往上爬的过程,取最优解即可。

 

既然复习了KMP,就继续写写。首先求next数组的过程其实就是自己匹配自己,递推出前后最长相同的长度,只是边界不太好搞。对于这个next数组,还有个非常好的应用就是找最小循环节还有循环周期之类的玩意。直接上结论:当i%(i-nxt[i])==0&&nxt[i]!=0时,出现了长度为i-nxt[i]的循环节。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974