bzoj刷题计划A

Contents

我已经做了50/50

UPD:2017/7/22已完结。

[bzoj1007][HNOI2008]水平可见直线

对于给定的直线维护一个开口朝上的下凸壳即可,经典的convex hull trick用法,把斜率从小到大排序,维护一个单调栈,交点在右侧则栈顶一定不可能出现在凸壳上,注意斜率相等的情况。


[bzoj1211][HNOI2004]树的计数

树的prufer序列的一个特征是,每个点出现次数+1=在原树中的度数,证明yy下(其实我不会)

sum=\sum d[i]-1,那么答案就是

C_{sum}^{d[1]-1}\times C_{sum-(d[1]-1)}^{d[2]-1}\times....\times

不难发现每项都可以消去,于是通过质因数分解来避免高精度即可。


[bzoj1016][JSOI2008]最小生成树计数

考虑几个有用的observation:(证明参考https://blog.sengxian.com/solutions/bzoj-1016

1.两个最小生成树的权值的出现次数一定一样

2.不断加边的过程中两棵树的连通性相同

3.同等权值的边只要不是环就可以一起加进来

于是先随意构造一棵MST,记录每个权值应该有的次数,对于每个权值跑一次DFS判断可行方案数,乘法原理叠在一起即可。


[bzoj1017][JSOI2008]魔兽地图DOTR

比较神的一道题,我的思路是这样的,设f[i][j]表示第i个点为根的子树内,花了j个金币的最大力量值,显然这个不能让我们进行有效的转移,或者说太慢了。而导致这种惨况的就是,我们没有记录下他和父亲的欠债关系,于是设f[i][j][k]表示第i个点,买j个用来贡献给父亲,花了k元钱的最大力量,这样就可以进行dp了。

对于非叶子节点,我们要枚举他的每一个儿子,然后更新dp数组,但是这样有个问题,会重复的使用值,我们记一下就行了。时间复杂度我感觉上是过不去,但这瘠薄题似乎没有什么好的方法。。

最坑的就是,mmp题目说的是只可能是合并路线是树,也就是说,可能只有若干个低级装备,这个时候跑一个多重背包就行了,小爷我调了半天。。1


[bzoj2657][zjoi2012]旅游

简单题,就是题目不好读= =

这种三角剖分的典型做法已经烂大街了吧,利用重叠边构造一棵树,那么这题让你求一个经过点最多的,也就是一条直径咯,两次bfs下就没了


[bzoj1018][SHOI2008]堵塞的交通

终于A了ovo(然而我是用cogs的数据来不断地验证的gg..)

这题我们把路径分为两种情况,一种是在两个列之间,一种是在两个列之外

两个列之间的话直接维护线段树即可,怎么维护?画个图吧,记录下每个点向右向下是否有边

分四种情况,每种情况再分两种进行讨论合并即可

在列外怎么办?走到能达到的最远的地方,这样就把问题又变成了在列内

怎么找最远的地方?二分即可,可以在线段树上走来优化

时间复杂度O(n\log^{2}n)

调试总结:一开始我认为是走到最近的即可,这实际上是没什么卵用的,与我一开始的思路相悖。二者就是写代码一定要知道每一行在干什么,所以我现在坚持写注释。第三个问题就是,要知道每一个部分是否会有漏洞,是否会偷换题意?


[bzoj1019][SHOI2008]汉诺塔

orz蒟蒻不会这样的递推转移姿势。。

首先通过题目给出的两个约束条件我们能够得到的性质是:局面发展方向唯一,不会出现环的情况。

这给我们的一个提示是,递推。

那么如何递推?我们需要刻画出一种能够涵盖计数的递推状态。

f[i][j]表示把第i根柱子上的前j个盘子全都堆到第p[i][j]根柱子上去。

另外一个观察就是,一定的存在某一时刻,某根柱子上只有一个最大的盘子,另外一根柱子上有n-1根。

那么考虑p[i][j-1],如果p[i][j-1]=a的话,也就是意味着a上有j-1个盘子,i上有一个盘子,剩下的那根柱子上没有盘子。

如果p[a][j-1]是移动到剩下的那根柱子上,显然就是把大的先移过去(代价为1),然后把a上的移过去,于是代价为f[i][j-1]+1+f[a][j-1]

如果p[a][j-1]是移动到i上去,我们是没有办法推出从i移到剩下的那根柱子上去的,所以应该是先把大的移到剩下的那根柱子上去,把a上的移到i上去,把大的移到a上去,再把i上的移到a上去,故代价为f[i][j-1]+1+f[a][j-1]+1+f[i][j-1]

到此这道题得到了解决。

比较巧妙的思路在于,这题构造了另一个dp数组来辅助转移。


[bzoj4059][cerc2012]nonboring sequences

考虑第i个数值能够独立存在的区间的左端点应该在[last_{i}+1,i]中,右端点应在[i,next_{i}-1]中,其中last,next表示它上一次、下一次出现的位置。如果是第一次出现置为0,最后一次出现置为n+1

这样的话,我们把这东西放在二维平面上,横坐标表示L,纵坐标表示R,那么n个矩形的并就是有至少一个数是独立存在的若干个序列。

很容易发现,合法询问区间应该是在(i,i)以上的部分,于是我们考虑把每个矩形拆成两条时间线

剩下的就是扫描线+线段树即可,线段树记录区间最小值(我沙雕了第一次记的是非空数,然而实际上有bug)

时间复杂度O(n\log n),用inline卡常卡过去了4


[bzoj1071][SCOI2008]组队

式子可以变成A\times h+B\times S\leq A\times minh+B\times mins+C,于是按照左边升序,枚举minh,再枚举minv,对两个队列分别扫扫就行了。


[bzoj1218][HNOI2003]激光导弹

把每个点看成矩阵的右上角,拆成两个,扫描线扫一下,线段树支持区间修改,整体最大值即可。

神特么要先把同一列的全部处理再计算,不然会GG


[bzoj4561][JLOI2016]圆的异或并

每个圆看成两个事件,扫描线即可,每个事件要拆成上半圆和下半圆,对于当前半圆,找到他的前驱,没有就看做1。如果有的话,看是上半圆还是下半圆,上半圆证明被包含,下半圆证明被包含关系一样。set维护即可,距离用勾股定理算下。


[bzoj1029][JSOI2007]建筑抢修

可修改贪心直接淦


[bzoj4896][summercamp]补退选

thu出这种题也是吃枣药丸,神TM傻逼题,然后各种坑点系列。


[bzoj1040][ZJOI2008]骑士

基环树上的最大点权独立集问题,考虑把环拆树跑dp即可


[bzoj1227][SDOI2009]虔诚的墓主人

大力扫描线,贡献推成C(left,k)\times C(right,k)\times\sum C(up,k)\times C(down,k),求和部分树状数组维护即可,组合数由于k很小,直接递推出来。


[bzoj2458][Beijing2011]最小三角形

有毒= =怎么改归并都过不去我是不是傻逼他妈给傻逼开门-----------傻逼到家了。。

和平面最近点对一样的做法搞就行了。。不知道时间复杂度怎么证明= =


[bzoj1021][SHOI2008]循环的债务

这道题思路挺不错的,考虑到每种面值相互独立,以及每种面值一定是直接传而不是分开传,所以可以设dp[i][j][k]表示面值为\leq i的钞票,小A有j元,小B有k元时的最小钞票数,分六种情况转移即可。


[bzoj1500][NOI2005]维修数列

splay模板题,我放下我(hzw)的板子


[bzoj1588][HNOI2002]营业额统计

splay裸题,在树上二分即可。


[bzoj2209/2329][HNOI2011]括号序列

一个结论是,对于已经被匹配的括号,我们不用去动他们。闭上眼感受下就知道是对的。

于是去除这些括号后,剩下的一定是))))(((这样的。

显然记x表示右括号的个数,y表示左括号的个数

那么答案就是\left \lceil \frac{x}{2} \right \rceil+\left \lceil \frac{y}{2} \right \rceil

怎么统计?把左括号看成-1,右括号看成+1,那么就变成了从左边开始的最大连续子段和,从右边开始的最小连续子段和。

由于需要支持区间翻转和反转,需要用一棵splay树维护。

注意下标的顺序问题,如果INVERT和REPLACE都存在的话,先执行INVERT,看下有没有被REPLACE打过标记,有的话反转标记,不然就把标记下传。REVERSE不用管的随便放哪都行。


[bzoj3786]星系探索

用Splay维护ETT即可。由于序列会变,把原本的提[l-1,r+1]改成提l,r的前驱和后继。


[bzoj2303][apio2011]方格染色

考虑原题的条件满足a[i][j]\;xor\;a[i-1][j]\;xor\;a[i][j-1]\;xor\;a[i-1][j-1]\;=\;1

i=2,j=2开始进行猜测,显然该式子左边=1

然后如果扩展到i=2,j=3,我们发现中间的多出来的一列会根据xor的性质消掉

于是实际上是1在不断地异或他自己

于是如果i,j同为偶数,则a[1][1]\;xor\;a[x][1]\;xor\;a[1][y]\;xor\;a[i][j]\;=\;1

反之为0

也就是说,对于第一行、第一列,如果能全部确定下来,那整个方格就确定

我们考虑对第一行、第一列的每个点拆成两个点,根据障碍点把a[x][1],a[1][y]根据异或结果合并起来

左上角如果在障碍点中,就不用枚举,反之需要枚举的话就把两个加起来即可。


[bzoj2006][NOI2010]超级钢琴

区间裂解,用大根堆维护一个五元组(右端点,左端点区间,左端点,价值)即可。

查询最小值用ST表,注意ST表要从0开始,因为他可以全取。


[bzoj2208][JSOI2010]连通数

bitset优化传递闭包即可。时间复杂度O(n^{3}/64)


[bzoj1483][HNOI2009]梦幻布丁

考虑修改影响的是整体,不妨把同种颜色连续的布丁缩成一个块,然后分入属于他的颜色的组里。

那么每次修改等价于合并两个颜色组,考虑启发式合并,但是要注意,这里可能会把大的合并到小的那里,所以我们要交换两个颜色所代表的实际颜色。


[bzoj1057][ZJOI2009]矩阵游戏

显然只要存在n个棋子满足两两不同行、不同列即有解,把棋子看成交点看是否有完备匹配即可。


[bzoj1143][CTSC2008]祭祀

DAG最大独立集,根据dilworth定理,偏序集最长反链就是最小覆盖数

所以拆点,然后这题就是求最小可相交路径覆盖,我用了bitset优化Floyd然而还是没卡进第一页= =


[bzoj4396][NOIP2015]运输计划

二分+倍增+树上差分即可。我去年买了个表当年我是怎么傻逼的爆0的= =


[bzoj4719][NOIP2016]天天爱跑步

树上两点之间的路径肯定可以看成两段s->lca,lca->t

那么第一段若某点符合条件则需要满足dep[s]-dep[i]=w[i],移项得dep[i]+w[i]=dep[s]

于是记s[x]表示depx的起始点的数量

有个问题就是,这可能会多统计一些不在链上的。我们考虑,一个点能被经过,那起始点一定在他的子树内(这是很显然的),那么如果出了这个点,清空下,记录下前后差值肯定就是这个点的贡献。

另一段同理。


[bzoj1096][ZJOI2007]仓库建设

半平面交裸题,推下公式就可以看成线段然后直接上了。


[bzoj4449][NEERC15]Distance on trangulation

先拓扑排序找出所有三角形,这个平面图的对偶图是一个树,考虑距离会过重心所以把答案分治处理,点分这棵树即可。


[bzoj2120]数颜色

树套树,外层线段树,内层套treap,每次在treap上走一波就行了,调了好久QAQ,确定前后第一个用set来做,考虑到当前这个点只会影响到下一个所以不难证明这是对的。


[bzoj1178][APIO2009]convention

第一问直接大力贪心,第二问考虑只保留没有包含情况的区间关系,有的话取最小的显然合法,用单调栈做。然后考虑记f(x,i)表示从x开始,走2^{i}个区间最近到哪。然后某个区间能放进去的条件是getans(l,r)=getans(l,l_{0}-1)+1+getans(r_{0}+1,r),用set维护即可。


[bzoj3447][USACO14OP]Airplane boarding

考虑每头牛的限制,用数对表示,于是问题转化为查询有序序列前缀最大值,支持插入新数对。我们发现有可能并不单调,但很容易知道如果后面的数对的长度不超过前面的数对,那么这个后面的数对没什么卵用,所以splay维护下区间最小值、最大值,这样就可以做到快速查询删除插入了。


[bzoj1030][JSOI2007]文本生成器

Trie图上dp即可,利用补集转换思想。


[bzoj1031][JSOI2007]字符加密

考虑是环,拉两倍,那么原问题等价于对后缀排序,建立后缀数组即可。


[bzoj1037][ZJOI2008]生日聚会

动态规划,设f[i][j][x][y]表示前i个人,有j个男的,以i结尾的任意长度序列,男生比女生最多多x个,女生比男生最多多y个的方案数。


[bzoj1056][HAOI2008]排名系统

大力splay即可。


[bzoj1058][ZJOI2008]报表统计

大力STL即可,很容易发现每次插入对min_gap的影响只会是这个位置的最后一个和下个位置的第一个数的数值,这个我们把答案用两颗平衡树维护,一棵做MINGAP一棵做MIN_SORT_GAP即可。


[bzoj1025][SCOI2009]游戏

把映射看成有向边,那么每个环的大小的LCM显然就是该置换所需的次数。问题转化为求若干个正整数,和为n,有多少种lcm。直接DP就行。


[bzoj1027][JSOI2007]合金

第三维去掉,等价于平面上找一最小黑点集合的凸包能覆盖住白点集合的凸包。floyd即可。


[bzoj1060][ZJOI2007]时态同步

树DP即可。


 

发表评论