TopCoder SRM 661 (Div. 2) 总结

早上涨到蓝名下午就在模拟赛垫底了。。这人品守恒

唔。。这次div2打得还算可以吧,房间rank2(很不理解第二题dfs为什么没人写。。怕麻烦吗),950的题一直在推公式后来才发现可以暴力DP。。不过发现的时候已经到Challenge阶段了。

涨到蓝名,下次就得打div1了。。好虚啊,div1的题都不会做怎么办T T

250:

题目大意:给出一个方阵,o代表沙子,x代表障碍物,"."代表空地。如果沙子下面是空地就会往下掉,障碍物不动。问最后是什么样子的。

模拟。。

500:
题目大意:有两行点,初始每行第i个点和第i+1个点之间有双向边,带权值(最后一个点没有向后面的连边)。然后你需要添加k个垂直的双向边(即连接第一行的第i个点和第二行的第i个点),这些边权值都是0,使得所有点对中最短路最长的路径长度最小。返回这个值。

n,k<=11

嗯。。dfs枚举在哪加边,floyd更新答案

950:

有n个点,初始没有边。要用k种颜色染(不一定全部用到)。对于每个点i,可以选择一个j(j<i且i和j颜色不同),从i到j连一条有向边,也可以不选。问有多少种不同的图。

n<=100 k<=3

由于数据范围比较小,可以暴力dp。对于k=3的情况,dp[n][a][b]表示前n个点有a个颜色为1的点,b个颜色为2的点,n-a-b个颜色为3的点的方案数。k=2类似。定义状态之后转移就很好想了(详见代码)

然后敲完暴力dp交上去就可以A了。

但是!这题输入只有两个数,这启发我们寻找是否有规律。

经过打表发现确实是有规律的。。k=2的时候,答案=(n+1)!,k=3的时候,答案=1*3*5*7*...*(2*n+1)

然后这样写个程序交上去就跑的飞起了

由于懒。。没有写第二种解法的代码。。应该没有人不会写吧

 

发表评论

电子邮件地址不会被公开。

*