题目链接:uva 11235 - Frequent values
题目大意:给定一个非降序的整数数组,要求计算对于一些询问(i,j),回答ai,ai+1,…,aj中出现最多的数出现的次数。
解题思路:因为序列为非降序的,所以相同的数字肯定是靠在一起的,所以用o(n)的方法处理处每段相同数字的区间。然后对于每次询问:
- num[i]=num[j]:j−i+1
- numi≠numj:max(RMQ(righti+1,reftj−1),max(righti−i+1,j−leftj+1))
using namespace std;
const int maxn = 1e5+5;
int N, Q, num[maxn], rmq[maxn][20];
int left[maxn], right[maxn];
void RMQ_init () {
memset(rmq, 0, sizeof(rmq));
for (int i = 1; i <= N; i++)
rmq[i][0] = right[i] - left[i] + 1;
for (int j = 1; (1<<j) <= N; j++) {
for (int i = 1; i + (1<<j) - 1 <= N; i++)
rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
}
}
void init () {
for (int i = 1; i <= N; i++)
scanf("%d", &num[i]);
left[1] = 1;
for (int i = 2; i <= N; i++) {
if (num[i] == num[i-1])
left[i] = left[i-1];
else
left[i] = i;
}
right[N] = N;
for (int i = N-1; i >= 1; i--) {
if (num[i] == num[i+1])
right[i] = right[i+1];
else
right[i] = i;
}
RMQ_init();
}
int RMQ (int L, int R) {
if (L > R)
return 0;
int k = 0;
while (1<<(k+1) <= R-L+1)
k++;
return max(rmq[L][k], rmq[R-(1<<k)+1][k]);
}
int main () {
while (scanf("%d%d", &N, &Q) == 2 && N) {
init();
int x, y;
for (int i = 0; i < Q; i++) {
scanf("%d%d", &x, &y);
if (num[x] == num[y])
printf("%d\n", y - x + 1);
else
printf("%d\n", max(RMQ(right[x]+1, left[y]-1), max(right[x] - x + 1, y - left[y] + 1)));
}
}
return 0;
}
分享到:
相关推荐
Basic concepts and a road map Efficient and scalable frequent itemset mining methods Constraint-based association mining Summary
广工《算法和高级数据结构教程课程设计》 Frequent Values(poj 3368) C语言实现
Subposition assembly-based construction of non-frequent concept semi-lattice
从FPARM-Frequent-Patterns-and-Association-Rule-Miner文件夹运行程序注意:对于Command_Line_Version,数据集路径应在src\Command_Line_Version\Main.java 文件中指定 Command_Line_Version: $ javac src\Command_...
高效的单次频繁模式挖掘--Efficient single-pass frequent pattern mining.pdf
文本挖掘频繁模式分析 Aprioiri 频繁模式分析 - Java 实现 在 Java 中实现了 Apriori 频繁模式挖掘算法,以从会议论文中挖掘频繁模式。 最终输出是从 5 个领域的论文标题中提取具有高度代表性的短语,即: ...
频繁项 用于在线业务的机器学习应用程序。 #0.Overview 这个项目能够在大量的交易数据中找到频繁的项目组。 它经过精心设计,可以使用更少的内存来允许更大的输入规模。 它能够检索所有大小的频繁组,而不仅仅是...
程序员英语词汇宝典 本列表中的单词是英语类计算机书籍,文档,文章中频繁的常用技术词汇,也是程序员工作中常见的英语词汇,最终目的是希望程序员集合自身的英语基础,在掌握列表中的词汇后,可以无障碍阅读英语...
查找频繁项集 我们使用A-priori算法找到频繁项集。 在输入文件的每一行上,每个8个字符的字符串代表该会话期间浏览的项目的ID。 这些项目用空格分隔。 输出包括大小分别为2和3的前5组,即置信度值最高的那些
显示历史频繁站点按钮扩展替换Firefox的“显示历史记录”按钮以列出常用站点。 在AMO上:
查找最常见的单词网页 REST API使用Spring Boot从网站中查找最常用的单词。 概述 在具有RESTful端点的Spring Boot项目中,从网站页面定义中找到最常用的单词。 接收网页URL的列表作为输入,并按单词的长度返回这些...
频繁项目集项目 四种用于挖掘频繁项集的算法的可伸缩性研究 该项目的重点是比较用于查找频繁项集的四种算法的性能:A-Priori,PCY,Multistage和Mutlihash算法。 我实现了这些算法,每个算法都有自己的类,并通过将...
java8集合源码频繁 描述 这是一款轻量级音频分析仪,使用 Steinberg ASIO 协议对多通道音频流进行频谱分析。 此应用程序的预期用例是用于现场音频工程设置,因此侧重于轻量级安装、快速设置和操作、稳定性以及出色的...
Mining Top-k Approximate Frequent Patterns,何增友,,requent pattern (itemset) mining in transactional databases is one of the most well-studied problems in data mining. One obstacle that limits the ...
搜索记录频繁模式挖掘 这是一个《大数据挖掘技术》@复旦课程项目,试图从搜狗实验室用户查询日志数据(2008)中找出搜索记录中有较高支持度关键词的频繁二项集。在实现层面上,我搭建了一个由五台服务器组成的微型 ...
HPFP-Miner:一种新并行化的频繁项集挖掘算法,陈晓云,何艳珊,频繁项集挖掘是数据挖掘领域的一个重要的基本问题,它可以用于多种数据挖掘的任务中。这类挖掘任务大多需要多次扫描数据库,如果
并行频繁相机挖掘算法 Frequent itemset mining is a fundamental and essential issue in data mining field and can be used in many data mining tasks. Most of these mining tasks require multiple passes ...
The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs, ...
英文原版论文:fp-growth Mining Frequent Patterns without Candidate Generation:A Frequent-Pattern Tree