一 题意:给定递增序列,找出连续出现的最长子序列,然后求出它的长度,即最高频率。注意必须是连续出现。
二 算法:可以事先求出序列中每个数字的最高频率,比如序列(-1,-1,1,1,1,1,3,10,10,10)中各个数字的最高频率为:
(-1: 2), (1: 4), (3: 1), (10, 3),对于区间[s,t],仅首部和尾部有可能是从同一个数字中截断的,去掉首尾后的中间部分数字的
最高频率可以直接得到。最后比较首部,尾部,和中间部分的频率,就可以得到[s,t]的最高频率了,分三种情况讨论:
有色部分为要查找的区间[s,t],红色代表首部,蓝色代表尾部,绿色代表中间部分
1) 1111111111111
只有一种数字,直接返回(t-s+1)
2) 1111122222222222
去掉首部和尾部后,没有中间部分,直接返回首部频率和尾部频率的最大值
3) 111111222333444444
去掉首部和尾部后,中间部分为222333,在线段树中查找2和3的最高频率,综合首部尾部频率,得到答案。
问题的关键在于查找中间部分的最高频率,设中间部分有N个不同的数字,如果对每个数字都扫描一遍,算法复杂度
为O(N),必然超时,处理的时候,先把序列离散话,即把连续出现的数字聚集到一点,并计算它的频率,这样原序列转
化为一系列点集,比起原系列来,这个点集小得多,然后对这些点集根据建立线段树,线段存储的是点区间内的最高频率。
从线段树中查找,算法复杂度变为O(logN)
三 代码
#include <stdio.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define MAX(a, b) (a) > (b) ? (a) : (b)
#define inf 20000000
#define N 100001
int tree[262144]; /* 保存每条线段的最高频率 */
int pos[N]; /* pos[i] = j 表示i在离散表中的位置为j */
/* 区间[l,r]内的数相同,都是num */
struct node {
int l, r;
int num;
};
struct node table[N];
int M;
void build_tree(int n)
{
int i;
for (M = 1; M < (n+2); M <<= 1);
//存储数据的叶子节点
for (i = 1; i <= n; i++) {
tree[i+M] = (table[i].r-table[i].l+1);
}
//不用的叶子节点
for (i = n+1; i%M != 1; i++) {
tree[(i%M)+M] = -1;
}
//分支节点
for (i = M-1; i > 0 ; i--) {
tree[i] = MAX(tree[i<<1], tree[(i<<1)+1]);
}
}
int query(int s, int t)
{
int max_freq;
max_freq = -1;
for (s = s+M-1, t = t+M+1; (s^t) != 1; s >>= 1, t >>= 1) {
if (~s&1) {
max_freq = MAX(max_freq, tree[s^1]);
}
if (t&1) {
max_freq = MAX(max_freq, tree[t^1]);
}
}
return max_freq;
}
int main()
{
int n, p, q, i, s, t, ans, ss, tt, num;
while (scanf("%d %d", &n, &q), n) {
table[p = 0].num = inf;
//输入,离散化
for (i = 1; i <= n; i++) {
scanf("%d", &num);
if (num == table[p].num) {
table[p].r = i;
pos[i] = p;
}
else {
p++;
table[p].l = table[p].r = i;
table[p].num = num;
pos[i] = p;
}
}
build_tree(p);
while (q--) {
scanf("%d %d", &s, &t);
//[s,t]内只有一种数
if (pos[s] == pos[t]) {
ans = (t-s+1);
}
else {
ans = -inf;
/* [s,t]内至少有两种数,把首尾两种数去掉
* 然后查询剩下的数的区间[ss,tt]
*/
ss = table[pos[s]].r+1;
tt = table[pos[t]].l-1;
if (tt >= ss) {
ans = query(pos[ss], pos[tt]);
}
ans = MAX(ans, MAX(ss-s, t-tt));
}
printf("%d\n", ans);
}
}
return 0;
}
分享到:
相关推荐
广工《算法和高级数据结构教程课程设计》 Frequent Values(poj 3368) C语言实现
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1740501
POJ3468,线段树处理,注意longlongint
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 ...
NULL 博文链接:https://128kj.iteye.com/blog/1746750
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
题目分类 目前网上最全的 PKU 的 网上所有的 分类总结 祝ACM 一路顺风
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码