【2018SCUACM Wednesday 4 ST】

题目来源

A:UVA 11235

B:UVA 1322

C:UVA 11992

D:UVA 1400

E:UVA 1400

F:HDU 1754

G:POJ 2828

解题报告

A:由于数字是连续递增的,所以相同的数字必然集中在连续的一段上,我们用\(left[i]\)表示第\(i\)个数字\(x\),其第一次出现的位置;\(right[i]\)表示第\(i\)个数字\(x\)最后一次出现的位置。比如-1 -1 1 1 1 2 3,\(left[4]=3,right[4]=5\)。同时,我们对第\(i\)个数字记录下到它本身为止(包括他本身)这个数字一共出现了多少次。于是对于每个询问区间\([a,b]),有以下几种情况:

①\([a,b]\)为同一个数字段,此时只需要输出\(frequency[b]-frequency[a]+1\)即可。

②\([a,b]\)为两个数字段,此时可区分为\([a,right[a]]\)与\([left[b],b]\)(\(left[b]=right[a]+1\))两个数字段,那么答案显然就是

\(max(frequency[right[a]]-frequency[a]+1,frequency[b]-frequency[left[b]]+1)\)

③\([a,b]\)为三个或以上数字段,则可划分为\([a,right[a]\),\([right[a]+1,left[b]-1]\),\([left[b],b]\),分别记作区间\(A,B,C\)。其中区间\(A,C\)的计算方式同②,中间的区间B实际上就是求一个\(RMQ\),线段树或者ST表都可以。不过既然比赛标题是ST表,就用ST表吧。

简单说一下ST表的思路:设\(maxFre[i][j]\)表示从\(i\)开始(包含\(i\)),连续\(2^j\)个数字中出现次数最多的数字的出现次数,即\([i,i+2^j-1]\)这个区间内的最多数字出现次数。如何转移呢?注意到\([i,i+2^j-1]\)可以被划分为两个长度均为\(2^{j-1}\)的子区间\([i,i+2^{j-1}-1]\)与\([i+2^{j-1},i+2^j-1]\),因此不难得出下列状态转移方程式:

\(maxFre[i][j]=max(maxFre[i][j-1],maxFre[i+2^{j-1}][j-1])\),根据定义,当\(j=0\)时就是\(i\)自身,初始值\(maxFre[i][0]=frequency[i]\)。

如何做到\(O(1)\)查询?显然有\(2^{log_2{x}}\ge \frac{x}{2}\),记\(t=floor(log_2{x})\),则因此对于长度为\(x\)的区间\([A,B]\),只要取两个长度都超过\(\frac{x}{2}\)且加起来能覆盖整个区间的子区间就可以计算出最大值,这两个区间我们根据上面的推导很容易获得,分别是\([A,A+2^t-1]\)与\([B-2^t+1,B]\),也就是说最大值一定是\(maxFre[A][t]\)或\(maxFre[B-2^t+1][t]\),取一个\(max\)即可。

 

B:

C:

D:

E:

F:

G:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*