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。转移方案数就组合数子树大小乘一乘就行辣

← Hello World 2016-4-2 CQOI2015 →