AHOI2013 Round1 题解&&总结

Posted on 2013-05-18 17:38 Mato_No1 阅读(949) 评论(4)  编辑 收藏 引用 所属分类: AHOI
(首先声明一下,今年AHOI R1的题==JSOI R3 Day1的题)
【题解】
sport:
首先很容易证明,最优方案必然是左边都是-,右边都是+(从样例也可以看出来囧)……
因此问题转化为了第几次开始+,可以使得开始+的时候,目标元素的位置最左……
注意到排队的过程实际上是个冒泡……因此本题的关键在于发掘出冒泡的性质囧……
设最初的序列为A[0..N-1],目标元素为A[pos]。设S[0]为排在A[pos]之左的比A[pos]大的元素的个数(因为一开始排在A[pos]之左的且<=A[pos]的元素,不管肿么搞都一直在目标元素之左,不管它们了囧……),然后,考察所有一开始排在A[pos]之右的,比A[pos]小(注意是<A[pos],不是<=)的所有元素,设它们之间的间隔分别为S[1]、S[2]、S[3]……(具体见图,其中S[1]为A[pos]和第一个比A[pos]小的元素之间的间隔)

然后来审视一下整个冒泡的过程。一开始,必然是将目标元素左边的一个比目标元素大的元素移到右边去,在目标元素右边它可能会停下来,但紧接着必然是一个值更大的元素继续往右移,最终的效果等价于将目标元素左边的一个比目标元素大的元素“移出去”了(即移到了最右边的比目标元素小的元素的右边),也就是S[0]减了1,而S[1]、S[2]……都没变,这个过程显然只能持续S[0]次,目标元素左边比它大的元素就全部移出去,此时目标元素到达了它“可能到达”的最左位置。
接着,目标元素和右边第一个比它小的元素(即图中的A[i1])之间的,比目标元素大的那些元素将被依次的移出去,也就是S[1]不断减1,而S[2]及后面的都没变。这一过程会持续S[1]次,目标元素就和A[i1]靠在一起了(注意,在这个过程中,目标元素的位置是不会变的)。
如果此时继续冒泡,则目标元素就会和A[i1]交换,右移一个位置,并且就从这次冒泡开始,S[2]不断减1,减到0为止,接着目标元素和A[i2]交换,右移一个位置,S[3]不断减1……直到最后一个S[]值也减到0后,目标元素到达它的目标位置。
也就是,设“第i阶段”为S[i]值减少的这个阶段,则在第0阶段,目标元素会不断左移,显然不用+,第1阶段,目标元素不动,也不用+,但从第2阶段开始,在每阶段的第一次冒泡时,目标元素都会向右移一个位置。因此,开始+的时候,必然是第x(x>=2)阶段的开始的那次。由于最多只能+ K次,因此可能的最左位置就是满足N-1-∑(0<=j<x)S[j] <=K的最小的x值减2,加上一开始就在目标元素之左的,且值不大于目标元素的元素个数(它们必然在目标元素之左)。注意特殊情况:x<2(此时当成x=2处理),或者x不存在(全是-)。
因此,本题就是预处理求出所有S之后,扫一遍得出最小的x值就行了,O(N)。
当然,二分答案+暴力判断可以得50,有神犇说二分答案之后可以在O(N)时间内判断,从而O(NlogN)解决,我太弱了,完全搞不懂囧……(Orz!!)

mole:
首先,一个很重要的事实就是,“整个过程中左手所在的位置严格小于右手”其实是一个废条件!!因为如果左右手交叉了,必然是左手试图去打靠右的一个,而右手试图去打靠左的一个,此时,让它们交换,则两只手移动的距离都变小,方案仍然合法,且更优(我太弱了,当时就是在这里想抽了很久,以至于木有做这题……后来才知道这题很水……真悲剧!!!)
接下来就变成了一个全局统筹的问题,可以用网络流解决:每个地鼠i拆成两个点:入点i'、出点i'',中间连一条容量为1(表示只能打一次),费用为它的得分的边,两只手开始的位置也当成有地鼠,只不过得分为0而已。如果某只手在打完第i个地鼠后能接着去打第j个地鼠,就连边<i'', j'>,容量1,费用0。s往表示两只手开始的两个点的入点连一条容量为1,费用为0的边,每个出点往T连一条容量为1,费用为0的边。求这个图的最大费用最大流即可。
当然,用O(N3)的DP也可以得到至少60分,如果卡的好的话可能有80以上囧……

bus:
裸的数据结构题,用一坨Splay Tree维护即可,唯一要注意的就是链可以翻转,因此要rev标记……
还是不会搞的可以去做ZJOI2012 Day2的某题……
这题在数据结构题中还是比较好写的……值得吐槽的是它的对拍很难写……本沙茶写正解用了50min,写对拍用了75min……
———————————————————————————————————————————————————
【总结 && 一些闲扯】
(1)(Orz @sunzhouyi)
“要想滚粗:
0.仔细看错或者记错题。
1.选对不可做题。
2.思考坑爹题[鉴于‘坑爹’一词在AH的特殊含义,建议这一点改为“思考废条件怎么处理”]。
3.认真写自己不会的东西。
4.最后还不写暴力分。”
本沙茶中了其中的三点,因此悲剧了……
(2)热烈庆祝今年的题目不再坑爹了!!!!!(因为用的是JSOI的题,bus还抄袭了ZJOI……)
(3)这次的题目……要么是难想、好写(sport代码只有1K多),要么是好想、较难写,但还可以写的完的(指bus,和BZOJ上最近的那些数据结构相比真是太人道了……)
(4)要善于发掘题目的本质,特别是一些隐含的最优性质(比如mole的那个废条件为什么废);
(5)遇到想了很久想不出的题,一定要换一个方向去想,因为很可能是一开始的方向疵了;
(6)对于代码量较大的题(如数据结构题),到底写不写是要看情况的,灵活掌握;

一些闲扯:
(1)本沙茶所在的考场几乎全是神犇,就我一个沙茶……于是被虐傻了……
(2)比赛时看到对面的一个人在喝“和其正”……瞬间吓傻了……(话说肿么木有看到喝阿华田的囧……)
(3)昨天试机的时候,被Atbiter虐了半天,一开始肿么配置都是“找不到答案文件”……后来才发现Atbiter已经改版了,players下面的第一层文件夹应该是考试场数编号(Day1、Day2……);
(4)试机的时候发现鼠标是坏的,后来才知道这个考场有6个鼠标坏了,3个键盘坏了,2个系统时间显示错误……
(5)总之这次挂惨了,不过前30应该能进,重点是Round2,加油!!我要复仇!!

Feedback

# re: AHOI2013 Round1 题解&&总结  回复  更多评论   

2013-05-29 20:00 by hza
能不能求个完整的题面?

# re: AHOI2013 Round1 题解&&总结  回复  更多评论   

2013-05-31 14:53 by HT
@hza
百度文库有

# re: AHOI2013 Round1 题解&&总结  回复  更多评论   

2013-05-31 18:40 by Mato_No1
这……hza都出现了,吓傻了!!!!!

# re: AHOI2013 Round1 题解&&总结  回复  更多评论   

2013-06-14 16:58 by SillyJ
我是一只傻乎乎的J。
为什么我的mole网络流只有55分?用堆优化SPFA之后才过

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