国庆节还是没法好好休息呢…比赛,走亲访友,旅游…
今天的武汉网络赛
这里有官方的解题报告和标程数据
一上来…先一道道粗略的看下去…挑短的读一下…
然后就看到了1006这题…一看…阶乘和并对m取余…规模10^100…但是m只有1000000…
sky提醒了一下…大于m的部分全都没用了…因为肯定能被m整除…于是马上敲…马上交…AC…此时rank1了…虽然马上就有人两题了…
然后看到有人过1008文件路径判断的题目…以为是复杂的模拟…结果是很简单的判断…很快就过了
然后1001星际旅行也有人过…但是这题目…太晦涩了…一遍看下来没看懂
让answeror读…后来明白了…删除最少边使得图没有奇环…想不出来…
sky和answeror说了个奇妙的定理…一个图没有奇环当且仅当它是二分图…
那就简单了…才那么点顶点,直接2^n枚举一下左边,然后计算一下要删掉多少边,取个最小的…也AC了…
1010矩形切割…一开始没什么想法…然后answeror提醒了dp只要二维…于是敲之…wa了…
然后想到可能小矩形可以旋转,改了下…但是犯了个低级错误wa了一次后ac了…
1009打怪…计算几何预处理,二分+网络流…貌似有更好的方法…总之这题wa了好几次…
最后居然是在把eps改成0后ac了…这精度问题也太恶心了…
然后别的题就没做出来了…
因为有官方解题报告和标程…就没有下文了…
tags: HDU, acm author: ben1222 comments: No Comments
今天杭电上的比赛
HDOJ2009暑期集训公开赛（8）－非原创
题目来源是
The 33rd ACM International Collegiate Programming Contest Asia Beijing Regional Contest
即2008年北京赛区现场赛的题
当看到第一题时就感觉看到过…
一题题看下去时既视感越来越强烈…
看到C题感觉很水,直接敲了…但是还WA了一次…因为可以有回字形的
然后又把树状数组那题给敲了,不过还是WA了一次…没看清题…
然后sky想到是去年北京赛区现场赛的题…之前有做过…
于是我翻出那时的代码…把积分公式,婚礼,比例生成树给直接交了AC…
然后开始想其他的题目…
我在想龙卷风那题,他们在想A题…
我搞了个按周期一个个来,每段用三分求极值方法来搞…结果TLE了…
想想也是…如果以1的速度去走2*10^9那么多的距离…唉…
然后ssjia把A题搞掉了…
然后我想到…既然直接搞不行,就设个步长然后一点点减小吧…
WA了一次后AC了…
还剩三题…一个是博弈,一个是游行,一个是究级模拟…
ssjia慢慢搞模拟题…我和sky在想另外两题…
博弈那题写了个小数据想找规律…k=1,2,3,4时好不容易以为找到了规律了…结果k=5时这个规律居然不适用了…囧…
于是转向游行那题…记得上次做的时候直接dp,结果复杂度是O(n*m*m)级别…
n虽然才100,可是m有10000…铁定TLE…
我就想着怎么才能优化掉一个m…想啊想…最后还是没想出可行的方案…于是退而求其次…想着把m优化成logm…
结果想到了rmq…wa了几次后终于ac了…以O(n*m*logm)的复杂度…跑了1.4s才过…
简述:
A: 删边拆点网络流…据说如此…
B: 博弈,没做出来
C: 窗口,直接模拟
D: 龙卷风,三分法求极值,减小步长前进…
E: 比例生成树,枚举2^n种选取点的方式,固定点权然后以这些点做最小生成树
F: 游行,我是二维dp+rmq,应该有更好的方法
G: 婚礼,按中点排序后贪心
H: 乒乓,树状数组
I: 积分出水量关于水位的函数,然后二分
J: 模拟电梯?
下面是DFI的详述和部分代码
tags: HDU, acm author: ben1222 comments: 2 Comments
组队赛第三场,在杭电上做
Ecust 2009 ICPC Team Practice 3
题目是2006年西安赛区的现场赛
Asia Regional Contest 2006 Xi-An
uva的链接
这次题目难度就上去了…
44分钟才有第一个队伍提交…
这次只过了3题…火柴棍,睡觉,叠纸片
一开始看题…这次看题真一个郁闷…看一道没想法一道…
好容易读到一道看起来可以做的题…肚子痛了…上了个厕所回来…
看完题…睡觉那题…感觉和以前做过的一道美术馆喷泉的题目有点像…而且这次似乎还简单一点…
说是上课…学生们很困…睡b分钟会醒来a分钟,过了a分钟后会看看睡觉的人数是不是比醒着的人多,是的话就又睡b分钟,否则就一直醒着了…
题意貌似是说否则就再过a分钟后继续观察…不过发生这种情况的话不可能会有人又去睡觉的吧…
a和b都小于等于5分钟,且是整数
于是取所有(a+b)的最小公倍数c,那么只要模拟c*2次看有没有全醒就行了…
敲之…对面的人ac了这题…10分钟后我们也ac了这题…
这时已经快一小时了…
继续看题…sky和我说了最后一题…就是纸片覆盖那题…
4*4的区域用2*2的纸片覆盖,顶点只能在整数点上,按顺序放,给出最后从上往下看到的形态,问能否用6枚以内的纸片完成这种形状
我想了一下,很迷茫…sky和我说…预处理下,打个表,才9^6那么多状态…
我想也是…sky又说…火柴棍那题可以dp,我说要高精度太麻烦…于是先敲叠纸片…
先粗略的估算了下空间,觉得每个状态用5*9的字符串表示太浪费也太大了…
于是想了个压缩方案…每列压成1字节,总共压成9字节的字符串…然后用set来判断
敲完ac了…
然后让sky去敲火柴那题…我继续看别的题…
火柴这题是给你n个火柴,要你拼出最大的可以被m整除的数…sky用dp[用i个火柴][除m余数为j]=最大的数字
和ssjia讨论了一些题…但是仍没什么想法…
其中有题音阶的…有点后悔没仔细看题…
后来sky敲好了,不过程序速度有点慢…极限数据要数秒,时限是5秒…试着交了下tle了…
似乎比较高精度数字大小慢了点,因为是记录前驱,所以每次比较的时候就要把双方的高精度数值都搞出来然后比较…
我说…弄个double预判一下吧…如果double值接近就再用高精度判断一下
改之…然后发现一些数据先前的结果不对…但是现在的结果是对的…也没管,就交了…结果wa了…
想到先前的结果不对应该是高精度比较函数写错了…检查了下…最终发现问题所在…高位在前还是在后搞混了…
改之ac…
然后我去写箱子…无奈wa到结束…
简述:
A: 棍子…上上下下来来回回的感觉要考虑很多,没想法…
B: 火柴…dp
C: 宝箱…二分,计算几何?不确定,没过…
D: 生成填数字的谜题…呃…没什么想法…
E: 睡觉…最小公倍数,模拟
F: 精灵…三维计算几何?这题搞成2维的都挺难的…
G: 水流…网络流..吧?带上下界的有权的…
H: 音阶…仔细看题…角度是整数,所以枚举下应该可以…计算几何
I: 冰人…横版过关游戏…恶心的…搜索?
J: 叠纸片…预处理
下面这段是关于宝箱的那题,可以无视,因为这题最终还是没做出来…因此下面这段可能是错误的思路
tags: HDU, acm author: ben1222 comments: No Comments
2956 Robot Encryption
昨天比赛里的那题K
今天早上睡醒后突然灵感来了…把它给ac掉了…
题目没有看…是队友和我说的…
大约是类似logo语言的东西,不过控制的不是乌龟而是机器人,不是画图而是取字符…
指令有F向前一格,L左转,R右转,朝着墙壁F的话变成向后转
指令里有 (指令)次数 这样的循环嵌套结构,虽然次数最多9次,但是由于嵌套,每3个字符就能使循环次数增大9倍…虽然只有50字节的指令,却能达到9^16那么多指令
先给地图,地图是格状的,每格都有字符,然后是指令串数,然后是每个指令串
每条指令串执行完后输出机器人当前所在格子的字符
范围是地图50*50,指令串20个,每个指令串长度50
自然呢…想到的是先用naive的直接模拟搞
如果数据弱的话就能过
可惜出题人太邪恶了…不出所料TLE
很显然的意识到不把复杂度弄低只是做常数优化是不可行的
比赛的时候我想了另一个想法…
把地图延伸出去,像瓷砖一样,不过不是平移而是镜像翻转…有如卡诺图那样…
这样长宽增长一倍的地图就对称了,无论翻转多少次都是平移一样的效果
而且对于碰壁回头的设定也可以轻松的理解为继续往前走一格,只不过走到了镜像的那个区域里
然后每个循环就可以当作一次x方向走多少,y方向走多少,然后往哪个方向转多少度…这样每次循环就只要模拟一遍了
但是当写完之后调了样例才发现…我的想法错了…
因为每跨越一次边界…虽然F指令没问题…但是LR指令的效果会互换…
这样就没法搞了…于是比赛时也就放弃了继续做下去的念头…
在这个想法冒出来之前,比赛时还有另一个想法…
就是每个循环虽然照常运行,但是如果遇到之前走到过这个位置和这个方向的时候,直接用之前记录的运行了这个循环之后位置和朝向
不过当时想的是,一个循环最多9次,每次嵌套都要重新弄,地图大小远远大于9,记录下来几乎完全派不上用处…
于是也就没再多想了…
今天早上起来的时候突然想到…凭什么每次嵌套都要重新弄…
完全可以保留之前的数据,也就是当外层的循环多次执行了内层的循环,内层的循环的记录就可以很容易填满这个地图从而有所优化
也就是每串指令执行复杂度只和嵌套深度和地图大小有关,而和指令展开后的长度无关
于是加一个记录数组
rec[指令起始位置][机器人坐标和朝向]=这段指令运行后机器人所在坐标和朝向
其中指令起始位置仅限于每个左括号的右边一个位置以及指令串的第一个位置
不过很遗憾的,居然还是tle了…
在本机测试的时候虽然嵌套的很厉害的指令和一般的指令没有明显的时间上的差异
但是每串指令的延时都能感受到…
于是想到初始化数组是不是太慢了,因为每次我都memset整个50*50*50*4*3的数组
改进了一下,变成只对左括号右边一个位置以及第一个位置的长*宽*4*3的部分memset
于是ac了…速度还不错…排到了第一…
这是我第一次遇到改进memset量而从tle变成ac的题目…
下面是我的代码:
tags: HDU, acm author: ben1222 comments: 1 Comment
旅游归来…
去的是台湾…不过在游轮上待的时间比较多…
感觉还不错…
匆匆忙忙的又来做比赛了…这回是组队赛…
Practice For Ecust Team 1
题目来源是
HDOJ2009暑期集训公开赛（6）
交题可以在这里交
和sky,ssjia组队
没有大键盘…笔记本的键盘敲起来果然不爽啊…
一共出了8题…话说水题不少…
一上来看了A…读完题发现有歧义…不过不论哪种都是很水的…
和sky说了下…先用一种解释来写再说…
结果wa了…正要用另一种解释来写的时候…发现题目有一处写的很恶心…
上来说第一个数字是饼干盒的个数…还以为是接下来是那么多个饼干盒的描述…然后是单词的描述…
结果另一处写的却是每个case给定这个饼干盒的描述和单词的描述…
才发现原来一个饼干盒是一个case…很囧…
改好后过了
然后他们继续在看题…都还没看完…这时发现有人过题了…于是去看…数羊群的题…又一大水…
敲了交掉过掉…
然后又发现有人过题了…黑球白球的题…看了下…一时没什么思路…于是搁着…
sky和我说了下抢银行的那题…也说了dp的思路…于是写之…ac
然后又说了下扔飞镖的题目…简单的计算几何…写之…没过…
写的过程中他们似乎发现了一道不可思议的题目…
飞镖题wa了后他们和我说了这题不可思议的判两字符串是否相等的题…ac之…
然后我继续查飞镖题的错误…改了几次都没过…
于是转而看黑球白球那题…感觉会是有非常简单的公式或者方法的…
推了一下几个小数据…发现全是要么肯定是黑要么肯定是白…于是按照这个猜想去敲…ac了…汗…
然后继续看飞镖那题…动用了调试的功能…终于发现错误所在…有一处没写大括号…导致if的流程错掉了…囧…
改掉后就过了
接着看了那题卡车司机的…发现不难…于是自己就把它敲了…ac了…
然后ssjia和我说去搞机器人那题…估算了下模拟的话数据恶心点会tle…不过还是抱着试试看的心情敲了个模拟…结果果然tle了…
然后想啊想…想到了一个点子…改之…结果样例都没出…然后发现这个方法果然不正确…想不出来别的方法…
后来看到拼图那题有人过了…于是去搞这题…
20!比较吓人…推了几个小数据…然后发现了规模小一些的dfs方法…具体多大规模心里没底…于是说…打表吧…
此时ssjia在搞车票那题…未果…换我…
写之…调试了几次弄好了…验证了一下没爆int64…而且出结果的速度也很快…
于是就不打表了…直接在这上面做了…
这时候看了下时间…还剩10分钟…时间有点紧…不管三七二十一就敲了…
改啊改…终于把样例弄出来了…交之…wa…有点郁闷…
想继续改的时候想到了…0也是整数…之前只处理了1这个整数…改之…ac了…
呼…好险…最后4分钟里过的…
还有三题没做出来…车票,魔方,机器人…现在还没什么想法…
简述:
A: 饼干单词,水
B: 拼图,整数划分,组合数
C: 飞镖,计算几何
D: 卡车司机,概率,二分
E: 不可思议,水
F: 车票,不会
G: 数羊,bfs
H: 魔方,繁,bfs?
I: 黑球白球,想
J: 抢银行,背包
K: 机器人,模拟不行,其他方法还没想到
ABCDEGIJ详述和部分代码:
tags: HDU, acm author: ben1222 comments: No Comments
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