over 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的前缀折叠而成

 
over 1 year ago

感觉大爷们都做过poi压,那我就做做看吧

poi2007

旅游景点atr
题意:
从前有n(<=20000)个城市,m(<=200000)条边,经过每条边要一定时间。有个人想去编号1..k+1(<=20)城市。有很多对要求表示去过i城市后经过j城市算j去过(i,j<=k+1),在去过i城市前去了j城市只算经过,不算去过。问去完1..k+1最后到达n最短时间
题解:
k次spfa少不了辣~~ 又因为奇奇怪怪的限制条件,就写个状压f[s][i]表示去过城市为s,当前在i最小时间
听说这题常数感人,为什么我没感觉?

办公楼biu
题意:
有n(<=100000)个人,m(<=2000000)对人有关系。没关系的人必须在一栋楼里,问最多能把他们分到几栋楼里
题解:
实在膜得不行
首先一个naive想法就是把补图建出来看有几个联通块。
考虑从前往后处理每个未被并入别人联通块的人,bfs看那些人要和他在一个联通块中。
先将与他相连的人标记出来,访问一遍当前所有有用的人,将没被标记的人删除并加入队列,这样就能得到他所在联通块所有的人了
分析一下复杂度。当访问到一个人时,若他没被标记就会把他加入队列,以后去打个标记,每个人只会这样做一次,复杂度O(n+m)。若他被标记,就产生一次无用遍历,一个标记最多产生一次无用遍历,这部分是O(m)的,所以总复杂度O(n+m)。
现在我们需要一种数据结构能遍历每个当前有用的人,每个人的遍历O(1),支持删除。没错就是链表了(做这题前的ljm表示链表是什么可以吃吗

对称轴osi
题意:
n(3<=n<=100000),表示了多边形的点数。然后在后面n行每行两个整数x和y(-100000000<=x, y<=100000000),依次表示多边形的顶点坐标。多边形不一定是凸的,但是不自交——任何两条边都只有最多一个公共点——他们的公共端点。此外,没有两条连续的边平行。问多边形有多少条对称轴。
题解:
实在神得不行
以前做manacher的时候做的这题。考虑对称轴过的点一定是多边形顶点或边中点,先把中点加入。
从对称轴过的点开始向左右看,yy下发现边是对称的,就用点积叉积判相等做manacher。

Zap
题意:
(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个正整数,分别为a,b,d。(1<=d<=a,b<=50000)。询问有多少对i,j满足i<=a,j<=b,gcd(i,j)=d
题解:
积性函数经典题。。

山峰和山谷Grz
题意:
一个nn的地图,每个点有高度。与一个点相邻的点是周围8个点。我们定义一个格子的集合S为山峰(山谷)当
且仅当:1.S的所有格子都有相同的高度。2.S的所有格子都联通3.对于s属于S,与s相邻的s’不属于S。都有ws >
ws’(山峰),或者ws < ws’(山谷)。问有多少山峰山谷
题解:
水题

大都市meg
题意:
给一颗树,边权为1。m个操作,将一条边权值改为0或询问一个点到根路径和
题解:
dfs序,树状数组,水题

洪水pow
题意:
有一个nm(n,m<=1000)的地图,每个点有海拔。现在下雨了,每个点积水inf,水会按物理原则向上下左右流。现在要抽干k个指定点的水。在一个点放水泵,就会一直抽到没水。问最少多少水泵
题解:
考虑一个点什么时候不用水泵也能抽干水。就是只沿低于或等于他的格子走,能走到一个水泵。
就把关键点按高度从小到大排序。每次bfs按上面规则走,若能走到一个之前的关键点走过的点,就代表他能走到一个水泵。因为此时他的高度不小于所有走过的点,然后贪心即可。

石头花园SKA
题意:
第一向限有n(<=100000)个石头,给出他们坐标和重量。现在可以将一个石头从(x,y)搬到(y,x)代价是他的重量。找一种方案,使包括所以石头的矩形(长宽和x,y轴平行)周长最小,周长相等时代价最小
题解:
我yy了一下觉得好像同时翻到x=y上方或下方一定最优,做了就wa了。看别人题解,周长是这样的,但代价还有两种奇奇怪怪的情况看不懂,去问他们都忘了TAT看来要成为世界未解之谜了

立方体大作战tet
题意:
有n(n<=50000)对东西叠在一起,一对东西相邻时可消除,消除后就上面掉下来。可以交换相邻两个东西。问全部消除最少操作数。保证答案小于1000000
题解:
若两对物品是1 .... 2 ..... 2 .... 1一定是先消2更优 若是1.... 2 .... 1 ... 2 先消1消2都一样
因为保证答案小于1000000,开个栈模拟就好
如果泥想写splay当然也是资磁的~~

驾驶考试egz
题意:
有n(<=100000)条从南到北的路,每条路长度m(<=100000),有k(<=100000)条从东西或西东的路,第i条路在hi位置连接di和di+1。就是一个这样的图
现在能在任意位置添加p条东西或西东的路。以每条南北路位置0为起点,位置m为终点。只能按路的方向走,最多比加边前多多少起点能到达每个终点。
题解:
两个结论很明显。1、要到达所有终点等价于能到达最左和最右(即1、n)。2、若i能到1,则此时2..i-1都能到1。到n也类似
推出结论:能到达最左右的点是连续的。因为若i< j,i和j能到左右。对于i< k < j,i能到右,k则能到右,j能到左,k则能到左
那如果我们做出l[i],r[i]表示i到左右最少要添多少条边(明显l递增,r递减),枚举i,单调找一个j < i,使l[i]+r[j]<=p更新答案就行了
现在来看如果作出l和r
下面是ljm的辣鸡做法(做l的情况)
考虑一个dp。f[i][j]表示第i条路,j高度到达最左至少要加多少条边
对于i在高度j有到i-1的边,f[i][j]=f[i-1][j]
对于没有的j,f[i][j]=f[i-1][j]+1
然后当j>k,f[i][j]可以更新f[i][k]。因为k可以先走上去
那我们可以先把每个数都加1,再把不用加1的人减1。只有减1的人会破坏单调增,所以把他扔给下面所以人取个min
于是这个东西可以用claris老司机教的神到不行的维护上下界的线段树搞。
加减打标记,取min不打,直接对这个区间改上界。然后每走到一个节点,有标记直接改上下界,传掉他的标记和他孩子的标记后,用他的上下界限制孩子上下界,回溯时用孩子上下界更新他的上下界
(在线段树大功告成AC后,ljm突然发现——这东西弄个最长 * * 子序列就好了吧??!

天然气管道Gaz
题意:
给出天然气井和中转站坐标。现在需要将中转站和天然气井连接起来。每个中转站必须被连接到正好一个钻油井,反之亦然。 Mary特别指名,建设的天然气管道必须从某个天然气井开始,向南或者向东建设。Mary想知道怎么连接每个天然气井和中转站,使得需要的天然气管道的总长度最小。
题解:
对于天然气(x1,y1)->中转站(x2,y2)曼哈顿距离是x2-x1+y1-y2。其实只有一种情况

堆积木Klo
题意:
给出一个n(<=100000)个数序列,现能从中删若干个。问最多能有有多少ai=i
题解:
一眼最长上升子序列~~ 一秒wa~~
冷静分析一下,f[i]表示使ai最终位置为ai最多多少个 * * *
那f[i]继承f[j]需要的条件是:1、i>j 2、ai>aj 3、i-j>=ai-aj
3转化为i-ai>=j-aj
考虑将ai从小到大加入,这样保证了ai>aj.若此时i-ai>=j-aj,便能保证i>j。那对i-ai开个树状数组就行了

砝码Odw
题意:
公司有m个(<=100000)容器可以装n(<=100000)个砝码。他们想装尽量多的砝码。每个容器可以装的砝码总重量不能超过每个容器的限制wi。任何两个砝码中总有一个的重量是另外一个的整数倍,当然他们也可能相等。
题解:
以前做的。。
好提亚
首先贪心尽量取小的 然而我不知道怎么放 于是膜了题解
因为两两互为倍数,所以不同的种类是log级别的
将重量排序 第i种重量作为第i位的底弄出个新进制,可以将容量写成新进制。然后每位是可加的,高位能向低位借位,低位不能向高位合,然后贪心就好
为什么是正确的呢?我觉得本质是因为重量数很少,并且两两相关,就可以做出容量对每种重量的影响,并且可以调整
低位不能合高位是因为他们必在不同容器中

四进制的天平Wag
题意:
从前有个人想要用天平和砝码称出重量n(<=10^1000)物品,他有所有重量为4的幂的砝码,数量无限。物品放左边,砝码可放左右。问最少用多少砝码,以及最少砝码情况下方案数
题解:
肯定是a+n=b的形式(a,b,n是四进制数),砝码数是a,b的数位和。所以就写个数位dp,从低位往高位弄。f[i][o]表示搞完i位,b是否进位最小值,g[i][o]记录对应方案数。有个小优化就是在每一位上,要么让a=0,要么让b=0,因为如果他们都大于0,让他们同时-1更优



poi2008

砖块Klo
题意:
N(<=100000)柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.
题解:
很显然,对于k个柱,把他们都调整到中位数是最优的。所以我们需要一种数据结构,兹磁加入、删除、查找第k大、求和,我用的是线段树

海报PLA
题意:
N(<=250000)个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.(海报是长方形的,不能贴到矩形外面)
题解:
很显然,对于那个最低的,我们至少要一张长是这个的海报,那么可以贪心一下,让这张的宽从最左到最右,然后递归处理左右,这样做出来是最优的。考虑哪些矩形需要新加入一张海报,就是那些只沿比他高的海报往左(右)走不到和他一样高的海报,那就规定从左往右扫,单调队列就行了

CLO
题意:
n(<=100000)个点,m(<=200000)条边,问能否将某些边定向使每个点1入度
题解:
1入度就是基环+外向树,对于一个联通块,能搞个环套树的条件是有至少一个环,也就是边数>=点数。并查集就好了

激光发射器SZK
题意:
多边形相邻边垂直,边长为整数,边平行坐标轴。要在多边形的点上放一些激光发射器和接收器。满足下列要求: 1发射器和接收器不能放置在同一点; 2发射器发出激光可以沿壁反射,最终到达一个接收器; 3发射器只能沿角平分线发射激光。求:最多可放置多少对发射器和接收器?点数4<=n<=100000
题解:
觉得是个几何题就膜了题解。。竟然是直接输出n/2。。看完题解觉得很对。。

账本BBB
题意:
有个长n(<=1000000)序列,每个数是1或-1,一开始给你p,每到ai,p+=ai,使最后和为q,要求中途不能出现负数。现有2种操作:1、某位取反。2、序列最后一个数移到最前面。每种操作有各自花费,问最少花费
题解:
首先要知道,1和-1个数是固定的,1尽量放前面,-1尽量放后面。
考虑答案一定是将某段后缀移到前面,然后取反一些位,我们枚举将哪里开始后缀移到前面。
枚举到一个位置时,贪心先把1和-1个数修改正确,然后找出前缀和最小的那个点,看要使他合法,需要翻转几次。这里修改1,-1数量使之正确其实不需要暴力改,直接处理这样改对最差点影响就行了。可以证明,最差的点合法后,所有点都合法。假设我们枚举到位置i,到位置j(j>i)的和就是s[j]-s[i-1],s[i-1]是固定的,最差的那个j就是s[j]最小的那个。到位置j(j< i)的和是s[n]-s[i-1]+s[j],也是一样的道理。

BLO
题意:
n(<=100000)个点,m(<=500000)条边,对每个点,问删掉他后有多少对点不连通
题解:
割点随便搞搞就好了。。

枪战Maf
题意:
有n(n<=1000000)个人,每个人手里有一把手枪。一开始所有人都选定一个人瞄准(有可能瞄准自己)。然后他们按某个顺序开枪,且任意时刻只有一个人开枪。因此,对于不同的开枪顺序,最后死的人也不同。问最多和最少死多少人
题解:
一直在想基环—内向树dp想不到只好膜题解了。。
居然是贪心orz!
先看死最多
对于一个简单环,最多n-1。对于一个环套树,最多n-叶节点数
然后死最少
简单环n/2
环套树的话,由于叶节点不会狗代,先把他们加入队列。从队列取出x,他对y开枪,少了个人指z,若此时指着z的人都狗代了,那z也入队。这个贪心正确是因为决策z是否入队时,让z入队,z的父亲节点就药丸,最多让一个可能成为答案的人狗代。z不入队,就是z不对父亲节点开枪,那z就要先狗代,这样至少让一个可能成为答案的人狗代了。环套树最后环上可能没有一个点入队,这时还要特判些什么东西,我就(bu)不(ji)说(de)了

Poc
题意:
有n(<=1000)个字符串,每个长度<=100。现有m(<=100000)个操作,交换某两个字符串的两个字符。对于每个字符串,问所有时刻中,与他完全相同的字符串最多有多少个
题解:
hash一下,写个splay,打个标记就好

KUP
题意:
有个nn(n<=2000)的矩阵,每个位置有非负数。给出k找一个子矩阵,使他的和属于[k,2k]
题解:
跪漆子超神orz
若有一个数在[k,2k],直接输出。
若没有,由于没有非负数,大于2k的数都不能取,将他们标记出来。
此时,剩下所有数小于k
考虑给你一个子矩阵,和大于2k,是否一定有解
我们按行尽量将矩阵和平分,分成x,y(x>y)。若x,y中有一个属于[k,2k]直接输出。
若没有:
1、x>y>2k 随便选x那半或y那半继续平分
2、x>2k,y< k 选x继续平分
注意到不可能出现x< k && y< k,因为x+y>2k
那这样一直分下去,变成一行就分列,由于每个数都小于k,所有不会出现和大于2k分着分着就分不动了,因此一定有解
无解的情况是什么?和最大的子矩阵和< k
那我们就找一个极大子矩阵判无解以及构造解
由于没有负数,极大子矩阵就可以用悬线法搞

Lam
题意:
对于一个长度为n(<=1000)的数列p,数列中任意两个数互质。准备一个无限长的储存器。然后从p1开始,把储存器中p1倍数位置都赋值为p1,把储存器中p2倍数位置都赋值为p2,把储存器中p3倍数位置都赋值为p3。。。把储存器中pn倍数位置都赋值为pn。最后求每个pi在储存器中出现的比例,用分数表示。
题解:
因为后面会覆盖前面,所有从后往前弄
pi被pj覆盖的位置为lcm(pi,pj),由于保证两两互质,所以就是pi * pj的倍数。(如果不保证那应该就要2^n容斥了。。
设ai为pi的答案
本着pj所有覆盖的位置中为pi倍数的数是均匀的的理念,我们推出ai=1/pi-1/pi * sigma(aj)=(1-sigma(aj))/pi (i+1<=j<=n)
然后就用一个高精度分数s存着sigma。s=p/q,上面(1-s)那一块就变成(q-p)/q,若p与q互质,那q-p与q也互质,就不用约分辣~~
然而s累加的时候要高精度约分


想了想就弃疗了。。看题解他的式子是ai=((ai+1 * (pi+1 -1))/pi
就相当于把sigma除了i+1那部分都用ai+1算掉。。这样就只用单精度约分了。。

Per
题意:
给你一个序列s,你把这个序列的所有不同排列按字典序排列后,求s的排名mod m。|s|<=300000
题解:
式子很容易推吧。。涉及除法就把m分解了一个个算最后CRT合并吧。。具体看代码吧。。

POD
题意:
给出一个具有N(<=26)个结点的无向图,将其分成两个集合S1,S2. 这两个集合的点的个数一样多,但连接它们的边最少。
题解:
C(26,13)枚举。。位运算优化。。

Sta
题意:
给出一个N(1000000)个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
题解:
深度之和就是到他的距离之和吧。。tree dp不用说了吧。。

Tro
题意:
平面上有N个点. 求出所有以这N个点为顶点的三角形的面积和 N<=3000
题解:
规定第一个点枚举最左最下点,再按极角枚举第二个点,然后叉积算面积。注意叉积公式,可以记录一个之前的和啥的,就不用枚举第三个点了。。(不吹不黑,ljm口胡的点到直线距离也可以做,不过连我自己都不想打了233


poi2009

石子游戏Kam
题意:
有N(1000)堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子,但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。
题解:
考虑某个人拿掉第i堆x个后,他后面的人可以拿掉i+1堆x个从而抵消。。
于是很像个阶梯博弈。。由于拿掉第n堆无法抵消。。就像阶梯博弈的第一级台阶一样。。于是阶梯的奇数级异或就相当于与n奇偶性相同异或。。

救火站Gas
题意:
给你一棵树n(<=100000),现在要建立一些消防站,有以下要求: 1. 消防站要建立在节点上,每个节点可能建立不只一个消防站。 2. 每个节点应该被一个消防站管理,这个消防站不一定建立在该节点上。 3. 每个消防站可以管理至多s个节点。 4. 消防站只能管理距离(两点间最短路径的边数)不超过k(<=20)的结点。请问至少要设立多少个消防站。
题解:
很妙的一道题啊。。想当年我想了两个星期(其实当天下午就想弃疗看题解,结果根本不知道题解在写什么玩意儿

 
over 1 year ago

hdu3840
题意:
有个nn(n<=40)的网格,要在里面放芯片
有些格能放,有些已放,有些让你选
给出a,b 使每行每列的芯片数不大于总数a/b 问总共最多放多少
题解:
好难啊被虐爆了
首先可以枚举每行列最多放多少个x,算出此时最多芯片数y,检验一下,合法就更新答案
枚举后,要限制行和列的相同 于是构造二分图,一边行,一边列
若某格(x,y)有芯片,则x行向y列有1流量 从i列向i行连一条边 做循环流就保证合法 因为i列被选后i行也要选一个列流出这个流量
然后要求总芯片最多,并且有些是一定要选的
就转化为最大费用循环流,一定要选就把他的费用设为很大

hdu3157
题意:
有源汇上下界最小流
题解:
超级源汇、连边都和上下界一样 平时上下界会在原汇到原源连一条下界0,上界inf的边 现在先不连做一次最大流 再连上做一次那条边流量就是答案
因为要最小化这条边的流量就先让能流别的地方先流别的地方,剩下就是非要流这条边的了

hdu4859
题意:
有个nm的格子(n,m<=47),有些地方是陆地有些是海有些让你选。若两个相邻格子不同,则他们之间有一条海岸线,nm外默认为海。选一个方案让总海岸线最长。
题解:
本来每条边都能成为海岸线 当相邻两个格选了相同的东西的时候就会有1的损失 因为是相同所以要二分图黑格正着建 白格反着建

hdu5594
题意:
有n(<=200)个数,问能否将他们分为若干个环,使每个环相邻两数相加为质数 环大小至少为3
题解:
好难啊被虐爆了
首先可以暴力看哪两个数可以相邻
如果忽略1的话相邻两数一定是1奇1偶
本来环的模型是1出度1入度
为了限制大小,做个二分图 让奇数连到偶数 源到奇数2容量,奇数到偶数1容量,偶数到汇2容量 这样若满流,就保证环至少为4
先将1当奇数补到奇偶数相同,若满流就有解 很多1可以当成1个1来用
有1种特殊情况就是1-x(如2)-1 这种情况只发生在所有1和x在一个环上 若不是的话可以拼上去 此时就如果要加入的1个数为1并且1总数大于1就把他到偶数的边连2
无解情况yy就好了

bzoj3144
题意:
有个abc的立方体(a,b,c<=40)要横向切开,要切开一个ab的面,要求面上相邻两点高度差不能大于d。每个点都有花费,问总花费最少
题解:
麻麻我会做切糕辣
我会告诉你我做过rin吗。。
考虑如何限制高度差

这样就能限制蓝色那条边了

uva11604
题意:
给n(<=100)个01串,每个长度不超过20 问有没有办法拼出两个相同的串 拼法不能完全相同 每个01串可在两个串中多次出现
题解:
好难啊被虐爆了
两个大串g1,g2
考虑每次都给g1加入一个串,g2跟着g1用合法串匹配,最后匹配了某一段前缀
首先可以枚举两两串做exkmp
假设s1[1..i]匹配s2[j..j+i-1]看看有什么用
1、i=len1 j+i-1=len2 如果g2走到了s2[j]那就能g1加s1,g2匹配完成 从s2[j]向终点连一条边
2、i=len1 j+i-1< len2 如果g2走到了s2[j],g1加入s1,g2走到j+i-1 从s2[j]向s2[j+i-1]连一条边
3、i< len1 j+i-1=len2 此时调换g1和g2 换后g1加入s1,g2走到s1[i+1] 从s2[j]向s1[i+1]连一条边
4、i< len1 j+i-1< len2 此时并没有什么卵用,因为考虑g1是完整的串拼成,最终答案一定可以是一直加完整的串
连完边后把每个串开头和起点相连,看看起点到终点连不连通就行了

la3661
题意:
给nm(n,m<=1000)的格子,格子间有这样的边


割一些边让起点和终点不连通,问最少花费
题解:
好难啊被虐爆了
最小割肯定可以,但太慢了
由于图的特殊性,割的边一定是这样的

就是从坐下到右上。
就把那些三角形的三条边当成点,互相连边 左边和下边连起点,右边和上边连终点 最短路就是答案

bzoj1312
题意:
麻烦程度可以认为是(带来麻烦的人的对数/总人数)。求最大麻烦程度时总人数最大。在这样的一个公司中,保证公司的人数小于100人,带来麻烦的员工不会多于1000对。
题解:
最大密度子图 边权/点权最大
二分k 表示 检验a/b>=k能否成立 即a-kb>=0是否成立
点权乘上k后 边权为正数 点权为负数 选一条边必选那两点
看最大权闭合子图是否大于0
大于0就找割边,就是我们尽量割连点权和汇的边 那就把必定不是割边连点权和汇的边(残量大于0)的拿出来 剩下的就是割边
此时合法且最大

 
over 1 year ago

真是呵呵呵呀。。
t1
题意:
有个数列,两个人在玩游戏。第一个人先把满足ai大于ai+1的某两数对调,第二个人50%概率对调ai大于ai+1两数,50%概率对调ai小于ai+1两数。问期望多少轮结束
题解:
发现只会把逆序对+1或-1,结束状态为逆序对0
随便推推就行了
p.s.多少轮看成多少次操作 推期望还没乘2。。发现我真的很搞笑。。
t2
题意:
有两个01串,长度小于4000。有些位置是?,选填01。最后代价就是两个串所有位置匹配不匹配的数个数。问最小代价,构造方案
题解:
最小割!!然而我不会找割边,然后就开始各种yy。。然后就跪在这题上了。。
割边找法:从st开始bfs,只经过残量网络大于0的边,把到的点标记。标完后看所有边,若他剩余流量为0,且一端被标另一端没被标就是割边
t3
题意:
给n(<=1000)个点,问把所有点移动到同一条直线上最小代价。移动代价就是移动距离
啊计算几何好难根本不会
t4
迷之题意:


答案对质数取mod
题解:
其实挺良心的一道数据结构。。我推出了每个果子对祖先的贡献就是果子的值连乘到祖先每个点的边数 但由于太多时间花在t2 而且题意太迷 我连样例都画不出来TAT 最后打了个wa暴力。。
说实话推出那东西后就区间乘除、单点改数,除用逆元就行了

include

include

include

include

include

define N 310000

define mmod 10000019

define LL long long

using namespace std;
struct node{LL o,x,d;}q[N];
struct node1{LL l,r,lc,rc,sum,d,lz;}lt[2*N];
struct node2{LL y,next;}a[2*N];
LL n,m,dfn[N],las[N],id,tl,fa[N],cnt[N],first[N],ltlen,ans,len;
LL qmod(LL a,LL b)
{
LL t=1;
while(b)
{
if(b&1) t=(t*a)%mmod;
a=(a*a)%mmod;
b>>=1;
}
return t;
}
void ins(LL x,LL y)
{
a[++len].y=y;a[len].next=first[x];first[x]=len;
}
void dfs(LL x,LL ff)
{
fa[x]=ff;
dfn[x]=++id;
for(LL k=first[x];k;k=a[k].next)
{
LL y=a[k].y;
if(y==ff) continue;
dfs(y,x);
}
las[x]=id;
}
void bt(LL l,LL r)
{
LL now=++ltlen;
lt[now].l=l;lt[now].r=r;
lt[now].lc=lt[now].rc=-1;
lt[now].sum=0;
lt[now].d=lt[now].lz=1;
if(l {
LL mid=(l+r)/2;
lt[now].lc=ltlen+1;bt(l,mid);
lt[now].rc=ltlen+1;bt(mid+1,r);
}
}
void down(LL now)
{
LL lc=lt[now].lc,rc=lt[now].rc;
if(lc!=-1) lt[lc].lz=(lt[lc].lz*lt[now].lz)%mmod;
if(rc!=-1) lt[rc].lz=(lt[rc].lz*lt[now].lz)%mmod;
lt[now].d=(lt[now].d*lt[now].lz)%mmod;
lt[now].sum=(lt[now].sum*lt[now].lz)%mmod;
lt[now].lz=1;
}
void upd(LL now)
{
LL lc=lt[now].lc,rc=lt[now].rc;
if(lt[lc].lz>1) down(lc);
if(lt[rc].lz>1) down(rc);
lt[now].sum=(lt[lc].sum+lt[rc].sum)%mmod;
}
void change(LL now,LL k,LL d)
{
LL mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;
if(lt[now].lz>1) down(now);
if(lt[now].l==lt[now].r) {lt[now].sum=(lt[now].d*d)%mmod;return;}
if(mid>=k) change(lc,k,d);
else change(rc,k,d);
upd(now);
}
void modify(LL now,LL l,LL r,LL d)
{
if(l>r) return;
LL mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;
if(lt[now].lz>1) down(now);
if(lt[now].l==l && lt[now].r==r)
{lt[now].lz=(lt[now].lz*d)%mmod;return;}
if(mid>=r) modify(lc,l,r,d);
else if(l>mid) modify(rc,l,r,d);
else modify(lc,l,mid,d),modify(rc,mid+1,r,d);
upd(now);
}
LL find(LL now,LL l,LL r)
{
LL mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;
if(lt[now].lz>1) down(now);
if(lt[now].l==l && lt[now].r==r) return lt[now].sum;
if(mid>=r) return find(lc,l,r);
else if(l>mid) return find(rc,l,r);
else return find(lc,l,mid)+find(rc,mid+1,r);
}
LL get_d(LL now,LL k)
{
if(k==0) return 1;
LL mid=(lt[now].l+lt[now].r)/2,lc=lt[now].lc,rc=lt[now].rc;
if(lt[now].lz>1) down(now);
if(lt[now].l==lt[now].r) return lt[now].d;
if(mid>=k) return get_d(lc,k);
else return get_d(rc,k);
}
int main()
{
LL tt;
scanf("%I64d%I64d",&tt,&m);
tl=1;
for(LL i=1;i<=m;i++)
{
scanf("%I64d",&q[i].o);
scanf("%I64d",&q[i].x);
if(q[i].o==1) {ins(q[i].x,++tl);q[i].x=tl;scanf("%I64d",&q[i].d);}
}
dfs(1,0);
ltlen=0;
bt(1,tl);
cnt[1]=1;
change(1,dfn[1],tt);
for(LL i=1;i<=m;i++)
{
LL x=q[i].x,ny;
if(q[i].o==1)
{
ny=qmod(cnt[fa[x]],mmod-2);
modify(1,dfn[fa[x]],las[fa[x]],ny);
cnt[fa[x]]++;
modify(1,dfn[fa[x]],las[fa[x]],cnt[fa[x]]);
cnt[x]++;
change(1,dfn[x],q[i].d);
}
else
{
ans=find(1,dfn[x],las[x]);
ny=get_d(1,dfn[fa[x]]);
ny=qmod(ny,mmod-2);
printf("%I64d\n",(ans*ny)%mmod);
}
}
return 0;
}

 
over 1 year ago

嘛。。成功的被自己的flag玩残了。。
t1
给出l,r(l,r<=10^9,r-l+1<=10^5),n(<=10^5),m(<=10^9)
询问从l到r可重复选n个数gcd为m的方案数
容斥搞搞就行辣(莫名其妙wa两点)
p.s.暴力分多了10分不开心
t2
n(<=1000)个点,m(<=100000)条边 每个点有流量 每条边有边权
问从1到n只走最短路的最大流
跑一遍最短路拆点最大流就好了。。(有个地方long long打成int掉了6个点TAT)
p.s.出题人不卡spfa不开心
t3
有n个时刻(<=10^6),m(<=10^6)个任务,每个任务有l,r,d表示开始时间结束时间重要程度,其中d<=10^7
强制在线询问某个时刻重要程度前k小任务重要度和
线段树合并搞搞就行了。。
t4


看到这样的题面就觉得很慌 然后就看错题了 以为要解一个x出来 然后就出于人类本能弃疗了。。
后来看看,,不就是个暴力二项式嘛。。
现场做这题码力真是没话说

include

include

include

include

include

define N 8100

define mmod 10000

define LL long long

using namespace std;
struct node{LL len,a[N],zf;}n,m,res,z[10],f[10],c,tt,b[10],g,gt,rest;
char s[N];
LL t,cf,num,len,a[10],k;
void read(node &a)
{
scanf("%s",s+1);
len=strlen(s+1);
cf=1;num=0;
for(LL i=len;i>=1;i--)
{
num+=cf*(s[i]-'0');
cf*=10;
if(cf>=10000)
{
a.a[++a.len]=num;
cf=1;
num=0;
}
}
if(num) a.a[++a.len]=num;
}
void clear(node &a)
{
for(LL i=1;i<=a.len;i++) a.a[i]=0;
a.len=a.zf=0;
}
void mns(node &a,node &b,node &c)
{
clear(c);
c.len=a.len;
for(LL i=1;i<=c.len;i++) c.a[i]=a.a[i]-b.a[i];
for(LL i=1;i<=c.len;i++)
if(c.a[i] LL i=c.len;
while(c.a[i]==0 && i>0) i--;
c.len=i;
}
void dvd(node &a,LL b)
{
for(LL i=a.len;i>=1;i--)
{
a.a[i-1]+=(a.a[i]%b)mmod;
a.a[i]/=b;
}
LL i=a.len;
while(a.a[i]==0 && i>=1) i--;
a.len=i;
}
LL qmod()
{
LL g[3][3],t[3][3],a[3][3];
a[1][1]=1234;a[1][2]=1;
a[2][1]=0;a[2][2]=1;
bool bo=0;
while(m.len>1 || m.a[1])
{
if(m.a[1]%2)
{
if(bo)
{
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
g[i][j]=0;
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
for(LL k=1;k<=2;k++)
g[i][j]=(g[i][j]+t[i][k]*a[k][j])%3389;
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
t[i][j]=g[i][j];
}
else
{
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
t[i][j]=a[i][j];
bo=1;
}
}
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
g[i][j]=0;
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
for(LL k=1;k<=2;k++)
g[i][j]=(g[i][j]+a[i][k]*a[k][j])%3389;
for(LL i=1;i<=2;i++)
for(LL j=1;j<=2;j++)
a[i][j]=g[i][j];
dvd(m,2);
}
return (t[1][1]+5678*t[1][2])%3389;
}
bool cmp(LL x)
{
if(z[x].len>f[x].len) return 1;
if(z[x].len for(LL i=1;i {
if(z[x].a[i]>f[x].a[i]) return 1;
if(z[x].a[i]<f[x].a[i]) return 0;
}
return 0;
}
void get(LL x)
{
f[x].a[1]+=a[x];
if(f[x].len==0) f[x].len=1;
for(LL i=1;i<=f[x].len;i++)
{
f[x].a[i+1]+=f[x].a[i]/mmod;
f[x].a[i]%=mmod;
}
if(f[x].a[f[x].len]) f[x].len++;
if(cmp(x)) {mns(z[x],f[x],b[x]);b[x].zf=-1;}
else {mns(f[x],z[x],b[x]);b[x].zf=1;}
}
void tms(node &a,node &b,node &c)
{
clear(c);
if(b.len==0 || b.len==1 && b.a[1]==0) return;
c.len=a.len+b.len-1;
for(LL i=1;i<=a.len;i++)
for(LL j=1;j<=b.len;j++)
c.a[i+j-1]+=a.a[i]
b.a[j];
for(LL i=1;i<=c.len;i++)
{
c.a[i+1]+=c.a[i]/mmod;
c.a[i]%=mmod;
}
LL i=c.len;
while(c.a[i+1])
{
i++;
c.a[i+1]+=c.a[i]/mmod;
c.a[i]%=mmod;
}
c.len=i;
}
void pls(node &a,node &b)
{
LL l=max(a.len,b.len);
for(LL i=1;i<=l;i++) a.a[i]+=b.a[i];
for(LL i=1;i<=l;i++)
{
a.a[i+1]+=a.a[i]/mmod;
a.a[i]%=mmod;
}
LL i=l;
while(a.a[i+1])
{
i++;
a.a[i+1]+=a.a[i]/mmod;
a.a[i]%=mmod;
}
a.len=i;
}
int main()
{
freopen("polynomial.in","r",stdin);
freopen("polynomial.out","w",stdout);
read(n);
scanf("%I64d",&t);
read(m);
mns(n,m,res);
k=res.a[1];
a[k]=qmod();
for(LL i=k-1;i>=0;i--)
a[i]=(a[i+1]*1234+5678)%3389;
for(LL i=0;i<=k;i++)
{
get(i);
c=tt=n;
n.a[1]--;
for(LL j=1;j<=n.len;j++)
if(n.a[j]<0) n.a[j]+=mmod,n.a[j+1]--;
else break;
if(n.a[n.len]==0) n.len--;
clear(g);
g.a[1]=t%mmod;
g.a[2]=t/mmod;
if(g.a[2]) g.len=2;
else g.len=1;
gt=g;
for(LL j=i+1;j<=k;j++)
{
dvd(c,j-i);
tms(c,b[i],res);
LL o=1;
if((j-i)%2) o=-o;
if(b[i].zf==-1) o=-o;
tms(res,g,rest);
if(o==1) pls(z[j],rest);
else pls(f[j],rest);
tt.a[1]--;
for(LL j=1;j<=tt.len;j++)
if(tt.a[j]<0) tt.a[j]+=mmod,tt.a[j+1]--;
else break;
if(tt.a[tt.len]==0) tt.len--;
tms(c,tt,res);
c=res;
tms(g,gt,res);
g=res;
}
}
printf("%I64d",b[k].a[b[k].len]);
for(LL i=b[k].len-1;i;i--) printf("%04d",b[k].a[i]);
return 0;
}
t5
..
p.s.暴力多了20分不开心
3题正解还没2题正解+暴力分高。。看来懒得打暴力真是药丸压。。

 
over 1 year ago

大概是对着TC思考人生太久了,觉得码力大减。。是时候来一波常练了
bzoj4379
(从今天开始,世界上就有15个人A了这道题辣~~ 手动撒花~~)
题意:
给一棵树,500000个点,定义直径为最长链。现在可以删一条边再加一条边,求新树最大直径、最小直径和构造方案
题解:
最长直径
枚举要删x和他父亲的边,删了后新直径就是x子树直径+除x子树直径+1 找个max后去找哪两个点是这两条直径
最短直径
首先一定删的是原最长直径上的边,不然最长不会变短
枚举删x和父亲的边,那拼起来的树的直径为x子树直径,除x子树直径,一条过新加的边的最长链中最大值
其实就是要最小化过新加边的最长链,连接i,j两点后,最长链就是i到x子树中最远点距离+j到除x子树最远点距离
注意只有i为x子树直径中点时最远点最近,j也同理 证明很简单吧。。
于是就找个min记下这两条直径去找中点就行了
x子树直径,除x子树直径树形dp都可以做
p.s.写起来真心淡腾。。

bzoj1996
题意:
有n(<=1000)个人,身高各不同。依次入队,若某人比上一个入队的人高,则排在当前最右,否则在当前最左
给目标队列,问有多少种方法入队
题解:
注意排队的过程是从最终队列中间一直延伸到两边的,就可以写个dp f[i][j][0,1]表示i到j这一段,最后入队的人排在了左(右)端有多少种合法方案

luoguP2267
题意:
n(<=500000)个数,可能相同。从左到右选若干个成为新数列,问有多少种新数列
题解:
讲道理写个辣么长的题面是不是应该把重点标出来。。一开始没看到从左到右觉得是道神题,狂想组合数想不出来TAT
其实找每个数上次出现位置搞搞就好了吧。。

bzoj1710
题意:
给一个字符串,长度小于2000,有m(<=26)种字符可用,原串也只有这m种
给出每种字符删去或添加费用,可在串任意位置添或删,问把原串变为回文最少费用
题解:
yy了个f[i][j]表示i到j这段变为回文最少费用
感觉很迷,一写竟然A了。。

bzoj2802
题意:
有个商店,第i天早上会进ai个货,中午有个人会来买bi个货。可选卖不卖,不够就不能卖。
问最多能卖几人
题解:
我想了个线段树的做法 贪心选bi最小最靠后的看他能不能买 线段树维护一些东西就行了
然而线段树的常数是真.名不虚传。。
于是膜了题解
题解就是每个人一直取 取到不能取了就看看把之前取过最大的拿出来能不能取 用堆维护就行了

bzoj2790
题意:
给出n(<=100000)个正整数(<=10^6)。定义d(ai,aj)为ai变为aj最少操作次数,每次操作能乘一个质数或除一个质数。除的时候必须是因子。询问对于每个i,使d(ai,aj)最小的最小的j(好绕啊。。)是谁
题解:
首先g(x)表示x有几个质因数
推出d(ai,aj)=g(ai)+g(aj)-2g(gcd(ai,aj))
然后怎么做呢。。膜题解吧
“对于每个ai,可以枚举他的因子x,预处理f(x)表示有x这个因子的aj g(aj)最小值是多少”
天啦噜。。枚举因子不是10^9的吗。。
其实枚举到的x记录的那个最小的g(aj)与ai最大公约数不一定是x,但没关系,枚举到对的gcd时一定更优
还有个trick,f(x)可能就是从ai来的,所以还要记录次大值。。

bzoj3831
题意:
n(<=10^6)个点,给出m(<=n-1),每个点有高度。从一个点跳到高于这个点的点疲劳+1,否则不加。
i点可以跳到i+1,..,i+m这些点。问从1到n最小疲劳
题解:
从后往前dp就行了吧。。
优先选答案最小的,答案相同就优先选高度最小的。。

bzoj2442
题意:
n(<=100000)个人,每个人有个价值,不能选连续超过m(<=n)个人,问最大总和
题解:
承认只会线段树系列。。
写了个线段树就喜闻乐见的T了
f[i]表示选i最大
g[i]表示不选i最大
f[i]=max(g[j]-s[j]+s[i]) i-m<=j<=i-1
g[i]=max(g[i-1],f[i-1])
然后就单调队列了

bzoj2274
题意:
n(<=100000)个人,每个人有价值。把人划为若干段,使每段和非负。问有多少划分方法
题解:
承认只会线段树系列。。
吸取上题教训想不到比线段树更优的方法就看了题解
居然就是树状数组。。为什么。。

bzoj3398
题意:
选n(<=100000)个人出来。有黑色和白色,要求两个黑色之间至少k个白色,有多少种排法
题解:
too simple

bzoj1264
题意:
两个序列,n(<=20000)种颜色,每种颜色恰好出现5次,问最长公共子序列
题解:
too simple

bzoj3747
题意:
共有m部电影,编号为1~m,第i部电影的好看值为w[i]。
在n(<=1000000)天之中每天会放映一部电影,第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n),并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
题解:
考虑枚举右端点 用线段树随便搞搞就行了

bzoj3521
题意:
有一个长度为n(<=1000000)的字符串,每一位只会是p或j。你需要取出一个子串S(从左到右或从右到左一个一个取出),使得不管是从左往右还是从右往左取,都保证每时每刻已取出的p的个数不小于j的个数。你需要最大化|S|。
题解:
把p当成1,j当成-1,就是任何时候和>=0
把和转化为前缀相减,发现开始点要最小,结束点要最大
可以用单调栈做出某个点最大最小可覆盖多远
看到时限我还以为是线性的怎么都想不到

最后看到是线段树 那枚举左端点随便做

bzoj1110
题意:
公司有m个(<=100000)容器可以装n(<=100000)个砝码。他们想装尽量多的砝码。每个容器可以装的砝码总重量不能超过每个容器的限制wi。任何两个砝码中总有一个的重量是另外一个的整数倍,当然他们也可能相等。
题解:
好提亚
首先贪心尽量取小的 然而我不知道怎么放 于是膜了题解
因为两两互为倍数,所以不同的种类是log级别的
将重量排序 第i种重量作为第i位的底弄出个新进制 可以将容量写成新进制 然后每位是可加的 高位能向低位借位,低位不能向高位合 然后贪心就好
为什么是正确的呢?我觉得本质是因为重量数很少,并且两两相关 就可以做出容量对每种重量的影响 并且可以调整
低位不能合高位是因为他们必在不同容器中

bzoj3315
题意:
一个坐标轴有N(<=1000)个点,每跳到一个点会获得该点的分数,并只能朝同一个方向跳,但是每一次的跳跃的距离必须不小于前一次的跳跃距离,起始点任选,求能获得的最大分数。
题解:
f[i][j]表示i从j来最大分数,n^3很好想
怎么优化?我还在想二分+树状数组之类的辣鸡东西
其实对每个i的j单调加入维护g[i]表示最大值就行了 一共n^2个数,每个加入一次 所以是n^2的

刷水刷水 越刷越水~~
是时候来一波高(bu)姿(hui)势(zuo)的dp辣

UR1外星人
题意:
给n(<=1000)个数,ai<=5000。给出x(x<=5000)。排列这n个数,从左到右扫过去。一开始y=x。碰到一个ai,y变成y%ai。问排列得到最后与x最接近y以及能得到这个y的排列方案数
题解:
注意到如果%ai前%了aj(ai>aj)那ai就没有影响了。那不妨将ai从小到大排序~~
设f[i][j]为排完前i个人,我一开始给你j,最后最优答案。g[i][j]为对应方案数
考虑ai加入时影响。因为前面所有人都比ai小,ai只有加在头才有影响。分加在头和不加在头讨论
加在头:那么f[i][j]就可从f[i-1][j%a[i]]来
不加在头:f[i][j]从f[i-1][j]来

APIO2015 Bali Sculptures
题意:
给n个数以及a,b。对n个数分组,恰好分为x组(a<=x<=b)。最后花费为每段的和按位或(好绕啊233)。问最小花费
对于a=1,n<=1000 对于a>1,n<=100
题解:
我们可以按位贪心,看每个位能不能取0。对于a=1,做个f[i]表示前i个数至少分成几组,n^2。对于a>1,做个f[i][j]表示前i个数分j组是否可行n^3。我还想大概不是这样吧,应该正解很厉害吧,怎想他那么无聊强行2合1。。

UER4被粉碎的数字
题意:
给出n(<=10^18),k(< 1000)。设f(i)表示i数位和。问有多少i<=n,f(i)=f(i乘k)
题解:
因为k< 1000,所以一个位最多影响后面3个位
那就写个f[i][a][b][c][x][o]表示考虑了i位,对后3位影响分别是a、b、c,差为x,是否大于n的数有多少个
因为进位这个东西是从低位影响高位,那就从低位往高位推~~

是时候抢救一下智商了

bzoj3622
题意:
有n(<=2000)个糖果,n个药片,每个糖果和药片上都有一个数字,这2n个数字两两不同。现要将糖果和药片两两配对,刚好一个糖果配一个药片,问有多少种配法使存在糖果的值比药片大的对数比药片比糖果大的对数多k对。
题解:
想了会儿没思路就%题解辣。。
将糖果和药片排序后可以做出nex[i]表示第i小的糖果比1..nex[i]的药片大
设f[i][j]表示考虑前i个糖果,确定j个配对药片比他小,其他糖果不考虑的方案数
f[i][j]=f[i-1][j]+f[i-1][j-1] * (nex[i]-(j-1))
前一部分是不考虑第i个,后一部分是考虑
这时把没考虑的算进去
g[n][i]表示恰好i对糖果比药片大方案
g[n][i]=f[n][i] * (n-i)! - g[n][j] * c(j,i) (j>i)
乘排列就表示考虑剩下的所有方案,从中要减去超过i对的方案。
某个最后有j对的方案,这j对中选i对被f[n][i]考虑有c(j,i)种情况,而每种情况都能弄出一个那样最后有j对的方案
最后x=(n+k)/2,g[n][x]就是答案
为什么看题解觉得很对,我却想不到:(

bzoj4033
题意:
有一棵点数为 N(<=2000)的树,树边有边权。给你一个在0~ N之内的正整数K,你要在这棵树中选择 K个点,将其染成黑色,并将其他的N-K个点染成白色 。 将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。
题解:
。。想的太复杂了。。只好膜题解
f[i][j]表示i子树染j个黑最大值,然后注意我们确定这个后,就能确定经过i到i父亲这条边有几对人了,然后就可以搞了
这题很像松鼠移苹果那题压。。然而我却忘了。。
dp最重要的就是设计出一个复杂度可以接受的,确定了一些东西,然后知道这些东西就可以知道怎样影响的状态吧

bzoj2064
题意:
有a,b两个序列,和相等,每个序列元素个数小于等于10。每次可以将一个元素分为和等于他的两个元素,或把两个元素和成一个值为他们的和的元素。一开始有a序列,问最少多少次操作能变为b序列
题解:
合并分裂的方式一定是一直合合合然后分分分,不会出现分不完又去跟别人合的情况,因为这样一定不比一开始合起来优
a序列x个数要变成b序列y个数要x+y-2次操作,就是全合起来然后一个个分
于是我就想状压然后枚举子集,可惜3^20太大了
题解处理的方法很巧妙
假设最后分成k坨,那最后答案是n+m-2 * k,所以可以最大化k
同样状压,然后f[i][j]可以从i拿掉或j一个数找个max继承过来,最后当suma[i]=sumb[j]时,f[i][j]++
为什么这样是对的呢?
考虑我刚刚说的,每次是在a找一堆数,b找一堆和相等数来继承,那这样每个合法状态a中选的与b中选的和相等
像上面那样max继承,那f[i][j]继承的值一定是最大的f[x][y],其中x为i子集,y为j子集,suma[x]=sumb[y],因为每次拿一个数,能继承的其实都是他的子集
然后suma[i]=sumb[j],suma[x]=sumb[y],代表suma[i xor x]=sumb[j xor y],那i xor x,j xor y其实就是我们要找的那个子集了
(枚举子集劲啊。。交一发居然A了,还碾了正解。。

CH Round #54(NOIP模拟赛Day1)/高维网络
题意:
有个n(<=100)维网格,第i维范围是0..a[i]。现有m(<=500)个点坏了,从(0,..,0)到(a1,..,an),只能向坐标大的地方走,问不经坏点有多少种方法
题解:
(注意在这种网格上从(x1,..,xn)走到(y1,..,yn)的方案数是s:
ci=yi-xi,cnt=sigma ci
s=cnt!/(c1!c2!...cn!)
就是全排列然后除掉等价元素自己里面全排列
看到80%可以暴力容斥,于是就想100%是不是很厉害的容斥。。结果就是个普通dp
明明搜的是容斥题,为什么会这样。。
普通dp我想容斥想不到的时候随便想了想,想弄个g[i][j]表示i到j合法方案数,f[i][j]表示i到j不合法方案数
f[i][j]就(枚举第一个不合法点k)g[i][k] * (k到j全部方案数)
g[i][j]用(i到j全部方案)-f[i][j]
我一看这n^3妥妥跪,还是想容斥吧。。
其实把他们合在一起,g[i][j]就变成了(i到j全部方案)-(枚举第一个不合法点k)g[i][k] * (k到j全部方案数)
发现g[i][j]只从g[i][k]来,与g[..]无关,所以只用做(0,...,0)为起点。把(0,...,0),(a1,...,an)加入,最后g[m+2]就是答案。。

bzoj3812
题意:
一个n(<=15)的有向图,给出m条边,问有多少种边集使整个图强联通
题解:
题解都看了一天才看懂TAT。。
考虑求出非强联通即dag的方案数用全部情况减
注意统计dag从出度为0的点入手,这题中就是缩点后出度为0的点
先考虑一个辣鸡做法
若现全集为s,我们已经知道某种方案子集t会缩成k个强连通分量,这些强连通分量出入度都为0
那么我们可以得出s至少缩成k个出度0强连通分量的一类方案数(即用t中这k个限制最小的方案)为2^x(x为s^t里的点为起点,s里的点为终点的边数)。因为这x条边的所有连法,包括了所有缩点后有大于等于k个的方案。
(容斥很重要的一点就是设置“至少为。。” 状态,注意“至少k状态”应包含所有“为x状态”,其中k是x的子集
然后我们就上容斥,对于至少k个出度0的方案,当k为奇数时就减,当k为偶数时就加
现在考虑正解
我们枚举一个子集的某种方案,看他的出度0个数是奇还是偶太慢了
注意对于一种方案我们关心的只是他是哪个点集,他缩完点后有奇数个出度为0还是偶数个出度为0,其中奇数时就-1,偶数时就+1
那我们可以设g[s]表示s这个点集所有缩点成若干个强连通分量方案的贡献和,其中缩成奇数个的方案贡献-1,偶数的贡献+1
设f[s]表示s为一个强连通方案数,s内部有h[s]条边,那么
f[s]=2^h[s]+sigma (2^cnt) * g[t]
t为s的子集,cnt为起点在s^t中,终点在t中的边数
注意这一步是已经带上容斥的,因为g[t]是容斥贡献和
然后
g[s]=-f[t] * g[s^t] - f[s];
其中t为包含s最小标号节点子集。g表示缩为若干个出度0强连通,t就是枚举最小标号所在强连通,这样保证情况不重不漏。前面的-代表,加入t这个强连通分量后,原来方案的强连通数奇偶取反,所以贡献正负取反。最后-f[s]就表示单独s这一个强连通分量,因为1是奇数,所以每种方案贡献是-1
然后就做完辣owo

Codeforces 37D. Lesson Timetable
题意:
有编号为1,2,⋯,m一共m(<=100)个教室和编号为1,2,⋯,n(<=1000)一共n个学生,每个学生要上2节课,要求第一节上课的教室编号不能大于第二节上课的教室编号
第i个教室还需要满足
第一节课必须恰好有Xi个学生在这里上课
同一时间不能有超过Yi个学生在该教室上课
问有多少种上课方案
题解:
想歪了啊。。考虑每个学生第二节课一定是往后走,所以我想从后往前考虑每堆学生,看第一节课在第i个课室的学生第二节课往后走有多少种方法。但这样无法区别分到了多少个课室的情况,也无法知道哪些课室能装下多少人。
正解是从前往后考虑每个课室,这样就没了容量限制的问题了。设f[i][j]表示前i个课室已经确定j人方案,然后枚举现在课室第二节课有多少人组合数转移。最后再给每个学生标号就乘全排列/内部排列也就是n!/(x1! * .. * xn!)。

Codeforces 40E. Number Table
题意:
给出一个n×m的矩阵,每个元素都是1或−1,其中有k个位置元素已经确定,并且这个矩阵满足每一行、每一列元素的乘积都是−1,问有多少种不同的矩阵
数据范围是 1≤n,m≤1000,0≤k< max(n,m)
题解:
我只看了一眼题解


当行列奇偶相同时能找一行全空,让其他行只保证行合法情况下,这行有唯一方案能使列合法,同时必然使行合法。否则无论列的状态是怎么样的,使列合法的方案必然使行不合法。证明不写了。
然后就随便艹了。。
(这种矩阵行列或相邻相关的题,注意确定一些情况就能推出其他情况或别的行随便搞能找某一行把他们都弄合法

Codeforces 9D. How many trees?
题意:
统计有多少棵二叉树满足有n个节点,并且高度不小于h,其中 n,h≤35
题解:
设f[i][j]表示i个节点高度j方案数
分一个孩子还是两个孩子
一个孩子2 * f[i-1][j-1]
两个孩子2 * f[k][j-1] * s[i-k-1][j-2]。就其中一个高度为j-1,枚举有多少节点,另一个孩子就是剩下的节点,高度为1..j-2。因为这时算上另一边高度j-1会重。两边都是j-1就f[k][j-1] * f[i-k-1][j-1]。

Codeforces 28C. Bath Queue
题意:
有n个人等概率随机进入m个房间,一个房间可以有多个人,第i个房间有ai个水龙头,在一个房间的人要去排队装水,他们会使得最长的队尽可能小,求所有房间中最长队列长度的期望。(n,m<=50)
题解:
期望长度就是所有情况下的长度和/情况数
考虑dp。f[i][j][k]表示前i个房间,进了j个人,最长队列为k有多少种方案。
然后枚举这个房间进了l个人,就可以算出此时最长队列为t
f[i][j][t]+=f[i-1][j-l][k] * c(n-j+l,l)

Codeforces 382E. Ksenia and Combinatorics
题意:
有一棵 n(n≤50)个节点的树,节点标号为 1,2,⋯,n除了1号节点最多会与其它2个节点连边外,其余节点最多会与其它3个节点连边,两棵树是相同的,当且仅当每个节点的相邻节点都相同,问有多少种不同的这样的树,满足它的最大匹配是k,答案对10^9+7取模
题解:
这是个二合一题啊owo。。
首先这是一颗以1为根的二叉树
设f[i][j][0..1]表示i个点,最大匹配为j,根节点是否匹配的方案数
我是限制根节点标号最小,限不限制都可以。这样限制转移时就乘上一个子树大小就行了,因为此时他和根相连了,所以每个标号在这个地方都是不重复的情况。
yy一下就知道若x子树某最大匹配方案根y匹配了,把y的匹配拆开让y和x匹配不会更优
所以f[x][1]只从f[y][0]来。同样,当孩子y没匹配时,最大匹配一定要让x和y匹配,若x两个孩子都没匹配,让x随便匹配一个就行了
根只有一个孩子的转移就不说了
有两个孩子的话,枚举左孩子大小和匹配数。为了避免重复,就限制左孩子小于等于右孩子。当左右孩子大小相等时,再限制左孩子匹配数小于等于右孩子。当大小和匹配数都相同时,这是两堆相同的情况在弄,所以要除2。转移方案数就组合数子树大小乘一乘就行辣

 
over 1 year ago

Hi, This a demo post of Logdown.

Logdown use Markdown as main syntax, you can find more example by reading this document on Wikipedia

Logdown also support drag & drop image uploading. The picture syntax is like this:

Bloging with code snippet:

inline code

Plain Code

puts "Hello World!"

Code with Language

puts "Hello World!"

Code with Title

hello_world.rb
puts "Hello World!"

MathJax Example

Mathjax

Inline Mathjax

The answser is .

Table Example

Tables Are Cool
col 1 Hello $1600
col 2 Hello $12
col 3 Hello $1