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