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

ydc的博客

 
 
 

日志

 
 

codeforces 215 div1  

2013-12-03 20:20:44|  分类: codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
跑去打CF
发现A题没看懂…………
A题卡了很久很久
于是做B题,过了pretest
去看C题
翱犇说D题是个傻逼题
去看D题
发现不会做
这时已经很晚了
卡扎菲说C题是个傻逼题
于是去想C题
发现自己竟然会做题
很开心的在1:50多交了C
于是B题fst了
很happy的掉rating了
智商被完全压制
以上

A:div1的A都不会……我果然是弱
B:随便搞搞就行了
C:容易发现这长得很像欧拉回路……那么如何处理重复走一条边呢?就看作重边就行了。题目转化为增加最少的边让它变成欧拉回路
然后是D和E
都不会做T_T
所以被lyy嘲讽了……
嘛……人家说E题是个傻逼题
可惜我连傻逼题都不会做呢

D:
ydc思路:
转化模型:你有n个集合,每个集合有若干个区间,现在要你选一些集合,集合并的区间覆盖某个区间
ydc做法:
不会做……
正解思路:
转化模型:你有n个集合,每个集合有若干点,对于区间[i,i+d-1]必须有个点被你选的集合选中
正解做法:
这样想就可做了。我们扫过去,可以得到对于任意区间[i,i+d-1]里,有哪些集合包含了里面至少一个数,假设状态为S,显然~S即~S的子集是不合法的。最后找到最大的不合法状态,就得到最小的合法状态了

E:
ydc只会做n>m的怎么破……

n>m特判一下输出0
否则,F[i][j][k]表示我考虑到数字i,已经有j个区间开始了,现在还有k个区间还没结束
这样就能转移了,分四种情况
一、当前弄一个新区间
二、当前弄一个新区间,与此同时结束一个
三、没发生任何事情
四、结束一个区间

情况三和情况四当i=x时你不能转移
用滚动数组优化
时间复杂度O(mn^2),空间O(n)

最后给大家讲个笑话:
ydc想了这样一个暴力dp做法
F[i][j][k]表示选了第i个区间[j,k]
时间复杂度O(nm^2),空间复杂度O(m)
咦……n>m不是输出0就行了么

真好笑
  评论这张
 
阅读(232)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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