算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
先说一个事,我成都赛区基本彻底GG了。磊哥因为考试不能去,损失一大站力。
题目连接
http://acm.hdu.edu.cn/search.php?field=problem&key=2012%20Asia%20Tianjin%20Regional%20Contest&source=1&searchmode=source

然后我在今天19:00开始刷了一下天津赛区的题。到现在23:44分做出了5道。还被F怒坑了。


A题  大模拟,看了就不想写。。。。

B题
枚举一个数的所有因子
B

C题
貌似可以直接递推求解的,但是不愿意多想了就直接写了一个SPFA,还为末尾的情况纠结了好久,其实直接加哨兵就可以的。
C

E题
我一开始看的这题,感觉卧槽这题可做么。多哈密顿路点数还是128个点的欧式图。。。。。
后来发现并非每个加油站只能去一次。。。。

因为在点i建立加油站的费用是2^i,所以即使前i-1个都建立加油站,也比在i点建立加油站合适。。。。
于是可以从后向前枚举是否建立加油站。如果前i-1个节点都建立加油站可以保证合法,那么i一定不建立,否则一定建立。

然后问题就是在给出哪些点建立加油站之后,如何判断方案可行了。。。
首先所有的加油站必须联通。
其次对于所有非加油站,最好的情况是找一个最近的加油站作为自己的“补充”。
E

F
一看到“所有的子串”,就一定会想到后缀自动机来搞了。
连接所有的串建立后缀自动机。不同的串用特殊符连接。

然后对这个DAG进行DP。转移非常明显。不要走特殊符的边和第一个零边。
拓扑排序的时候我到了深搜然后hdoj就爆栈了。。。。。。。。。
F

H
上过高中的都会吧。。。
H

K splay可以做,但是连敲5个小时体力不支了。。。以后还要多练习啊
posted on 2012-10-30 00:07 西月弦 阅读(854) 评论(8)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: 2012天津赛区原创题解
2012-10-30 11:43 | silver__bullet
我擦...磊哥不去你咋比啊还...这么跪了也太尼玛坑爹了吧...  回复  更多评论
  
# re: 2012天津赛区原创题解
2012-10-30 12:19 | 西月弦
@silver__bullet
所以管你要电话本来想让你代替磊哥的。。。  回复  更多评论
  
# re: 2012天津赛区原创题解
2012-10-30 12:32 | silver__bullet
@西月弦
这。。。弱菜啊。。拖后腿。。明年这个时候应该能有战斗力。。囧  回复  更多评论
  
# re: 2012天津赛区原创题解
2012-10-30 13:58 | 西月弦
@silver__bullet
集求战斗力组队出线。。。  回复  更多评论
  
# re: 2012天津赛区原创题解
2012-10-30 16:26 | silver__bullet
@西月弦
...飞哥明年还准备搞不  回复  更多评论
  
# re: 2012天津赛区原创题解
2012-10-31 15:03 | 西月弦
@silver__bullet
必须搞啊。。。 在搜寻队友呢,正好你TC也黄了。。。  回复  更多评论
  
# re: 2012天津赛区原创题解
2012-11-01 09:08 | silver__bullet
@西月弦
so nice~~争取明年能有绝对实力给你打辅助吧
ps.这把tc黄得太偶然了。。。  回复  更多评论
  
# re: 2012天津赛区原创题解
2012-11-01 20:08 | 西月弦
@silver__bullet
恩,加油吧  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理