A:Snakes
B:D1-Digit Divisibility
C:Stacking Blocks
D:Equal Distance
E:Filling The Cone
F:Longest Sub-sequence Again!
这题有点单调队列的思想
先离散化处理,0<ai<1000000000但数据只有100000可以把a[i]的每个数据按从大到小赋值为1到100000
比如a[0]=100 a[1] =10 a[2]=1 处理后a[0]=3 a[1]=2 a[2]=1
记录位置,两次快排即可
定义一个数组f[i]表示一段数据中i的个数,num表示
给你一段子序列里面含有≤k+1种的数据,可以知道去掉≤k个数据后最大的连续子序列是所有数据中数量最大的那个,比如k=2 f[1]=1 f[2]=2 f[3]=3 其他数为0,去掉1 和 2留下3最大
看样例:
设子序列开头为head=0
class(当前数据中已有的数据种类)初始化0
f[ i ](一段数据中i的个数)初始化0
k=1
设max为最大连续子序列
head 0 1 1 1 1 1 1 6 6
样例ai 2 7 3 7 7 3 7 5 7
位置 0 1 2 3 4 5 6 7 8
class 1 2 3 2 2 2 2 3 2
max 1 1 1 2 2 1 4 4 4
当找到第2个位置时种类超过k+1,就要从head删到2这个位置删除了2这类数,class-=1
当在第7个位置时种类超过k+1,从head删到第6个位置删除了3这类数,class-=1
更新max的时候因为只有f[a[i]]++,max和f[a[i]]比较去取大值即可
G:Rounding to Fibonacci
H:Cogwheels