首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
ynoi2018专题
P4117 [Ynoi2018] 五彩斑斓的世界
分析第一个操作 朴素的做法,遍历一遍大于x就-=x,极限复杂度O(mn) 分块做法 整块:我们维护一个最大值,从mx到x遍历一遍(减去x)用并查集操作merge(i,i-x),考虑mx=100001,x=1,极限复杂度O(mV) 我们可以分析 1.x>(mx/2),从mx到x遍历一遍,应该是最优的复杂度O(mx-x) 2.x<(mx/2),最优的复杂度应该是O(x),因此思考在这种
阅读更多...
[Ynoi2018]天降之物
天降之物 题解 只有 ** 出题人才会出这种又难调又卡常的 ** 题。 笔者原先很快奶出了一个 O ( n n log n ) O\left(n\sqrt{n}\log\,n\right) O(nn logn)的做法,然后调了一个下午,交上去后死活过不了,只好又优化了半天优化出了一个 O ( n n ) O\left(n\sqrt{n}\right) O(nn ),又调了
阅读更多...
bzoj 5143 [Ynoi2018]五彩斑斓的世界
二阶堂真红给了你一个长为n的序列a,有m次操作 1.把区间[l,r]中大于x的数减去x 2.查询区间[l,r]中x的出现次数 题解: 今天模拟赛第一题=_=,把题看错,然后暴力打了30分跑路了。 由乃题肯定是分块了。 由于数字的大小只有十万,可以先假装
阅读更多...