加载中…
个人资料
溫柔壹刀
溫柔壹刀
  • 博客等级:
  • 博客积分:0
  • 博客访问:4,760
  • 关注人气:1
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

hdu4456 Crowd

(2012-11-09 11:01:09)
标签:

hdu4456

crowd

杂谈

分类: 线段树
杭州赛区的这一题是个巨坑,虽然现场1A瞬秒,至今觉得不科学。
该题只有两个操作,一是在一个点加一个值,二是求一个菱形区域的和。这不是和二维树状数组的水题长得一摸一样嘛……至于如何把菱形变成平行于坐标轴的矩形,果断只要把地图转45度就可以了,然后稍微推一下坐标的变换公式。然后对于每一次第二个操作用容斥原理做四次求和。
不过这样效率是够了,但空间要开到20000*20000,搞笑的是现场的时候我是最后填数组大小的,填完就觉得会MLE,瞬间心凉了一半,无法,代码都写完了,总不能不交吧,硬着头皮点下submit,等了30秒弹来“Yes”,呵呵……,不拍桌子庆贺一下对不起自己啊!想想也后怕,如果写代码之前就意识到数组要开那么大,果断是不会下手的……
总结出一个道理,没有想不到,只有不敢做!
至于现场代码不知道在hduoj上会不会AC,反正要退役了,也懒得再写一遍,如果有人要代码的话,可以勉为其难脑补一下,不过我怀疑在hduoj上还是会MLE,如果想AC的话估计要考虑80000个询问,所以最多影响80000个点,应该将这些点用什么方法映射一下就可以了,没仔细想……


ps:现场的C题为什么没解题报告?虽然C题现场没做出来,但经事后讨论,先用等差数列求和公式算出Q=k时的所有数的个数(包括重复的),因为Q最大为1000000,所以从1开始到1000000递推一遍打表,当然也要同时减去重复的个数。当Q=1时,没有重复的,所以答案为n-0,当Q=k时,减去的重复个数=每两个相邻的相同数字之间有(p-2)个数字的个数的和(2<=p<=k),那如何算相邻的相同数字之间有q个数字的个数呢?因为元素的个数最大到1000000,所以只要对于每个不同数字记录它上一次出现的位置,如果再次碰到相同的数字与上一次的位置之差为q+1,则相距为q的个数+1,同时更新该数字上一次出现的位置,所以只要把数列扫一遍就能知道所有相距为q的个数(1<=q<=n-2)。总效率是O(n)的。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有