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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

2014-4-8 杂记&骗分记录  

2014-04-08 19:09:31|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

今天又测试了- -||

(为啥这么多测试啊喂

高二神犇找的题……然后发现全都不会QAQ,一道都不会啊

第一题以为是最小路径覆盖,然后发现最小路径覆盖都不会了……翻书,发现完全不是……

第二题一眼就看出来DP,但是完全没有思路,集合什么的最讨厌了。。。

第三题是之前清北讲过的,结果还是完全忘记怎么做- -、

怎么办啊怎么办……

就这样蛋疼了好长时间,坐在前面的神犇都早秒了第一题在搞第二题

……最后下定决心骗分

于是第一题就写了个贪心,有点像网络流的感觉?

第二三题直接暴力。。。

结果……又RP爆了……(高一)其他人似乎都第一题搞错题意了,所以都是<=50

然后第二题第三题都是暴力。

然后我一脸蛋疼地交上程序……

第一题90???

骗分骗了90???

有点胡扯啊……


先来说一下第一题题意:

     有一个有向无环图,你可以从任意一个点开始走,问至少走多少次可以走遍所有的路。两个点之间可以有多条路,点数N<=100(据说是BZOJ上的一道权限题)

我骗分的做法:

     让一个点S连到所有入度为0的点上,所有出度为0点连到点T上。然后每次做一遍DAG上的DP求一条最长路,然后把这条路的每条边长置零。(注意边长为0的边之后照样能走)一直这么做直到最长路长度为0,次数就是答案。然后注意一下两点之间的多边。。

发下数据之后我把DP那里的更新条件“>”变成了“>=”,于是多WA了一个点(当然还T了好几个),可见这个贪心是错的……

不过为什么是错的我到现在也不清楚,错的那个样例数据量巨大

如图:

2014-4-8 杂记骗分记录 - 时光机 - 时空裂缝

 这图在本地还能凑活着看的说……传上来怎么就成了一坨翔了……

我也不可能照着研究- -||

如果有神犇能举出反例请告诉蒟蒻,感激不尽QAQ

然后标解是费用流(最小路径覆盖行不行不是很清楚)好像要建一个特别复杂的图……题解至今不明白Orz

第二题(HNOI集合选数)标解是建一个奇怪的图之后状压DP,看了题解才发现这个题清北也讲过(都忘了好惭愧 0///0 )

Orz Wangxz神犇和我的思路一样,只是被误导理解错题才挂了……

Orz faebdc神犇最后想到了标解但是来不及了,于是建图之后只好写了爆搜。真心不知道这题标解怎么想出来的,然后蒟蒻我对着标程还写了一下午QAQ

Orz我现在只会骗分了……省选前RP都用完到时候爆0怎么办……Orz Orz 神犇们不要黑我其实我才是最弱的……


距离省选还有2
  评论这张
 
阅读(44)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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