contest zju Monthly August 2010
昨天是ZOJ Monthly, August 2010
好久没做题了…N天前就看到这次月赛是东方专场…于是想着一定要去凑凑热闹…
不过最后还是只做了4个小时…最后一小时忙别的事情去了…
一看题数…居然有13题…
题号也变成了各种人物的名字了…
一上来是第阿求题…禁语吗……glob和regex的转换…看了下样例感觉不难…但是害怕有一堆要考虑的东西…
然后是第⑨题…算术教室…n个人围成一圈随机选取m个人,其中有9人是连着坐的概率是多少呢?…第一反应就是感觉是组合数方面的于是无视中…
然后看到已经有人过题了…第妖梦题…为大胃王幽幽子准备食物…第i天能准备bi份食物,但是要吃掉ai份食物…希望食物越新鲜越好…求各天准备多少食物…果然很水呢…从后往前扫一遍就可以了…
本想就看看题目娱乐下…结果一不小心手痒了…
于是敲了下…过了…
接着发现又一题有人过了…第四季题…黑白分明呢…用了Bad Apple影绘的图…
把24位点阵图转换成灰度然后再根据公式二值化…也很水…看到那句”All divisions are truncated divisions.”后就想…会有人栽在这里吧…后来真发现有个id是”一句All divisions are truncated divisions. 让我wa了10次，杯具了整个下午！！！”
但是敲了一下…在本地测试的时候用scanf(“#%2lx%2lx%2lx”,&r,&g,&b);来读入,结果本地测试死循环了…难道#也是特殊字符?于是改成了scanf(“%#%2lx%2lx%2lx”,&r,&g,&b);在本地测试通过了…可是交上去OLE了…难道编译器不同吗…
于是很郁闷的改成了scanf(“%s”,str);sscanf(str+1,”%2lX%2lX%2lX”,&r,&g,&b);
题目描述里面没说输出的9或者空格之间需要空格隔开…但是sample output里面却隔开了…于是改成没有空格隔开结果wa了…
最后再改回来有空格隔开的才AC…
接着看到第灵梦题有人过了…塞钱箱…说是第i天请人赛钱可以得到si元,但是如果这么做了,下一次请人赛钱的时间必须在xi天后,yi天前…求如果第一天请人赛钱的话,最多能得到多少钱…
稍微想了下,一个简单的dp而已…dp[i]表示第i天请人赛钱的话,从第i天开始最多能得到多少钱…转移时只要找xi天后,yi天前这段区间的dp值最大的即可…
然后一看规模…5万天…囧了…不过求区间最大值而已…解题报告虽然说用线段树…可当时我想到的却是rmq…
但是rmq是一次性的预处理的…于是就YY着改造了一下,依然沿袭rmq那种思路:分成logN层,每层有N个数,第i层的第j个数表示在[j,j+2^i-1]的范围内最大值是多少
然后从后往前边dp边insert,对于第i天来说,这天之后的每一天的dp值和rmq数组值都是已经得到了的,于是就能得到第i天的dp值,然后将这个值插入进rmq数组,更新第i个数的那logN层数字,总复杂度O(nlogn)
很快写好了…提交却下标越界…然后发现数组开小了- -|||…改后AC
在看解题报告的时候发现评论里有说Sparse Table什么的…原来我那方法叫这个名字啊…
接下来看到第辉夜题有人过…妹红要埋伏辉夜吗…题目是求一张图上从起点到终点之间的必经之路…也就是桥?…模板题吗…可惜我只有割点的模板…于是忽略了这题…
接下来看到第芙兰题有人过了…永夜抄吗……看到迷途竹林以为又是图论有关的…结果却不是这样…
一共有n个房间,第i个房间有xi个ITEM,每个是ai点,有yi个TIME,每个是bi点,每次去一个房间把所有这个房间的ITEM和TIME收完回到入口,直到所有房间的ITEM和TIME都收完…
拿一个点数是a的ITEM的时候可以得到IV分,并且TV增加a
拿一个点数是b的TIME的时候可以得到TV分,并且IV增加b
一开始IV和TV值为0,求最多能得到多少分
因为进一个房间后,该房间所有的ITEM和TIME都要收完,所以先考虑在一个房间内的情况,该按什么顺序收最好
小数据手动演算了一下,发现分数会增加IV*xi+TV*yi+u*ai+v*bi,并且u+v=xi*yi,并且对任何正整数的u,v搭配都总有一种顺序可以满足
于是得到了在第i个房间内最多分数会增加IV*xi+TV*yi+max{ai,bi}*xi*yi的结论,可见ai,bi和IV,TV是分离的,因此外面用一层状态压缩dp计算2^15个状态就可以了
dp[state]表示state的位为1的对应的房间已经去过的情况下,所得到的最大分数
并且这个情况下的IV和TV值是固定的,轻轻松松的上吧…
又看到第因幡题有人过…腹黑兔啊…看似公平的游戏却把规则定的自己总有必胜策略…想到东方夜神雪里面那个取硬币小游戏…轮流取1~3枚,取走最后一枚的人输…可是起始的硬币数量并不是随机的…而是4k+1…太囧了…玩了好几盘才发现原来这游戏是必输的…
回到这里…这次是类似孔明棋的小游戏…每次可以选一个棋子往4个方向之一跳,但是必须跳过别的棋子并且最终落在某个空格上,中间可以跳过连续多个棋子,被跳过的棋子都会被拿走…
给定初始棋局,问让铃仙和因幡谁先走可以使得因幡有必胜策略…
一看规模才5*5…想想2^25也不是什么大数字…加上有一句”It’s guaranteed that no more than 61.8% of them are ‘e’s.”…感觉状态会很少…于是直接暴力记录博弈状态…
第一次交忘记处理了选取的棋子是一排棋子中间的某个棋子的情况…改后AC
然后…第魔里沙题有人过…魔炮啊…是个计算几何…求往什么方向射可以打中最多点,魔炮的范围是个顶点为原点的抛物线
抛物线啊…想到每个点有个可被命中的角度范围,也就是魔炮的方向在这个范围内,这个点可以被打中,但是对不同距离的点而言,这个范围的大小是不一样的…
计算了下,二次系数是a的抛物线和半径为r的圆的交点
y坐标是: y=(sqrt(1+4*a*a*r*r)-1)/(2*a)
设上图中P点对应的极角为alpha,那么当魔炮中轴对着[alpha-theta, alpha+theta]区间中任意的极角时,P点就能被打中
这个theta值为: theta=atan(x/y) =atan(sqrt(y/a)/y)=atan(sqrt(1/y*a))
于是问题转换成了,找一个极角,使得它被最多的区间覆盖…而数据规模有3万个点…
脑中第一个闪现的是离散化+线段树…显然太麻烦了…
然后想起以前某些题…比如矩形求并之类的…貌似只要看左右边界判断出入就行…
于是想到了用这个方法就好,将区间变成端点,左端点标记为入,右端点标记为出,然后将所有端点按大小(这里是极角)排序
然后从前往后扫描,遇到标记为入的端点就当前覆盖区间数加一,遇到标记为出的端点就当前覆盖区间数减一,扫描一遍下来,取当前覆盖区间数的最大值…就是所需的答案daze
另外处理下跨边界相邻的情况,就是当区间在[0,2pi]的两边时,就多插入个小于0的那个入端点和大于2pi的那个出端点
然后…有别的事情…于是就看看题目然后不继续做了…
第极题…姬海棠也有啊…貌似是找最安全点…话说游戏里寅丸星的香蕉激光实在是太恶心了…但是这题目里面是射线…而且是曼哈顿距离?…直接傻眼了…点和线的曼哈顿距离?那是什么?怎么求?
第图书题…不动的大图书馆…题目是一共m种元素卡,一共有n种符文,每种元素卡上等概率出现这n种符文中的一种,求m种元素卡各取一张的话,有多少概率可以使得这些卡上的符文至少有l个是相同的…输出成既约分数…
又是组合数类的题目吗…
第咲夜题…时间的操作…哦不…这题是求表达式结果是某个类型的可能性个数?
题目很长呢…
第幽幽子题…赏花会啊…真好呢…
又是做食物…这次是第i天幽幽子会吃掉ai份食物…妖梦每天可以做L份食物,或者花一天时间锻炼自己使得L值增加1…求N天过后剩下的食物最多还有多少份…
这里或者这里是官方解题报告吧…
下面是我灵梦,芙兰,魔里沙题的代码…