注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

codeforces 206 div1 D & codeforces 212 div2  

2013-11-19 21:42:57|  分类: codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
先给大家讲一个故事……
某年某月某日,还未看题的ydc在delayyy大神的博客里发现了翻译:codeforces 206 div1 D  codeforces 212 div2 - ydc - ydc的博客
于是ydc就没去看英文题了 ……

不会做的ydc开始看题解
“各个三角形互不包含……显然”
“三角形最深不超过800,显然”
然后就看不懂了……

最后问lyy,前面听得懂,但是诡异的是每次讲到dp方程的时候就各种觉得不科学
最后看lyy代码……盯着几行代码老半天,忽然惨呼一声:“尼玛子三角形要到最底层啊啊啊啊!!”

于是这道题目就可做了
由于互不包含,从底层开始,那么纵坐标大于某个值的一定直接3的代价覆盖,其他的三角形,以某个点为直角顶点(我把三角形看成了一个直角三角形),他只会弄一个三角形出来(因为互不包含),而且他往右上扩展不到的点,一定没有别的三角形扩展的到(还是因为互不包含)
预处理一些东西,比如某列的前缀和,当前列下i行i列的等腰直角三角形有几个关键点,设F[i]表示到第i行的最小花费,接下来就可以通过枚举i这个点弄一个长度为j的三角形,枚举1<=k<=j,通过F[i-1]与k*(k+1)/2+2加上除了i~i+k-1这一个矩形中去掉长度为k的等腰三角形的剩下的点的个数*3来转移
时间复杂度应该比delayyy和“苏明雪”的高……看起来是三重循环,但是加上一些j*(j+1)/2+2<=长度为j的等腰三角形内黑点个数*3之类的要求,经过均摊分析一下应该是不会TLE的

然后是codeforces 212 div2的题……虽然是div2,但也不至于这么水吧

A题容易发现第二个棋根本不需要动……然后就变成判断一个象能否吃掉另一个象了
B题就是判断有没有三个连续整数……以及特判
C题的话我一直不知道插入排序是那么写的……反正那个伪代码和冒泡一样就是逆序对个数,由于n不大,预处理之后只要枚举(i,j)更新答案即可
D题是个大水贪心……对每个联通块弄好之后,肯定是先通过合并最小联通块弄到那么多个,然后随便弄两个点不断输出就行了
E题的话我一开始看想到了bzoj的网络扩容……打算二分答案再用那题做法的。由于觉得这种做法“不够优美”,于是嘴巴上AK了之后就瞟了一下题解看看,他说每次最小费用最大流超过限制就结束程序就行了……既然这么说就这么写吧,暑假见过这种方法的,似乎有个叫什么奇葩的“连续最短路定理”之类的东西做保证,所以那种K路径覆盖的题可以连-inf的边边权为正就结束。然后就套用这个东西A了
  评论这张
 
阅读(235)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017