pe Problem 233
明天要去旅游了呢…一个星期…
Project Euler第233题
Lattice points on a circle
f(N)表示过(0,0),(0,N),(N,0),(N,N)四个点的圆经过多少个整数坐标点
求f(N)=420的所有N<=10^11的和
下面是我的解题过程:
oj hdu 2770 Easy Climb
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)
下面是我的代码:
contest Ecust ACM 2009 Summer Practice Contest 8
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的详述和部分代码:
contest Ecust ACM 2009 Summer Practice Contest 7
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详述和部分代码:
contest Ecust ACM 2009 Summer Practice Contest 6
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详述和部分代码:
pe vol12 56~60
Project Euler
最近不怎么切PE了呢…
56:C++
57:C++/人
58:C++
59:VB6,人脑
60:C++
下面是详细内容:
RSS订阅