2011topcoder_srm450-500_500and1000

2016.05.10 00:00 Tue | 186次阅读 | 旧日oi | 固定链接 | 源码

进度:9.5

SRM450

500

1000 最短路+思路

如果k特别大,那么最后一定是重复的走一个环,于是我们先处理出从1号点到每一个点的最短路经长度。
先把每个点拆成两个,代表向左走的和向右走的,点的标号直接设为i和i+n就行了。然后我们算出以每个点开头和结尾的权值最大的环。
然后考虑用最短路算法求出1号点到别的点的最短路,对于两个点u,v,如果u不能直接到达v,那么就需要在u开头的权值最大的环上走很多次,直到权值积累到大于u到v之间的距离,然后走过去就可以了。
求出这个之后答案也就好更新了还是利用刚才求出的每个点的最大环就可以了。
实现起来好麻烦啊……

SRM451

500 dp

先把点按y从小到大排序。
令f[i][j]表示前i个,选了j个时的最小步数.
$f[i][j]=min(f[k][j-1]+calc(f[k][j-1],k,i))$
后面这个东西只要找到最小的k满足(k-y+1)+...+k大于x就行了。
x,y是两个点的横纵坐标之差。

1000 状压dp

数据范围不大,可以考虑逐格递推的状压dp(类似插头dp)。
我们用把每个形状的右下角来代表这个形状。
假设当前的决策点是(i,j),那么f[i][j]只会跟(i,j-1),(i,j-2),(i,j-3),(i-1,j-2),(i-1,j-1),(i-1,j),(i-1,j+1)这7个点有关系,我们把这7个点的状态取出来,然后判断每一种形状能否放在(i,j)中就可以了。
一些细节就是判断无解,j=1时要处理一下上一层的状态什么的。存储状态可以用hash表,hash的模数要大一点,10^6左右吧。

SRM452

500 观察性质

观察到不能形成IOI的串只有所有的I的位置形成了公差为奇数的等差数列。然后暴力统计就行了。

1000 构造+dp

对于一个上升的数,我们可以把它表示成不超过10个形如1,11,111,...,111....1111这样的数。
这种数最多p个就会对模p出现循环节,于是我们可以暴力找出循环节(注意每次不一定循环回1),然后统计出模p等于x的数有多少种。
然后令f[i][j][k]表示用模p等于0...i-1的数,用了j个,现在模p等于k的方案数,然后枚举这组用了多少个即可。
注意最高位必须用一个。

SRM453

500 模拟

首先算出最多能有多少平局,然后每次找能平局数最多的人减掉最少数量的平局使得剩的数是w的倍数就可以了,其实这题可以做到很低的复杂度,但是TC的范围真是太小了,怎么搞都行了。。。

1000 DP

研究了好久的贪心,感觉好复杂……压根没往dp上想,翻了下题解,好像是个挺简单的dp,然而自己想不到,还是太弱……
第一个人一定是要赢的,最后的分数是确定的,我们要做的就是对每个人决策,使得超过第一个人的分数的人数最少。
令dp[i][j][k]表示前i个人已经决策,现在胜负场差是j,有多少个平局没被匹配,转移的话枚举这个人的状态就可以了。注意枚举第i个人的平局数时不一定都要用来匹配原来的,也可以作为新的未匹配平局出现。
复杂度大概是n^2*200倍的常数吧。

SRM453.5

500 暴力+结论

能用的东西不多,也就1000多个,直接dp一遍结束。点数>=3的平面图最多有3n-6条边。

1000 搜索(打表)

把4和7的所有数搞出来,然后把他们之间的最小公倍数也都搞出来,这样的数也就10000个左右,搜索在1秒之内也轻松出解。

SRM454

500 dp

f[i][j][k]表示前i位数,移动了j位,现在差k个数使得1的个数和原来一样的方案数。
转移随便搞啦
TC好多dp啊,还好在第二题的都比较简单……

1000 公式

假设N在(x,y),那么(i,j)位置被算了(x+1-i)(y+1-j)次,拆开分别维护一下每一项就好了。复杂度是根号级别的。

SRM455

550 递推

考虑大小为i的三角形的贡献(贡献指每条边都在边界上的六边形个数),再乘上这样的三角形的个数就是答案。
大小为i的三角形的贡献:设顶部的边是长度为j的,如果(i-j)*2<=i,贡献是(i-j-1)^2,否则是

900 状压dp

挺水的,把大树和小树能匹配的方案记录在根节点上,然后枚举根节点和小树,压每条边的状态就行了。

SRM456

450 二分答案

傻题一个。

1050 函数方程+二分图最小权匹配

两个推导结论:f[i]+2c=f[i+2c];f[i]=t,f[j]=t+c.则i+j=2t+1.
于是我们对所有数按模2c的值分组,观察可以发现,能配对的两个数一定奇偶性不同,于是只要求出来两个数配对的最小花费,然后跑个费用流就行了。

SRM457

500 容斥

sb题一个,中间的数是啥无所谓,边上的数有2n-2种方案。随便容斥一下合法的就行。

1000 费用流+小技巧

每个棋子可以单独考虑,所以一个棋子从(x,y)到(p,q)的花费一定是abs(x-p)+abs(y-q),根据这个我们就可以费用流跑最小步数了。
然后考虑怎么保证字典序。我们从小到大枚举每个位置,如果这个点跑出来就是'.',那么不管,并删掉这个点。如果这个点是'C',看能否找到一条替代的路径,如果能找到,那这个点还是'.',并删掉这个点,否则这个点是'C'

SRM498

1000 dp

如果不考虑那个限制,那么两维可以单独dp。
然后考虑限制,令f[i][j]表示走了i步,到j,每步只能走被禁止的步数的方案数。然后容斥搞一下就行了。