除草

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

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

(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的状态。

Avatar_small
residential cleaning 说:
2022年4月21日 23:19

Should you be trying to identify a maid throughout Dubai who concentrates on kitchen cleanup then we has to be your ultimate option. All of our own housemaids are generally kitchen cleanup specialists. They will manage every instant detail as part of your kitchen. Beginning from scrubbing your floors and counter surfaces and taking away the sauces and dirt through the kitchen partitions, maids may help you. They will likely clean your appliances along with ensure to take care of the hygiene a higher level your home.

Avatar_small
PSPCL Bill Receipt 说:
2022年8月07日 20:10

The Government of Punjab in coordination with their State electricity department created the PSPCL organization. It is a Punjab state power corporation limited. It is solely responsible for management and supply of power across the state. Through this Government has unified the supply chain of power to provide uninterrupted electricity services to consumers. PSPCL Bill Receipt At the same time has created a portal for citizens to pay for all their PSPCL electricity bills online. If you’ve recently paid your electricity bill for Punjab through the PSPCL portal or if it for few years. Then you can follow this process that will help you understand how you can get your PSPCL bill history for every year bill payments.

Avatar_small
AP SSC Gk Question P 说:
2022年9月10日 23:36

General Knowlorge is most important subject to all Class 10 students studying in English Medium, AP SSC Gk Question Paper Telugu Medium & Urdu Medium of the State Board. So every student who is studying in the state Government & Private Schools can download the AP 10th GK Model Paper 2023 Pdf with answer solutions designed and suggested by subject experts. General Knowlorge is most important subject to all Class 10 students studying in English Medium.


登录 *


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