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 的地方就是答案
所以可以考虑线段树,只需要维护最右边最左边元素是谁和最右边那个地方的栈大小,然后维护最小值和最小值的位置
标签:这个,栈顶,元素,Exam20240629,当且,nq,栈底,赛后 From: https://www.cnblogs.com/haozexu/p/18288960