除去1001,1006,1007,1008四道水题外,1002 ~ 1005这4题应该是有铜牌到银牌的难度的,剩下的1009 ~ 1011属于金牌及以上难度。签到题里面,1008可能稍微难一点,到区域赛能出这题并且罚时不高基本可以铜。
1003 后缀数组 + RMQ + 二分 + 主席树
题意
给长度为105的串s,有m次查询,查询用(l,r,k)表示,要求输出s[l..r]这个子串在s里面第k次出现的位置,如果不存在,输出−1。
分析
- 首先由于子串s[l..r]肯定会在l处出现一次,并且子串长度为r−l+1;
- 不妨对s进行后缀排序,学过后缀数组就会知道,rank[i]表示第i个后缀的排名,sa[i]表示排名为i的后缀是谁,height[i]是排名为i和排名为i-1的后缀的最长公共前缀长度;
- 有了这些信息,根据height转移单调性,不妨对height数组建立ST表;
- 设后缀l与排名小于l的后缀的最长公共前缀的最小位置为L,后缀l与排名大于l的后缀的最长公共前缀的最大位置为R,根据height单调性,可以采用二分 + ST表O(1)查询的方式求得;
- 这样,问题就转变成了查询区间[L,R]内,sa[i]第k大是谁,标准的主席树操作。
整体时间复杂度O((n+m)logn),个人感觉难度接近(低于)regional银牌,但由于网络赛各种原因,这题最后出烂了?
我的代码
1 |
|
1002 主席树 + set
题意
给一个长度为105的排列A,有105次操作。第一种是给A[i]+107;第二种是给定一个k和r,要求找到一个x,使得k≤x并且x不等于A[1..r]中任意一个数。
强制在线。
分析
- 首先可以想到,由于一开始给的A数组是个排列,且第一种操作加的数字固定为107,所以,操作1可以认为在原序列中删除了A[i]这个数字;
- 那么我们可以把A[i]这个数字标记为已经被删除,那么下次查询的时候,一方面我们可以从原序列中去查询第一个大于等于k,且未在A[1..r]出现过的数字,另一方面,我们可以在标记删除的容器里二分找到第一个不小于k的数字,两者取小便可,根据排列的性质,这两个数字一定不会冲突;
- 所以问题就变成了,维护一个set,存放被删除的数字,构造一个主席树,然后查询的时候直接找到第一个合适的数字便可。
时间复杂度O((n+m)logn),个人觉得整体而言比1003简单,介于铜牌题和银牌题之间。
我的代码
已经将输入挂去除,read(x) 等价于 cin>>x。
1 |
|