Exam20240629 赛后结

Exam20240629 赛后结

T1

想法几乎是对的，结果两个不能直接乘起来

就是如果你不太冷静的话就容易做出错误的判断，我考虑了这个问题，居然认为直接乘起来是可以的emm

T2

不太熟悉容斥，想到前缀和之后扔了

结果它这个时候就已经变成 slime和npc 了

这个时候就只需要钦定一段是大于 k 的其他直接组合数填就 OK 了

其实考的时候想到了这样做，但是由于害怕自己不熟悉容斥弃掉了，比较可惜，其实肯定是可以做的。

所以重算一下，理想应该能够拿到 260pts，这个还是相当高了，还是要对自己有信心，同时增强熟练程度

T3

搞了奇怪方法，好像复杂度卡成 \(\mathcal O(nq)\) 了，直接拿到 60，不知道怎么搞得。但是向这个方向想是肯定不行的，其实这个第一个性质当时我想到了，可是没有重视，下次应该记得都写出来（主要是时间不足了，打暴力花了很多时间，马力还要练）

剩下的还是比较有思维难度

看懂了，发现这个性质之后，就可以考虑增量构造答案，这个改掉一段就相当于删掉连续段，这个是和我那个暴力是相同的，这也说明了那个做法就是 \(\mathcal O(nq)\) ，两个相同的大元素删除中间的一段”小“元素（此处大元素就是可以战胜小元素的），这个很像括号匹配，可以用栈维护，发现最后的栈底就是答案。

不过这样还是 \(\mathcal O(nq)\) ，但是我们发现，这个弹栈的操作，要么：

• 弹 0 个加 1 个（当且仅当会被栈顶打败）+1

• 弹 2 个加 1 个（当且仅当可以打败栈顶且栈大小大于1）-1

• 弹 1 个加 1 个（当且仅当可以战胜栈里的唯一元素或者和栈顶打平）0

要找的栈底，就是最后一个替换掉栈底的元素，即最后执行战胜栈里唯一元素的那个

此时栈大小从 1 还是变为 1，换言之最后一个栈大小为 1 的地方就是答案

所以可以考虑线段树，只需要维护最右边最左边元素是谁和最右边那个地方的栈大小，然后维护最小值和最小值的位置