【复仇之战】AHOI2013 Round2 总结

Posted on 2013-06-17 22:37 Mato_No1 阅读(2708) 评论(9)  编辑 收藏 引用 所属分类: AHOI
前言:
从2006年的全国第一,到2012年的全国第二十;
从国家队每年必有,到正式选手NOI Ag都拿不到;
时间可以改变一切,仅仅几年,我们共同见证了一个省从强省变成弱省;
而无比奇(keng)特(die)的省选题,又使得许多难以想象的事情发生了;
不知现在,还有谁记得一年前的那场风波,两年前的那场风波,三年前的那场风波;
不知现在,还有谁记得那些被奇(keng)特(die)的省选题和谐掉的众神;
相关链接0
相关链接1
相关链接2
———————————————————————————————————————————————————
今年,安徽省选终于不再是一场闹剧。
希望这能成为一个转折点。下面进入正题。
———————————————————————————————————————————————————

本沙茶还是考废了……6题有3题被卡常数,而且卡到和暴力差不多的得分……
不过毕竟复仇成功了……好像还进了A队……
不过像我这么弱到NOI也是被虐的份……

下面上题解:
【Day1】
coin:
首先那个贪心性质是比较好看出来的囧……就是如果每个面值都是上一个面值的正整数倍,则要得到一个价格的最小张数,总是先用最大的,不够了再用第二大的……以此类推。
(证明:假设价格为s,某个方案(a1, a2...am)(ai为第i大的面值使用张数)对于最大的面值不是按照这样的,则有s-a1*v1>=v1;若a2*v2>=v1,则将(v1/v2)张第二大的换成一张第一大的显然更优,若a2*v2<v1,则可得s-a1*v1-a2*v2>=v1-a2*v2>=v2,可以对第三大的继续分类讨论,这样一直到第m大的,必然会有一个出现可换成更大面值的情况,也就是该方案必然不是最优方案;如果最大的面值按照这样,后面的面值不按照这样,仍然如此)
这样只要所有面值确定,配成任何一种价格的最优方案也就确定了,且可以随着面值从大到小的一一确定,不断更新最优方案;
由于本题价格<=100000,所以考虑搜索。一开始搜最大的面值,然后在搜后面的面值的时候,只能枚举其因数。优化:
(1)初始定界:根据样例2+简单分析可以得出,使用2的幂的面值是一种比较优的方案,因此用它进行初始定界,可以大大方便后面的卡界;
(2)容易证明,如果所有价格中最大的为maxw,则最大的面值必然在[maxw/2, maxw]之间;
(3)很重要的剪枝:容易证明在最优方案中,相邻两个面值的比值必然是质数(否则设vi/v(i+1)不是质数,存在>1的因数d,则加入vi/d这个面值以后……)。因此,只需要预处理出2~100000间所有数的质因数即可;
(4)一些启发式优化(卡界);
(5)卡时;
综合使用以上方法可以得到85~100分;注意搜索中的数组分层问题;

cube:
被卡常数了,真悲剧……
本题的猥琐之处在于它的时空限制,时限1s,空限64M……给跪了!!!
只要求出(0, 0, 0)-(200, 200, 200)间的每个格子是否被覆盖,然后再做一次floodfill就行了囧……
实现方法有很多,最好的是三维树状数组(改段求点,一个数组即可,且可以用short)。
问题是,本题的floodfill如何实现?递归DFS,爆栈;人工栈DFS,MLE;BFS,在压位的情况下可以勉强卡过空间,但常数被卡了……
(求神犇好的解决办法囧……)

square:
首先两个不相交子矩形要么在X方向上不相交,要么在Y方向上不相交,要么在X、Y方向上都不相交……(废话)
因此结果等于(X方向上不相交的全黑子矩形个数)+(Y方向上不相交的全黑子矩形个数)-(X、Y方向上都不相交的全黑子矩形个数);
前两个显然灰常好求,第三个,只要求出每个点左上、右上、左下、右下四个方向里面的全黑子矩形个数,也灰常好求……
不过有一个细节:如何求出以某行/列为最下行/最右列的全黑子矩形个数?
一种方法是往左/右(或上/下)第一个比它矮的地方不断迭代,但这样遇到阶梯状的会被卡掉;
正确方法是找到往左/右(或上/下)第一个比它矮的地方,然后以这里为右下角的全黑子矩形个数=以那个地方为右下角的全黑子矩形个数+这里的高度*两个位置的距离;
然后就是严格的O(N2)了(不过数据很弱,本沙茶使用会被阶梯状的卡掉的办法也AC了囧);

至此Day1完挂。

【Day2】
(全DS题什么心态??????)
homework:
第一问……是人都会吧囧……
第二问……傻眼了囧……
其实看到第二问这种不能合并的东东就应该想到分块……这里说一种时间复杂度为O(N5/3)的分块方法
注意本题的两问都满足区间减性质,即“A[l1..r1]中关于[l2..r2]范围内的数的结果=A[l1..r1]中关于[0..r2]范围内的数的结果- A[l1..r1]中关于[0..l2-1]范围内的数的结果”。
因此,可以先对[l2..r2]这一维离线,然后按照值递增的顺序逐个加入A数组中的所有元素(一开始A数组为空),每加入一个数,就对l2或r2等于这个数的所有询问计算结果,这样原题就转化为了这个问题:
一个长为N的序列,一开始所有位置都为空,现在有两个操作:(1)在某个空位置插入一个数;(2)询问目前某区间内的数的总数,以及不相同的数的总数;
这两个问题都可以分块解决:设S1[i][j]和S2[i][j]分别表示目前第i块到第j块中数的总数以及不相同的数的总数,同时维护bool FF[i][j][k]表示第i块到第j块是否出现数k。插入一个数时直接维护S1,根据FF维护S2即可。显然块大小sz应取N2/3,总的时间、空间复杂度均为O(N5/3)。
这样……本题时限10s应该能过了吧囧……但是常数……万恶的常数啊!!!!!(事实上后5个点在本机上都是8.5s左右的,只有第4、5个点T,但在那里不知为什么几乎全T了……)

disconnected:
这个……本沙茶真心不会搞囧……
@drcrow神犇说有一种按询问分块的办法,其思想具体见他今年CTSC的论文……但本沙茶智硬理解不了……
求各位神犇解释……

diff:
(很水的题,很坑爹的常数……本题真是推广SAM的利器……)
本题的核心在于算任意两个后缀的LCP之和,其它的很容易推导出来……
后缀的LCP,“正常人”的第一反应是SA……
求出SA及height后,转化为线段树问题……然后就直接搞定了……
但是……………………………………………………………………………………………………
本题N<=500000,时限2s!!!!!!!!!!!!!!!!!!!!!!!!!!!!
如果求SA,不管是倍增还是DC3都会T(把SA求出来就T了)
因此,正解其实是SAM,把这个串的SAM求出来之后,直接用DFS求次序,再求height……这里的时间复杂度就是线性的了。
(WJMZBMR:现在SA早就过时了,要用SAM!!!不,其实SAM也过时了,现在是Suffix BST以及2K Substring BST,但考虑到AH太弱了,同情一下,降低一点难度……)

至此AHOI Round2完挂。
(不过许多人都放水了囧……他们说我去年滚粗,太可怜了,要照顾我……于是我这样的弱智就A队了……)
(HSAAHNU进了6个……太可怕了,坐等NOI组团虐场……)

Feedback

# re: 【复仇之战】AHOI2013 Round2 总结  回复  更多评论   

2013-06-19 11:25 by hza
day2 第二题是对询问分治。。

# re: 【复仇之战】AHOI2013 Round2 总结  回复  更多评论   

2013-06-19 21:29 by **
day2第一题离线之后MS可以树状数组套线段树
第二题先随便弄一棵生成树,
对于非树边(x,y)在生成树上找到x->y的路径的所有边值+1
删边操作的话,x->y路径的所有边值-1,边值小于0就不连通

# re: 【复仇之战】AHOI2013 Round2 总结  回复  更多评论   

2013-06-20 10:08 by hza
@**
第二题这样弄的话貌似没比暴力好多少

# re: 【复仇之战】AHOI2013 Round2 总结  回复  更多评论   

2013-06-20 18:32 by **
@hza
可以用LCT/树剖维护啊

# re: 【复仇之战】AHOI2013 Round2 总结  回复  更多评论   

2013-06-21 13:09 by taorunz
day2t3 SA再用栈维护救行了

# re: 【复仇之战】AHOI2013 Round2 总结  回复  更多评论   

2013-06-21 16:04 by hza
@**
不觉得树链剖分可做。。至少我没想出来

# re: 【复仇之战】AHOI2013 Round2 总结  回复  更多评论   

2013-06-22 13:15 by **
@hza
判断边值小于0,可以维护边值的最小值,然后打打标记

# re: 【复仇之战】AHOI2013 Round2 总结  回复  更多评论   

2013-07-03 20:18 by EZ_lzh
D2T2貌似可以树套树。

# re: 【复仇之战】AHOI2013 Round2 总结  回复  更多评论   

2013-07-16 00:19 by ftiasch
D2T2有每组询问2^4的算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理