除草

leaf posted @ 2015年3月20日 20:24 in 未分类 , 836 阅读

由于最近越来越颓,为了增加动力,就写下来吧。。

(dp地狱训练)

SRM 503 DIV1    500pt ( 求期望题.贪心,枚举,概率计算 ) 答案分成两点之间的答案,再组合数统计即可。注意dist相同的情况,可以规定优先级。。先连city,再按顺序连village,这样就很方便了。。ll没开怎么死都不知道!!

 

SRM 507 DIV1    900pt ( dp+组合数学基础 ) 直接暴力dp即可

 

SRM 495 DIV1    975pt(数学, dp)一开始不会,可耻的去膜题解,然后发现了诡异的转移。。看了很久没看懂,YY了很久,终于在一个晚上想明白了。。我是个傻逼。。。题意是给你高度为H的楼房,让你用n个电梯覆盖,覆盖是这样的,保持电梯的相对位置不变,不遗漏的覆盖完,问方案数。如H=8,N=4 12123434。然后令f(H,N)表是前两个是不同的电梯覆盖,g(H,N)表示是相同的电梯覆盖,然后观察序列,发现1-N序列连续的块大小是定值,然后就f(H,N)就枚举块的大小,有f(H,N) = sigma g(H/d,N/d) (d>1, d|N) 现在考虑g(H,N)的转移,有g(H,N) = f)H,H/N) 可以这样理解,着相当于将所有的1由1-H/N替代,由于前两个都是1,这样的方案对应一个前两个是不同的电梯覆盖的方案。这样就可以了。:-D

 

TCO'10 Wildcard Round 500pt

题意:给你一堆带符号的卡片包含(+,-,*),随机抽取成排列,求期望表达式的值

注意到每一个非乘号后面均是等价的,所以分开来算,只要把所有非乘号的卡片的和加起来再乘上每一段的期望。而每一段的期望等价于开头全是乘号的期望积,枚举连续的K个,简单统计即可。很拙,思考了很久。

 

SRM 498 DIV1   1000pt

题意:求从(0,0)走到(Tx,Ty)且步长不超过(Mx,My)且有一些bad走法(dx=dy且为10倍数)问方案数

没想出来,看题解的。容斥走了几步坏的,注意到步子是可以交换的,然后dp再组合数统计没了。。感觉很厉害

 

TCO'10 Semifinal 1    950pt

一开始想残了,然后YY了很久才搞出来。。比较恶心的dp.枚举再前后dp一遍即可

 

SRM 522 DIV1   1050pt

题意:给你一些y[i]代表点(i,y[i]),每一次可以删除以两个点为对角线矩形内的点,问最终点剩余的可能方案

一开始没想法,其实这题是很好想的。首先我们观察最终留下的状态,那么显然是左右端点以及ymax与ymin的点,唯一有变化的是与左右y坐标相同的一些点,简单dp即可。

 

SRM 521 DIV1 500pt

题意:给你一些点,可以选择边长在lown到highn之间选择正方形去覆盖,问可能的集合数

显然不会太多,然后枚举左上与右下,简单判即可

 

SRM 481 DIV1   500pt

题意:给你一些人的任务,同一个人有多个任务。求安排任务顺序,使得平均等待时间最小。只有一台机器,且在最优方案中等概率选择,问每个任务完成的期望

每个人的任务总是连在一起的,简单计算即可。

 

SRM 521 DIV1   1000pt

题意:一个烟囱是由4个1*2的砖垒成一层,问你垒N层的方案数(只有下面的堆玩才能堆上面的)

一开始想不出状态定义,感觉很复杂,后来开了一下脑洞,只要考虑放第i层第一个后前两层的状态,只有4种情况,转移矩阵系数挺烦的,暴力状压算即可。

 

SRM 520 DIV1    500pt

sb背包

 

SRM 520 DIV1   1000pt

题意:给你一些哪些人cha过人以每个人被cha的转态,询问cha不同的序列数。每个人仅cha一次,而且被cha以后不会去cha别人。

非常神。一开始没有什么想法,去膜题解。好巧妙!当你搞不清关系时,可以列表,转换成形象的图形。而且显然可以将人分类。先放既cha人又被cha的,再放其他人。dp+组合排列

 

SRM 519 DIV1    600pt

ac自动机+dp

 

SRM 519 DIV1    900pt

枚举2,3相互搞的数量,再剩下与5,7匹配即可。注意怎么开数组(vector)

 

SRM 518 DIV1   500pt

貌似随便写了个贪心过了

 

SRM 518 DIV1   1000pt

本来是fwt的,但不会,学习了简单易懂的分治乘,而且复杂度是NlogN的。

 

SRM 517 DIV1    600pt

题意:操作i可以是a[i]与a[i+1]交换,给你一个目标排列,问你用1-i-1的i-1个操作排列使1--i-1变成目标排列,问排列方案数

很考思维,注意到操作i之前左右的数值不会交换,令f[i][j]为将i--j搞成有序的方案数,那么枚举最后一个操作,就变成了两个子问题。关键是要发现dp子问题的性质。

 

SRM 517 DIV1    900pt

题意:给你一个字符board,每次可以染一行或一列。问你最小次数

首先这种问题一般方法是先枚举一下,再推出一些信息。可以证明肯定有一行或一列不用染(反正,如果都染,那么第一次的会被全部覆盖),然后就知道了一行或一列的染色,再看不合法的点肯定让另一维染,搞出拓扑图判断。注意如果行列颜色都一样就没有限制关系!!

 

SRM 516 DIV1    500pt

简单的贪心

 

SRM 515 DIV1    550pt

题意:给你一些人到达店买剑的时间,价钱以及概率,每个人最多买一把剑,问你最多买K把剑的最优期望

可以dp[mask][i][j]表示mask的到过店,有i把剑,时间为t,dp即可。我觉的最难的是他告诉你每个时间到达店的概率,这样没法dp,而我们能做到的dp是用p[i]表示到以及(1-p[i])表示不到的概率进行转移,所以要把概率转一下,这点非常非常关键!!

 

SRM 515 DIV1   1000pt

题意:给你N*M的棋盘,有一些障碍点,三种人分别有他们的起始位置,各部相同,等概率出现在对应的位置上,三种人到达同一点,求走最短路的期望,两种人数<=20(N,M<=50)

一开始感觉很困难,两种人显然是要枚举的,但第三种人感觉很难再N*M的复杂的内求出。看了题解之后,忽然感觉很简单,N*M的复杂度只能BFS一遍,那么就考虑一种构图方法,使得求出的第三种人的距离为三个人最短路的答案,那么就很简单了,先枚举前两个人,再枚举三个人的聚集地点,然后对于每种前两个人到达聚集点的距离建一个点,距离i向距离i+1连边,然后每个距离向合法的到达点连边,再跑一遍BFS即可。很巧妙,关键是要想到可以直接BFS最终的距离和。

 

SRM648 DIV1 850pt

题意:求N个点K个桥带标号的图的个数

好难,首先图可以分成一个一个联通块背包do,然后一个联通块可以将桥拆掉变成若干个双联通分量,由矩阵树定理可得:N个带标号的点S个联通块(大小为mi)加S-1条边使图联通的方案数为N^(S-2)*pi(ai)。然后就算N个点的双联通分量有几个,可以先算出所有的联通图数量,再减去1-N-1座桥的图的数量。

 

SRM 510 DIV1    500pt

题意:仅有4,7构成的数是lucky number,A从[a,b]中选出连续的L1个,B从A选出的中选出连续的L2个。A要最大化lucky number的数量,B要最小化lucky number的数量,问最终结果(a,b<=10^10)

一开始很乱,感觉直接贪心边界十分不好处理,情况也非常多。然后去看了题解,看了将B从x选起的结果用F(X)表示出来,立马就懂了,可以发现函数值是连续的,就可以分成一些段搞了。然后枚举答案,看是否存在L1长度连续的即可。关键思路是将复杂的东西具体化,暴力化,用函数表示出来,就很显然了。

 

SRM 510 DIV1    1000pt

题意:仅有4,7构成的数是lucky number,给你N(N<=1e16),问你有多少D是的ND进制下每一位是lucky number

首先方案不会太多,可以考虑枚举。但怎么枚呢?首先考虑假如有很多位那么D应很小,爆枚即可。当有2-3位时,看似很难枚,但由于数字只能是4,7构成,爆搜一下发现发难数都很少,check一下就可以了。关键是要先转化到位数很少的情况,再考虑爆枚。

 

SRM 658 DIV1    850pt

 二分图最大匹配,然后判一判即可

 

SRM 658 DIV1    650pt

题意:给你N个怪物(N<=20),每个怪的血值(<=60),每次attck可以选择三个,分别扣血1,3,9滴,问你最少几次

首先可以二分答案,然后呢,发现如果选完3,9,剩下的只能选一到满,令dp[o][k][l]表示搞到第i个人3,9用了j,k个的最少1个数。dp即可。关键在于发现1取到满即可的性质

 

TCO Round3 2A 1000pt

题意:问你A^B有多少种不同的数,1<=A<=1e9, 1<=B<=1e9

首先可以将每个A^X表示成(r^k)^X,其中r为不能表示成更小的指数幂形式,那么可以知道k<=30,故暴力枚举k,先考虑如何统计最大次幂为k的r有几个,可以考虑容斥,答案等于sigma(i,mu[i]*这段区间中能表示成i次幂的数的个数)。

好,然后考虑对一个r不同的方案数,那么可以转换成k*X的方案数。这个怎么算呢,首先观察到k很小,考虑分段,对于(i*X,(i+1)*X]这段的答案,显然只有i+1到k乘才会合法,而对于i能覆盖所有i的倍数覆盖的点,那么考虑容斥,只要考虑哪些不构成倍数关系的数即可,这样最多只有15个左右,就可以了。关键是要想到优化容斥,直接容斥是2^30次,而分段则可以优化很多。

1的情况要特殊考虑。

 

TCO Round3 2A 600pt

题意:一个Magic Matrix定义为所有行和列的和的最后一位相同。每个格子只能填0-9.问你在N(<=1)个格子已填的基础上,有多少种不同的方案。

首先,如果N很大,那么可以将空的一行和一列交换到最后,这样可以直接算出!!

如果N很小,暴力搞死消元。关键是要想到可以交换的性质。

 

SRM578 DIV1 1000pt

题意:给你N个节点的树(N<=50),让你割掉一些边形成若干个联通子树,选出两棵子树,使它们同构。问最大点数

好难!首先可以考虑对于两棵有根树该怎么办,可以递归算出两个儿子分别匹配的答案,然后最优匹配即可。

然后可以枚举一条边删掉,然后枚举两个联通快的根,统计答案取max

关键是想到对于两棵有根树该怎么做。可以递归得到儿子答案,在最优匹配合并。/(ㄒoㄒ)/~~

 

SRM578 DIV1 500pt

题意长度为N(<=300)的线段上每个点可能有fox,现在给你一些条件,形如[L,R]这段区间至多有两个fox。问方案数

首先观察N的范围,考虑N^3的dp。令dp[i][j]表示i,j上有为相邻fox的方案数。这道题关键是用到最多两个的性质,直接上两维状态表示即可。O(∩_∩)O

 

TCO13 Semifinal1 550pt

题意:给你一个DAG的拓扑序列,一个DAG序列生成的方式是等概率随机当前入度为0的集合中的一个点加到序列。问你这个DAG中有A->B这条边的概率是多少

可以从后往前dp,设dp[i][j]表示到第i个点,后面的点是不是入度为0(用j表示一个二进制)的概率。直接算即可。最后必须有这条边的概率与所有概率除一除即可 O(∩_∩)O

 

SRM 509 DIV1 1000pt

题意:给你一个凸多边形,以及内部的N个点,每个点分配周长的1/N,问你内部的点到分配的点的最大值的最小值是多少?

二分,然后怎么判,先枚举每条线段,与每个圆作交,求出每个交点,在对每一段建点,跑网络流看是否满流即可。判线段与圆的交,设交点为X+w*d,d为直线向量,这样比较方便。注意eps。关键是讲复杂的交法转换成每一条边与每一个圆的交,算计技巧以很重要。/(ㄒoㄒ)/~~

 

SRM 507 DIV1    500pt

题意:给你Ns个1*1*1的方块和Nb个L*L*L个方块,用体积最小的长方体装下这些方块,求最小体积(要求平行)

一开始不会做,后来抱着试试看的心态,写了L*L*x,发现过了4个点,然后就发现答案最大值最多加L*L-1,然后写了个爆枚体积,分解因数判断的。。

后来看了题解,发现傻逼了。。由于题目中给出体积小于int,故直接枚举最短边,次短边在算第三条边即可。。关键是想到题解很小,而且爆枚两个最小边的复杂度很小。。。^_^

 

 

Avatar_small
sure 说:
2017年2月06日 20:31

SRM 522 DIV1 1050pt 请教如何定义DP的状态。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter