2013年省赛选拔组队系列赛3解题报告

2013年省赛选拔组队系列赛3-by logx

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


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.