ECUST 1120 Easy Climb
HDU 2270 Easy Climb
昨天的比赛里那题
去NWERC 2008 的官方网站看了解题报告似的东西…今天照着写了一下…
题意大约是要翻山越岭…但是山路不好走…于是有人很神奇的提出把一部分的地面给抬高或降低…(这不是模拟城市吧…)
于是呢…这山路被分为了n段,每段有个高度hi,要求相邻两段之间的高度差不能超过d
起点和终点的高度不可改变
给一段提高或降低1的高度都要消耗1的费用,问使得山路满足这个条件消耗最少费用
范围是…n<=100,h,d<=10^9
很无语呢…
首先有一点是很神奇的…改造山路时,高度为hi+n*d的形式的值才是有意义的…
也就是约n^2个候选高度…
不过这是为什么呢…?…我不知道…都说很神奇了…(那为什么还写这篇…)
这样规模瞬间就很小了…来个dp[当前段][高度]=最小费用
不过直接搞的话复杂度就会有O(n^4)左右了…
可以发现对每段来说,其高度和费用之间画成图像的话是V字形的…\和/包含在这里
那么是不是每段的高度和最小费用直接也是类似V字形的单调性呢?
第一段肯定是V字形的
假设第k段是V字形的,那么转移后变成\_/形状,加上k+1段的费用V字形的之后,依然是V字形的
可以考察其”导数”,和的导数是导数的和,无论\_/还是V,导数始终是单调递增的(非严格),其和也是单调递增的,于是\_/和V叠加后依然是V字形,虽然可能有相邻两个是相等的情况发生,但是总体单调性不变…
于是就可以写个更快的转移函数了…复杂度O(n^3)
下面是我的代码:
tags: ECUST, HDU, acm author: ben1222 comments: 1 Comment
Ecust ACM 2009 Summer Practice Contest 8
链接不长期有效
题目来自NWERC 2008
The 2008 ACM Northwestern Europe Programming Contest
Utrecht University, The Netherlands
话说看到这套题的时候感觉好像做过的说…
记不起在哪里做的了…似乎手头也没当时的代码…
这次一共写着11题…但是G是not available,加上3题需要spj的…还剩7题…
做出来6题…
简述:
A: 预处理,排序
B: 强连通分量缩点,添加最少边变成强连通图
C: 最大二分匹配
D: 需要spj,没看
E: 没想出来,貌似是dp
F: 离散化,bfs
G: 不存在的题目
H: 构造
I: 需要spj,没看
J: 乱搞
K: 需要spj,没看
ABCFHJ的详述和部分代码:
tags: ECUST, acm author: ben1222 comments: No Comments
Ecust ACM 2009 Summer Practice Contest 7
链接不长期有效
来源是CTU Open Contest 2008
这次有2题需要spj…唉…
今天待在家里做…怎料家里的网络抽了…一上午都上不去…
以前是每次断个几秒钟…现在一断就是几小时…汗…
是不是线路老化了…
连电话都杂音无数…
后来想起来可以用手机当调制解调器…虽然慢了点…好歹也有3kb/s的速度…
于是晚了近2小时才开始做题…
这回题目描述…有点头大…
最后出了4题…
题目一难果然就无力了…底气不足…
追加2题
简述:
A: 伪随机数生成器预知接下来会抽到什么牌以定制策略使得分最大,没仔细想,dp?
B: 模拟银行业务…
C: B的输出来生成输入,需要spj,没做
D: 两段句子组成单词数最少的两段都是它的子串的字典序最小的句子,没仔细想,dp?
E: 模拟股市买卖
F: 砍掉价值最少的树去做篱笆,枚举+凸包周长
G: 3个连续k个点覆盖2k+1的轮盘,可以重叠,求最少消费,一开始以为是滑动窗口,后来发现错了…比赛时没做出来…但是这个方法可以帮助解这题,把盘面切成3部分考虑
H: 找一个顺序分配AB两者钱,使得任意时刻两者钱数相差最大值最小,比赛时没想法,其实是很简单的排序贪心
I: 多少种插入顺序使得与给定插入顺序所产生的二叉搜索树相同,组合数+高精度
BEFGHI详述和部分代码:
tags: ECUST, acm author: ben1222 comments: No Comments
Ecust ACM 2009 Summer Practice Contest 6
链接不长期有效
这次的题是去年亚洲区域赛Aizu的题
区域赛的题拿来做个人赛实在…
而且给的时限也比较低…有些题要跑那么快还是比较难的…
而且又有spj的问题…难得简单的AB却有精度问题需要spj…
可以跑去uva/tju/hdu交
这次不行了…一共10题…做出来4题…赛后追加一题
这题目真是个个都很长啊…
简述:
A: 模拟
B: dp,数学期望
C: 模拟…
D: 暂时没想法…
E: 三维计算几何
F: bfs
G: dp,优化优化再优化…
H: 没看题…
I: 公共多项式因子,没仔细想…
J: 没写…估计是枚举判断…
ABCFG详述和部分代码:
tags: ECUST, acm author: ben1222 comments: No Comments
今天拉肚子了…所以呆在了家里…
Ecust ACM 2009 Summer Practice Contest 5
链接不长期有效
似乎依然是TJU的题目…
一共10题…
做的比昨天还爽…做满了5小时…不过居然还是被我全切了…
等regional时候rp不够了就悲剧了…
简述:
A: 计算几何,两凸多边形间最短距离…规模小O(n^2)就能过了
B: 字符串,统计字母出现次数就行了
C: 进制转换,因为要求取余输出,瞬间变成了大水题
D: 用了O(n^2)的方法…不过貌似有更快的方法…?
E: 乱搞
F: O(n)的扫一遍,主要是复杂度计算很迷惑人…很容易以为是O(n^2)的了…
G: 预处理一下,O(1)回答,注意输入数据有负数
H: 在kmp基础上做一些奇怪的事情…统计用普通方法要比较多少次
I: dp,bfs
J: 字符串,要删字符,我偏不…我就要选…从前到后,从小到大,判断是否可行
详述和部分代码:
tags: ECUST, acm author: ben1222 comments: No Comments
今天的个人赛,出现了一个路人…最后据说是lhh?
Ecust ACM 2009 Summer Practice Contest 4
链接不长期有效
似乎还是TJU的…题目中出现了roba…
一共9题
这次的题做的比较爽…
不过居然3.5小时又被我切完了…
最近RP爆发的厉害啊…
简述:
A: 第k近城市,dijkstra+heap,或者floyd+sort
B: 转移矩阵+二分幂
C: 递归表达式计算或模拟人工计算
D: 模拟
E: dijkstra+heap+预处理
F: 离散化或暴力
G: 预处理+二分每段和阈值的交点(似乎解方程算交点也一样)
H: 二分答案+dp判断可行性
I: 数学期望+dp
详述和部分代码:
tags: ECUST, acm author: ben1222 comments: No Comments