wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
TCO2013作死记
? 训练计划 ?
2017-03-19 20:48:45
514
0
0
wuvin
? 训练计划 ?
听说TCO2013的题目有趣，于是就跑去做TCO了 由于TC太慢，所以来悠闲写题解了。 觉得自己比较弱，就做TC0500的题。1000的题留坑吧。 发现TC特别良心，常数无论多大都可以过。 比如一道题只有$n^2$和$n$的复杂度，那么$n$一般会是20000,刚好卡掉$n^2$。 ##TCO2013 1A 250 暴力即可 500 调整思想，一定会经过某个右端点，否则肯定缩小X。暴力验证即可，记着剪枝。 1000 同TJOI2013 循环格 ##TCO2013 1B 500 暴力枚举 暴力枚举行上的操作，然后统计剩余的X需要多少次列上的操作来完成。 ##TCO2013 1C 500 无脑二分，暴力验证。 ##TCO2013 2A 600 好神啊，不会。参见jiry_2大爷的博客。 ##TCO2013 2B 500 好难啊，做不来。 跑去看题解——记忆化搜索！什么，dp[i][j]表示i,j两个城市至多走多少步才会不同。出现循环就-1. ##TCO2013 2C 550 好难写。。。首先naive的N^4是过不了的。于是还要分析，发现有大量公共部分，预处理公共部分，暴力处理特殊部分，然后合并。复杂度O(N^3)。大概也就写了两个多小时吧 ##TCO2013 3A 550 想了一会，不会。去看题解，MD对偶图！我怎么就没有想到！一开始以为是轮廓线dp，发现复杂度不对。然后又分析出答案最大为6，然而并不能暴力枚举。没有用上在边界的条件，所以分析不出来。想到了最小割，但没有想到对偶图。我服！ ##TCO2013 3B 450 首先判断无解，这个容易。。然后发现实际上是在匹配每对值。等价于在一个有向图中每条边用一次，最多可以生成多少个环。（感觉可做，但是不会。）只好去看jiry_2大爷的状压集合DP的做法。 ##10.14 update 昨天打了第一次SRM，极限剩余10s提交900pts。发现竟然成了Room1，div2 rk6(看来打TC的人太少了)[拿衣服\(^o^)/]。结果250pts的没有初始化数组FST了（不过还是rk6）。于是一场上黄，比CF什么的涨得快多了。 就先结到这吧，后面的题连300都坐不起了。。。sad
上一篇:
训练计划1
下一篇:
BSGS
0
赞
514 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册