CSPS_104
又被爆踩。
正解写挂。
暴力不会。
只会改题。
还要加油。
T1
$nlog^2$是显然的
那么考虑只二分一次,就$nlog$了!
有什么能通过一次二分$O(1)$得到呢?
二分a的位置,$O(1)$得到b的位置
check的特判极其惨烈,%%%$Rock_B$调出来了
另一种简单一点的做法:
二分查找不好搞,考虑另一个二分——分治
通过分治,让每次的询问参数减半,也是$O(logn)$的复杂度
设计一个函数找到a的长度为lena,b的长度为lenb时,排名为rank的元素
那么把每次询问的rank分成一半,在a,b中找到对应的位置(长度不够则让另一个串多分一点)
如果$a[k/2]<b[k/2]$,则可知$a[1]~a[k/2]$都不可能成为排名为rank的元素
因为把ab放一起排序后$a[k/2]$后面的元素太多了..显然一定多于$lena+lenb-rank$
所以把$a[1]~a[k/2]$直接排除出答案,把rank-=k/2(或者当lena<k/2时的lena),递给下一层解决
T2
一个dp分成两部分
$dp[i]=min(dp[j-1]+value(j,i))$
单调栈维护所有可能贡献出value的j(单调递增栈)
对同一个j维护可能的最大$dp[k-1](k<=j)$,随便用什么数据结构维护栈里的最大值即可。
T3
暴力我打的是vector启发式归并,后来电脑关了,不知道有多少分。
正解?
高度烧脑警告。
我和miku啃了好久题解才弄明白
(miku教了我好久我才懂的差不多)
首先对于一个整型随机变量x有这样一个东西:
$E(x)=\sum\limits_{i=1}^{inf} P(x>=i)$
E(x)为x取值的期望,P为命题成立的概率。
证明么..
$$\begin{array}{rcl}\\E(x)&=&\sum\limits_{i=1}^{inf} i*P(x==i)\\&=&\sum\limits_{i=1}^{inf} i*(P(x>=i)-P(x>=i+1))\\&=&1*P(x>=1)-1*P(x>=2)+2*P(x>=2)-2*P(x>=3)+...\\&=&\sum\limits_{i=1}^{inf} P(x>=i)\end{array}$$
现在有了这样一个东西,先考虑每个询问的答案
$E_q=\sum\limits_{i=1}^{maxv} P(max_{j=l}^{r} val_j >=i)$
容易想到$i>maxv$的时候没有贡献。
那么求每个位置的最小值大于等于x的概率即可
这个概率就是小于x的数都不出现而大于等于x的数出现一个的概率
不是很好求,转化一下
求它的反面,也就是每个点的最小值都小于x,也就是大于等于x的都不出现
这个就好列式了,而且每个位置出现每个值的概率可以预处理,看起来可做了
$E_q=\sum\limits_{i=1}^{maxv} 1-\prod 1-P(v_j>=i)$
$v_j$是第j个位置的最小值
总结一下,答案就是:$ans=\sum\limits_{i=1}^{maxv} \sum\limits_{q=1}^{Q} 1- \prod 1-P(v_j>=i) (L[q]<=j<=R[q])$
可以想到,枚举i时,只有出现魔法石的i才会有$\prod 1-P()$的值的改变,其他情况下后面那坨柿子完全不变
所以只需要枚举有石头的i,没有石头的i没有变化可以放在一起统计
考虑维护后面那坨柿子。
首先那个1可以直接提出来,那么剩下的就是一个连乘的和
考虑每个石头,他的加入只会影响“某些询问”的连乘中的“某一项”
由于区间左右端点对应单调,他影响的区间也一定是连续的
所以可以用数据结构批量修改区间的连乘,具体做法为把他们的权值乘上一个$\frac{1-P_{now}}{1-P_{last}}$
推荐使用线段树区间修改。
大体的思路如上,细节比较多..
最新文章
- Spring+Quartz(定时任务)
- Android异步回调中的UI同步性问题
- 【转】編譯Ogre1.9 IOS Dependencies及Ogre Source步驟及相關注意事項…
- (原)win8下编译GLUT
- tengine-2.1.0 + GraphicsMagick-1.3.20
- mongodb的监控与性能优化
- SQLSERVER:计算数据库中各个表的数据量和每行记录所占用空间
- DJANGO中filter_horizontal和raw_id_fields的作用
- Service详解
- day01:study HTTP协议
- Windows下配置 Nginx + PHP
- 安装odoo小程序商城模块报错 KeyError: u&#39;oejia_weshop&#39;
- iOS----------关于Cornerstone的偏好设置
- table行颜色设置
- C# 操作文件类,文件夹存在判断,创建,文件内容读写。
- WINDOWS内核编程(一)Hello Drv的实现
- unicode编码和utf8编码的区别
- (大数取模)Big Number hdu1212
- 观察者模式(Observer Pattern)
- LAB3 整数相加
热门文章
- [Note] Clipboard.js 使用
- Kafka 学习笔记之 Kafka0.11之producer/consumer(Scala)
- Kotlin编译时注解,简单实现ButterKnife
- javascript进阶-《原型对象和原型链》
- Java 语言的发展史
- Android 列表(ListView、RecyclerView)不断刷新最佳实践
- 机器学习回顾篇(7):决策树算法(ID3、C4.5)
- Mysql 为什么要选择 B+Tree
- PHP krsort
- Github 上热门的 Spring Boot 项目实战推荐