博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[置顶] Codeforces Round #198 (Div. 1)(A,B,C,D)
阅读量:7104 次
发布时间:2019-06-28

本文共 778 字,大约阅读时间需要 2 分钟。

赛后做的虚拟比赛,40分钟出了3题,RP爆发。

A计数问题

我们可以对每对分析,分别对每对<a, b>(a走到b)进行统计,那么这对<a, b>产生的期望为distance(a, b)/n

(把这一对选出来以后相当于一个点,那么分子distance(a, b)*(n-1)!,分母n!,     (n-1)被约掉了。)

这样的算法是O(n^2)的,问题转化为统计所有对<a, b> 的距离。我们可以对输入的a数组排序

那么对于每对<a,b>可以拆成几段相邻a数组的值之差。

对于零到其它点另外拿出来考虑,显然ans += 所有a数组的值,

没有零的情况,枚举相邻a数组的值,然后统计经过这两个点的<a,b>对数(注意方向有两种,要乘以2)。

看上去很多,但有了思路就很快的。

B最长不下降序列O(n*log(n) )

找找规律可以发现,对于每个数,它后面有比它小的数,那么它们就有一条边,我们找独立点集是找没边的,

所以对于一个数,在它后面的数我们只能选择大于等于它的数。

C裸的容斥

《组合数学》里面容斥那章有很多类似的题目,记得某次浙大月赛也出过类似的题,这种题已经做烂了。

D二维树状数组

赛后补的题,比赛的时候想用线段树做,但二维线段树空间开不下, 一维是可以做的。

我们先分析一维树状数组的做法,树状数组是向后更新向前查询的,

对于(1---n),我们先假设更新都是(x---n), 查询都是(1---x),其它情况可以分成2个更新或2个查询。

更新 xor v:若x为奇数,那么我们要查询x+1,x+3.....时这个v值是没有用的(抑或掉了)。 有用的是x+2,x+4....

                  若x为偶数,反之亦然。

很显然我们开两个树状数组,分别是奇数位置和偶数位置。

查询:         若x为奇数,查询奇数的树状数组

                  若x为偶数,查询偶数的树状数组

推广到二维也是一样的。

 

转载地址:http://xochl.baihongyu.com/

你可能感兴趣的文章
scrapy-redis实现爬虫分布式爬取分析与实现
查看>>
Android仿微信UI布局视图(圆角布局的实现)
查看>>
docker
查看>>
OKR 方法 学习笔记
查看>>
CG资源网 - Maya教程
查看>>
http://blog.sina.com.cn/s/blog_62e1faba010147k4.html
查看>>
CSS默认可继承样式
查看>>
数据库中树形结构的表的设计
查看>>
关于Cocos2d-x的瓦片地图
查看>>
位置无关码
查看>>
find-k-pairs-with-smallest-sums
查看>>
情绪板携手视觉设计
查看>>
Atitit.php nginx页面空白 并返回500的解决
查看>>
http://blog.csdn.net/LANGXINLEN/article/details/50421988
查看>>
PHP高效率写法(详解原因)
查看>>
Swift 值类型/引用类型
查看>>
【WPF】点击滑动条(Slider),移动滑块(Tick)到鼠标点击的位置
查看>>
[每天五分钟,备战架构师-9]数据库系统
查看>>
[转]WinForm和WebForm下读取app.config web.config 中邮件配置的方法
查看>>
HDU-1903 Exchange Rates
查看>>