about 1 year ago

bzoj4513
题意:
给出n,m(<=10^18),求sigma max((i xor j)-k,0) (i<=n,j<=m)
题解:
转成2进制随意数位dp一波就好
(1wa对拍发现进制转错了。。

bzoj4514
题意:
有n(<=200)种数字,第i种数字是ai,有bi个,权值是ci。
若两个数字 ai、aj 满足,ai 是 aj 的倍数,且 ai/aj 是一个质数,
那么这两个数字可以配对,并获得 ci×cj 的价值。
一个数字只能参与一次配对,可以不参与配对。
在获得的价值总和不小于0的前提下,求最多进行多少次配对。
题解:
发现若ai/aj为一个质数,ak/aj为一个质数,ai和ak互不为因数。若ai/aj为一个质数,aj/ak为一个质数,ai/ak不为质数
所以就二分图了,随便费用流一波就好

bzoj4408
题意:
一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。
给n(n<=100000)个数序列,m(<=100000)个询问,问l到r区间的神秘数
题解:
不会做好囧啊。。其实这题挺好的
考虑给一个序列,如何算这个序列的神秘数
首先,设ans=1,然后将这个序列的数从小到大加入,当前加入x
若x<=ans,ans变为ans+x,否则ans就是神秘数,证明很显然
考虑这个过程,就是设一个ans,sum为小于等于ans的数的和,若ans<=sum则ans变为sum+1,否则ans就是神秘数
那我们可以弄棵主席树对每个询问模拟这个过程
最坏情况下,就是每次ans只增大lastans+1,对应序列是1,2,3,5,8..就是斐波那契序列,也就是最多加log次
所以复杂度为O(m logn logn

bzoj4515
题意:
一棵有n(<=100000)个点的树上。最初,每个点上都只有一个数字123456789123456789。
两种操作
1:一条从 s 到 t 的路径,在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r,若 r 与 s 的距离是 dis,在r上添加的数字是a×dis+b。
2:一条从 s 到 t 的路径。先从这条路径上选择一个点,再从那个点上选择一个数字。选择的数字越小越好。
对于每个2操作,输出选的数字
题解:
不会做好囧啊。。
某点上的最小值很容易可以想到弄成关于他到根距离的一次函数
然后怎么维护就膜题解辣
这是个叫线段树标记永久化的东西
假如当前区间有k1,b1,k2,b2两个一次函数,考虑怎样维护
若某一条在每处都比另一条优,另一条就可以扔了
否则,由于我们树剖了,所以处理的区间都是树上的一条直链,所以到根距离递增,也就是说一个函数最优是从左开始到某处,剩下的就是另一条最优,那选择覆盖了mid的那一条保留,另一条递归传下去
分析复杂度,考虑修改涉及logn个区间,每个区间要递归传标记,由于每次传的区间不过mid,所以要传logn次,再加上树剖,就是O(m logn logn logn)

bzoj1025
题意:
对于1到N(<=1000)这N个数字,都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1,2,3,……,N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为1,2,3,……,N。 现在windy想知道,对于所有可能的对应关系,有多少种可能的排数。
题解:
不会做好囧啊。。
很容易发现所谓排数就是环大小的lcm
然后怎么弄就膜题解辣
考虑某种方案第i个环大小为ci=p1^(a[i,1]) * p2^(a[i,2]) * .. * pm^(a[i,m]) sigma ci=n
那么lcm为p1^(max a[i,1]) * p2^(max a[i,2]) * pm^(max a[i,m])
那么很明显,lcm只与每个质数的最大次幂有关,那只用质数最大次幂,剩下环大小都是1,就可以达到相同的lcm
证明质数最大次幂的和一定小于等于n
若ci提供最大次幂x1..xm,由于xi>=2,sigma xi<=ci
然后就枚举p^k做个背包

bzoj4539
题意:
有棵n(<=100000)个点的模板树,1为根,每条边长度1。新树初始状态等于模板树。
m(<=100000)个操作,每次操作x,y。设现在新树cnt个节点,模板树x子树大小siz。在新树y节点下建一棵与x的子树一样的树,用cnt+1到cnt+siz给上面的点标号,使每个点编号的大小关系与模板树上一样。
建完后,q(<=100000)个询问x,y,问新树上x到y距离
题解:
看错题了囧,还以为是用新树上的子树建然后边建边询问,看题解觉得不对呀
可以将新建的每颗子树都缩成一个块,记录新树上的每个块到他父亲是从模板树哪个点进入的
记录每个块是那个点子树和节点编号范围,这样给一个编号,二分他在哪个块里,就知道他在块中编号第几大。对模板树dfs序搞棵主席树(可持久化线段树合并爆空间TAT,询问一个编号对应模板树上哪个点就去区间第k大
然后新树、模板树都做个lca,询问分类讨论就行了
那种树上加点的,如果每次加入都是叶节点,可以边加边做lca,不用dfs

感觉apio的题好妙啊,那就刷一波吧
[Apio2012]dispatching
题意:
一棵n(<=100000)个点的树,1为根,给出m。每个点有两个值ci和li。选一个点x,然后在他子树中选k个点,这k个点的c的和小于等于m。最大化lx * k
题解:
果断merge艹。。
(merge都打错了好悲桑

[Apio2012]Guard
题意:
有n(<=100000)个灌木丛,已知有k个后面躲着人。给出m个约束条件表示l到r有没有人。问哪些灌木丛能确定后面有人。
题解:
我想得太naive了。。
先把确定没人的删掉,然后区间离散化一下变成l到r一定有人。这时若刚好剩k个就全输出。
然后某个地方有人就只会有两种情况(1、某区间说x到x一定有人。(2、某位置如果不放人的话满足所以条件需要超过k个人
第一种情况特判
先删除覆盖别的区间的区间。第二种情况我们从选最少点覆盖所有线段的贪心可知最优点一定是左端点或右端点,现在就是要检验。设fi为1~i线段覆盖最少点,gi为i~tot线段覆盖最少点,可贪心预处理。检验x是否必须方法就是选x-1,然后x-1能覆盖l到r,看f[l-1]+g[r+1]+1是否小于等于k,x+1同样检验,还要检验x是否小于等于k。如果选x-1总数小于k的方案选了x也没关系,因为第二种情况中把该方案的x换为x+1一定合法。

[Apio2013]道路费用
题意:
一个n(<=100000)个点的图,每个点有点权。有m(<=300000)条带权无向边和额外k(<=20)条边,其中m条边权值互不相同。给额外边定权,然后做一棵最小生成树。每条被选上的额外边的收益是所定的边权 * 最小生成树子树的点权和(1为根)。问最大收益
题解:
看到k很小,我想到很多地方其实和额外边无关,然后缩点,然后枚举哪些额外边要选。然而枚举就要2^20,搞边权又要额外的时间,我想肯定会T就委了。。然后看了题解,就是缩完点后还剩k^2条边,先把枚举的额外边连上,然后用这些边去树上限制。这样不是k^3的吗?网上都写k^2不知道为什么。写了一发自测过了一交果然tle就弃疗了。。
(这题值得注意的是m条边权互不相同,所有最小生成树是唯一的

[Apio2013]机器人
题意:
一个n(<=500)m(<=500)的网格中有k(<=9)个机器人。有些格子是障碍,碰到会停。有些是转向器,机器人走进去会按规定转向,一个编号为[l,mid]的机器人若和一个编号为[mid+1,r]的机器人在同一格,则可合成[l,r]机器人。向上下左右某个方向推一个机器人他会一直走到被挡住。问合成[1,k]机器人最少推多少次
题解:
可以先递推出每个格子向四个方向最终会停在哪个格子
f[i][j][l][r]表示在(i,j)合成[l,r]最少次数
f[i][j][l][r]=min(f[x][y][l][r]+1) (x,y)向某方向推可到(i,j)
f[i][j][l][r]=min(f[i][j][l][mid]+f[i][j][mid+1][r]) 就是合成起来
这个方程是很明显的
然后像spfa那样转移。我看到状态数那么多就虚了,看了题解,他有个转移的方法。
第二部分就区间长度从小到大枚举然后暴力做,第一部分由于边权一样,考虑用bfs
如果是单源的,直接bfs就行了
现在是多元,就开两个队列,第一个队列里放所有排好序原点,更新的点放第二个队列。选人出来时从第一个队列队队首和第二个队列队首选一个较优的,这样就相当于模拟了dijskra每次找最小的那个点。

{APIO2015]Bali Sculptures
题意:
见dp
题解:
就是那个2合1题。。

[APIO2015]Jakarta Skyscrapers
题意:
有n(<=30000)个点排成一行,有m(<=30000)个人。每个人一开始都在bi点上。第i个人跳跃能力pi,意思是若他此时在x,一步能跳到x+pi或x-pi(在不出界的情况下)。现在1号人有一条消息要告诉2号人。知道消息的人可以选择告把消息告诉同一个点的另一个人或跳就是只有带着消息的人才能跳。问把消息告诉2号人总共最少跳多少步。
题解:
一看题我就想,如果pi大于sqrt(n)那他连出边数就小于sqrt(n)。。
然后就告诉自己先想想靠谱方法吧。。然后想不到。。然后看了一眼题解。。然后看到“如果pi大于sqrt(n)”。。
果然根号大法
那就可以这样做
pi大于sqrt(n)就直接连
pi小于sqrt(n)的话,由于每个人要向两边连,先考虑向后连的情况。
如果i>x>y,px=py,x已经向i连了一条边,那y向i的那一条边就不用连了,因为y到i的边等价于y到x的边+x到i边。向前连也类似。
所以对于小于sqrt(n)的pi,每个人只会被连入一条边,那总边数就是O(n sqrt(n))。

[APIO2015]Palembang Bridges
题意:
从前有一条河,两岸看成数轴。有n(<=100000)个人,第i人要从ai岸的xi到bi岸的yi。现可以垂直河岸修k(1或2)座桥。每个人都会沿最短路线走,问最少路程和。
题解:
从同岸到同岸的可以先拿出来。
如果k=1就是中位数。
如果k=2,就看如果修了两座桥,xi到yi这个人会走哪座桥。yy可得会走离(xi+yi)/2近的那座桥,那就按中点排个序搞搞。

[APIO2016]Boat
题意:
有n(<=500)个学校,第i个学校可以派出ai到bi条赛艇。学校可以不派出赛艇,如果要派,则派出的赛艇数要大于所有编号小于他的学校派出的赛艇数。总共至少1个赛艇,问有多少种方案
题解:
妙啊。。看了题解
首先离散化成2n个区间。注意规范左闭右开。
如果枚举每个人去哪个区间就不好弄,就像cf那题一样,要枚举每个区间有哪些人。
注意一个很巧妙的转移方法,在长度为l的区间选cnt人,因为限制状态不重复,强制最大那个人一定要选。方案数就是C(l+cnt-1,cnt),意思就是这l个数可以选,后面那cnt-1个就代表除了最大的人之外的cnt-1个人,这cnt-1个中第k个被选就代表第k大的那个人选空。
转移时限制状态不重复,除了限制最大必选,还要枚举不在这个区间上一个必选的人。这样就可以保证不重不漏。
方程就不写了,这题挺有意思的

刷apio发现自己还是有很多问题
(1、似乎pkusc之后码力大减。。k写成i之类的sb错误一大堆。。dijskra和merge都打错。。
(2、计数类dp还是弱项脑残怎么治?

bzoj4059
题意:
一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。(n<=200000)
题解:
记录上一次出现位置线段树搞搞

bzoj4027
题意:
有一棵n(<=2000000)点树,给出m。樱花树每个节点上都会有一些樱花,其中第i个节点有ci朵樱花。樱花树的每一个节点都有最大的载重m,对于每一个节点i,它的儿子节点的个数和i节点上樱花个数之和不能超过m。当一个节点被去掉之后,这个节点上的樱花和它的儿子节点都被连到删掉节点的父节点上。在不违背最大载重的情况下,最多能删除多少节点。注意根节点不能被删除
题解:
可以贪~~就是做出每个点子树最多删多少个和此时该点有多少孩子。
为什么是对的呢?就是说在上面一个点,下面一个点中只能选一个点来删,那一定是删下面那个比较优,因为他对答案贡献相同,而对上面负重的影响较小

bzoj2525
题意:
一棵N(<=300000)个节点的树,其中某些点上面已经安置了炸药,现在需要点燃M个点上的引线引爆所有的炸药。
某个点上的引线被点燃后的1单位时间内,在树上和它相邻的点的引线会被点燃。如果一个有炸药的点的引信被点燃,那么这个点上的炸药会爆炸。求引爆所有炸药的最短时间。
题解:
首先这个时间是可以二分的。然后就是类似于救火站和pkusc那题类似的想法。先考虑最深的那个有炸药的点,我们要选一个与他距离不超过lim的点。那选哪个点是最优的呢?没错就是他的第lim个父亲。因为不存在比他更深的点了,所以对于第lim个父亲子树里的点,这个点都能覆盖到他们。而对于外面的点,这个点无疑是最优的。于是贪就好了。。
一开始我打了个暴力染色,因为我想这样一条边最多被问两次哈哈哈然而以后可能有人可以染完以前染的点然后进他子树染更多的点。。
没事。。我们还有树形dp。。

bzoj4008
题意:
t(<=444)局游戏(就是多组数据)。每局游戏有n(<=220)张卡铺在桌上,给出pi,di。然后按如下规则进行r(<=132)轮
1如果这张卡牌在这一局游戏中已经发动过技能,则
1.1 如果这张卡牌不是最后一张,则跳过之(考虑下一张卡牌);
否则(是最后一张),结束这一轮
2否则(这张卡牌在这一局游戏中没有发动过技能),设这张卡牌为第 i 张
2.1将其以 pi的概率发动技能。
2.2如果技能发动,则对敌方造成 di点伤害,并结束这一轮。
2.3如果这张卡牌已经是最后一张(即 i 等于n),则结束这一轮;
否则考虑下一张卡牌。
题解:
popoqqq大神评价这题神思路啊我居然会做
考虑这个游戏到底是怎么玩的啊。。一轮最多发动一张牌是吧。。一张牌最多发动一次是吧。。我们可以想象成r轮一起进行。假设还剩m轮没发动。碰到一个人,第一轮就以pi概率发动,如果发动,那这一轮以后就不用考虑,同时剩下的m-1轮也直接去下一个人考虑。第二轮就以 第一轮不发动(1-pi) * 第二轮发动pi 概率发动是吧。。然后第i轮发动概率就是((1-p)^(i-1))p。然后(1-p)^m概率一轮都没有发动这张牌。发动的那个式子。。是个等比数列是吧。。直接算就好了。。那f[i][j]表示考虑到第i人,还剩j轮没有发动过一个人的概率,转移时顺便算算答案就行了。。一开始我算出f数组后直接sigma f[i][j] * p[i]。。这样为什么是错的呢?因为他发动概率不是pi而是那个等比数列压。。

bzoj3876
题意:
给一个dag,n(<=300)点m(<=5000)边,1号点可到所有点。每条边有边权。每次可以选一条以1号点为起点的路径,花费是这条路径的长度。问最小花费把所有边选一遍。
题解:
把除1号点外所有点连汇点,如果问总路径数最小,那就是有源有汇最小流了是吧。。然而这个最小费用流是个啥。。
不方我们直接套上下界最小流的做法用spfa增广同时算算费用是兹磁的。。然后就没有然后了。。

bzoj1560
题意:
直接看吧
题解:
心累不说

bzoj1194
题意:
给你s(<=50)个01自动机。每个自动机大小<=50。每个自动机有一个起始节点和若干输出节点。若一个01串走到了一个输出节点就能输出这个串。若自动机i能输出自动机j能输出的所有01串,那称i是j的升级。问最长升级序列。
题解:
做出所有自动机的包含关系缩点后就是个拓扑图,套拓扑排序的时候dp下就好了。关键是怎么检验i是否包含j。
膜了题解。。居然是bfs。。就是bfs数对(x,y)表示对于一个串i到x节点,j到y节点。若某时刻y是输出节点而x不是那就不包含,否则包含。好吧我脑残了。。数对(x,y)个数是n^2的。。搜就好了。。
这题关键在于不包含条件抽象为对于某个串,j到输出节点而i没到;已及我们不关心串是什么样的,因为这是个自!动!机!,只要知道到哪个节点就知道怎么转移了。。

bzoj1044
题意:
有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连
接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长
度最大的一段长度最小. 并将结果mod 10007
题解:
先二分再dp

bzoj4592
题意:
有个序列,n(<=200000)个数。一开始全是1。
要支持3种操作
1、l到r变成0
2、l1到r1所有1拿出来统计1的个数,拿完后l1到r1全0。从l2到r2一个个数看,如果是0,改成1,然后1的个数减一,如果1的个数为0就退出。最后多出来的1就不管了
3、询问l到r最长的连续0
题解:
这题脸上写着“我是线段树”。。2操作找覆盖位置要用线段树分治。。

bzoj1997
题意:
一个n(<=200)点,m(<=10000)边图,给一条哈密顿回路。判这是不是平面图。
题解:
姿势太少好悲桑。。
哈密顿回路就是个环,我们考虑把这个环展开到平面上。
可以发现,若两条边同时在环内连相交那同时在环外也会相交,所以一定一内一外。然后就%题解。。
嗯。。连边2-sat。。利用平面图边数小于等于3n-6减支。。
(记住啦平面图边数小于等于3n-6哦

bzoj1090
题意:
折叠的定义如下: 1. 一个字符串可以看成它自身的折叠。记作S  S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)  SSSS…S(X个S)。 3. 如果A  A’, BB’,则AB  A’B’ 例如,因为3(A) = AAA, 2(B) = BB,所以3(A)C2(B)  AAACBB,而2(3(A)C)2(B)AAACAAACBB 给一个字符串,求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为:9(A)3(AB)CCD。
给个字符串(len<=100),问最短折叠长度
题解:
用f[i][j]表示i到j这段最短折叠长度。两种转移方法
1、由[i,k]、[k+1,j]拼接
2、由某个前缀折叠
n^3可以预处理出g[i][j][k]表示i到j这一段能否由长度为k的前缀折叠而成

← poi练习记