2024-年第四届高校大数据挑战赛-赛题-A岩石的自动鉴定
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
的p和q可以相等。子序列为 p 0 p q,观察到,中间要出现一个0。那么,我们只需要找到第一个 p 满足与前一个 p 中间隔了最少一个0,并记录它的位置。那么,在它位置之后出现的所有正整数组成的集合的大小,就是 p 对答案的贡献。那么只需要先把满足条件的p的位置都求出来,然后按照从大到小的顺序排序一下,从后往前维护一个集合,然后遍历到p的位置的时候更新答案值,即可。