contest2 CF989 div2 ooox? ooox? oooo?
题意
div2C (o)
在\(小于50*50\)的棋盘上放\(A, B, C, D\)四种花, 并给出每种花的连通块数量\(a, b, c, d(\le 100)\), 输出一种摆法
div2D (x)(x)
在一个数轴上\(n(\le 10^5)\)个云, 给定他们的坐标(宽度都相等为\(L(\le 10^8)\), 保证不重叠),他们的初始速度为\(+1~or~-1\)
在原点上有一个月亮, 求云的无序对的数量, 满足给这两朵云同加一个风速\(w\)(\(|w|\le wmax(\le 10^8)\)),他们能在某一个时刻同时覆盖月亮
div2E (?)(?)
待续
题解
div2C
有意思的构造题
各种解法:
div2D
这题不要想得太复杂
首先思考两朵云怎样可能同时到达月亮:
- 同向的云不行
- 背向的不行
- 只有相向的可以
考虑在同一风速下, 两朵云相遇时间固定
换参考系: 风
则转化为: 两朵云以\(1\)的速度, 定点定时在中间相遇, 月亮以风速\(w\)运动
- 注意:为了简化问题, 因为速度限制是带绝对值的, 我们直接考虑标量即可, 不用再管正负
因为风速有上限, 所以最低要求就是让月亮在两朵云正好离开的那一刻到达中间点即可
设云分别为\(x1, x2\), 相遇点距离月亮\(d = (x1 + x2 + l) / 2\), 正好离开的时间\(t = (x2 + l - x1) / 2\)
则\[\frac{d}{t}\le w_{max} ~~~~~(1)\]
当\(x1\)不变, \(x2+\Delta\)时
\[\frac{d+\frac{\Delta}{2}}{t+\frac{\Delta}{2}}\le w_{max}~~~~~(2)\]
可以证明\((1)\)成立时\((2)\)也成立, 于是满足单调性
二分或者单调队列都可做
总结
模拟赛后面一个小时都在想\(D\)题。。。
没有发现相遇时间固定, 所以也不会去想什么换参考系
然后在死推不等式
赛后经同学提醒, 于是换参考系, 然而没有抓住最晚时间时两朵云正好离开这一点
(没看到题目说速度的限制时绝对值。。。于是在想速度很小。。。),还是没做出来
教训还是不要慌, 不要一下陷进去, 审清题意, 冷静分析
最新文章
- 用canvas绘制折线图
- 计算机网络(11)-----TCP连接的建立和释放
- 不写1行代码,在Mac上体验ASP.NET 5的最简单方法
- android学习笔记八——SeekBar
- PL/SQL devloper 常用设置
- enum 在c中的使用
- C#:在catch中return,会执行finally吗?
- SQL服务器名称的更改
- pomelo研究笔记-RPCclient
- KMP算法 学习例题 POJ 3461Oulipo
- SQL SERVER - 谈死锁的监控分析解决思路
- Linuxc - Makefile完成项目的管理。
- mysql常用基础操作语法(二)~~对表的增删改操作【命令行模式】
- 20175120彭宇辰 《Java程序设计》第九周学习总结
- java利用线程池处理集合
- webapi 重复提交问题
- xss测试用例
- 用IrisSkin2.dll美化你的WinForm
- Pytorch CNN的各种参数
- 问题诊断神器arthas