P6717 [CCO2018] Boring Lectures
问题相当于求两个距离不大于 \(k\) 的数对的和的最大值
我们把修改改为先删除再进行插入的操作,对于插入操作我们使用线段树在左端点维护每个区间的答案
维护区间最大的最大值+次大值,区间最值即可更新答案。
咋删?不好删,那么就不删,直接离线然后线段树分治即可
P4581 [BJOI2014] 想法
...?这啥神秘题目
一眼考虑随机化,这不随机化还能咋做,毕竟只需要以比较高的概率回答的比较准确即可。
我们首先考虑给每个入度为 \(0\) 的点都随机赋予一个权值,,求出每个点能够返回到的入度为 \(0\) 的点的最小权值,
权值的期望是 \(\frac{\text{随机值域}}{k+1}\)。
容易发现单次求的复杂度是 \(\text O(n+m)\) 的,我们直接暴力求很多次然后取平均值即可。
李华与变色龙
注意到 \(k\le 40\),向左走的变色龙遇到向右走的变色龙后认为是变成了 \((a+b)\bmod k\),而向右走的变色龙颜色不变。
我们从右往左枚举每一只向右的变色龙,设两只中间的距离为 \(val\),则答案(每个颜色)都要加上 \(\frac{val}{2}\times a_i\),其中 \(a_i\) 为颜色 \(i\) 的向左的变色龙初始位置在当前枚举的向右的变色龙右边的数目。
这样复杂度 \(O(nk)\) 可以通过。
笑熬浆糊
咕了先
标签:即可,太多太多,随机化,每刻,权值,变色龙,想要 From: https://www.cnblogs.com/Vsinger-LuoTianYi/p/18447203