CH上的Think Bear#1模拟赛
2024-09-05 13:20:46
分析:
第一题:并查集维护,类似生成树的思想。
第二题:线段树成段更新就行了。维护区间和sum以及区间平方和s。那么平均值只要用到区间和sum,方差的话可以把公式拆开=s-2*平均值*sum+平均值*平均值。updata的时候类似的拆开……
第三题:题解讲的很明白,这里只是总结一下自己的错误。
保持i和j的位置不变,如果有这样的式子:max{...,...,...,...+ai+...,...+bj+...,...}
交换i和j的位置,就有这样的式子:max{...,...,...,...+aj+...,...+bi+...,...}
要交换前的结果比交换后的结果小。
第一个错误:我认为这等价于一个不等式组:ai<aj且bj<bi。从这个不等式组的确可以推出前面那个,但反过来却不一定……
第二个错误:顺着第一个错误的思路,我错上加错,ai<aj且bj<bi我竟然直接等价于一个不等式ai*bj<aj*bi……然后发现者不对之后我竟然又以为等价于ai+bj<aj+bi,我不等式到底有多烂……
正确的思路是基于考虑交换相邻的两个位置i和i+1,使得i+1的价钱变小对后面就越有利。。。想一想真的很有道理……然后就很好推了……
最新文章
- 马氏距离(Mahalanobis distance)
- Inventor 2014 sp1/sp2激活
- 【BZOJ-1458】士兵占领 最大流
- asp.net mvc get controller name and action name
- oracle学习----特殊的连接方式
- Jquery 对话框确认
- CentOS6.8安装JDK1.7
- HDFS命令全总结
- linux使用Nginx搭建静态资源服务器
- ESP8266 RTOS SDK烧写环境构建
- [转]图解Docker容器和镜像
- fiddler 笔记-重定向
- Gym - 100989L
- HTTP笔记01-http相关的基础知识
- 微信小程序——获取用户unionId
- Log4J日志信息配置文件详解
- linux command wrap
- Tidb数据库报错:Transaction too large
- MikroTik RouterOS x86最大内存只能支持2G
- 国家code和区号计算