题解 | #智乃的博弈游戏#
任造化落骰
https://ac.nowcoder.com/acm/contest/95338/E
E题题解
思路
为什么要数据随机？因为不随机做不出来。
考虑这么一个例子，
1 2 3 4 5 6 7 8 9 ...
我们要取出所有的区间，复杂度是 的，直接爆炸。
现考虑随机性。
我们固定左端点，右端点在不断右移的时候，能够使得区间改变 的位置是有限的。
为什么？
改变 需要严格大于，每次选出一个大于其的数，后续严格大于的期望其实是在不断折半的，因此最多
个。同理对于
，所以我们固定左端点，右端点有效移动的位置，是这些严格 大于/小于 的位置之和，最多
个，我们通过单调栈 + 双指针 即可完成模拟。
实现
通过单调栈找严格 大于/小于，然后通过双指针取出这些位置， 记录
的数量，最后丢进数组中，记录
即可。
查看11道真题和解析