NOIP模拟 38
2024-10-06 11:30:38
liu_runda的题!
错过辽QAQ
T1虽然没用题解的损益法,但是用高精%还能过..
没想到敲完就过编译了,还以为要调一天呢
高精度的阴影没了~
T2的思路很巧妙
首先一个区间最多有一种颜色占一半以上,所以分别计算3种颜色的贡献
处理个+=1的前缀和,又转化成求逆序对
log过不去,发现右指针每右移一位,所查询的权值的变化量一定是1
那可以在左边也放个指针,抖一抖维护出贡献就行了
T3 二分套二分
之前就被一道wqs的二分题虐死了
到今发现以前根本没搞懂,重学wqs
核心就是根据题目性质,发现代价(斜率)随x单调(不严格)变化
所以可以根据x的需求变动代价(斜率)
同时还可以求出对应的f(x),二分到需要的x就完事了
稍难的在二分不到x怎么办(因为斜率不严格单调或精度不足以发现区别)
那么此时x那段是平的,也就是选不选贡献一样
那么可以强制都一样时一定要选(或不选),就使得 在切这一段斜率不变的函数时,你的答案总集中在边缘的某点。
假设让它集中在较小的x,就在每次$x<=lim$时更新$ans$,这样仍保证ans加回$lim*cost$仍是对的
让他集中在较大的x也一样。
二分套二分看起来玄学,其实把情况都考虑好了还是可以安安稳稳地一遍过编译&&样例&&100%的测试数据的~
最新文章
- python ImportError: No module named builtins
- linux进程
- EF框架组件详述【Entity Framework Architecture】(EF基础系列篇3)
- MySQL如何利用索引优化ORDER BY排序语句
- 如何在Ubuntu 14.04服务器上自动化部署Spring Boot的应用
- SVM=LASSO?
- windows下如何修改远程登录端口
- 继续推广我的新博客xysay:http://www.xysay.com/
- 【SQL】大杂烩
- lua代码的加载
- 开源电子商务平台:OfBiz
- 中文dumps显示
- IDA + VMware 调试win7 x64
- php时间戳和日期转换,以及时间戳和星期转换
- EXCEL导出工具类及调用
- Nginx应用场景
- laravel 5.1 单元测试 Cannot modify header information 错误
- VMware运行时“内部错误”的解决方法
- busybox编译 fatal error: curses.h: 没有那个文件或目录解决办法
- URL最大长度问题