uva 11235 Frequent values(游程编码+区间最小值查询)

游程编码的基本原理是:用一个符号值或串长代替具有相同值的连续符号(连续符号构成了一段连续的“行程”。游程编码因此而得名),使符号长度少于原始数据的长度。只在各行或者各列数据的代码发生变化时,一次记录该代码及相同代码重复的个数,从而实现数据的压缩。

游程编码(Run Length Encoding , RLE)

例如:5555557777733322221111111
游程编码为:(5,6)(7,5)(3,3)(2,4)(1,7)

解题思路很好:

用value[i] count[i] 分别表示 第i段的数值 和 出现次数;

num[p] left[p] right[p]分别表示位置p所在段的编号和左右端点的位置。

每次查询(left,right)的结果为以下三个部分的最大值:从left到left所在段结束处的元素个数、从right所在段开始到right处的元素个数、中间第num[left]+1段到第num[right]-1段的count的最大值。

特殊情况:如果left和right在同一段中,答案是R-L+1。

解决方法如下:

#include #include #include using namespace std; const int maxn = 100001; int n,q; int d[maxn][35]; int a[maxn]; int value[maxn],count_[maxn]; int num[maxn],left[maxn],right[maxn]; void RMQ_int(){ for(int i=0;i num[right_]-1) ans=max(ans,0); else{ ans=max(ans,RMQ(num[left_]+1,num[right_]-1)); } } printf("%d\n",ans); } } return 0; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:zoj3811Untrusted Patrol((bfs+并查集)
下一篇:树和二叉树总结及算法实现
相关文章

POJ 1089 Intervals 区间覆盖+ 贪心

TYVJ P2065(区间嵌套与统计)

POJ 2355(区间最大值-zkw线段树优化D

POJ 3171(区间覆盖最小代价)

区间完全覆盖问题 &&区间均取最少2个

连号区间数

HDU3208(区间指数和)

区间dp-zoj3541-The Last Puzzle

HDU 3954 区间更新区间查询 打怪升级

HDU3308:LCIS(线段树区间合并)

图文推荐
uva 11235 Frequent values(游程编码+区间最小值查询)
ZOJ 3640 Help Me
uva 11235 Frequent values(游程编码+区间最小值查询)
CF 518C(Anya and
uva 11235 Frequent values(游程编码+区间最小值查询)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-04 人气:6
本文关键词:
分享到:

相关文章

  • POJ 3368 Frequent values(线段树区间合并) 2014-07-18

    Frequent values Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 13352 Accepted: 4913 Description You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisti

  • UVA 818 Cutting Chains (DFS) 2012-01-11

    What a find! Anna Locke has just bought several links of chain some of which may be connected. They are made from zorkium, a material that was frequently used to manufacture jewelry in the last century, but is not used for that purpose anymore. It ha

  • UVa 548 Tree(建树,递归遍历) 2012-02-26

    题意 给你一个树的中序遍历和后序遍历 某个节点的权值为从根节点到该节点所经过节点的和 求权值最小的叶节点的值 如果存在多个 输出值最小的那个 把树建好就好说了 递归递归dfs msun保存最小叶节点权值 ans保存答案 #include #include #include using namespace std; const int maxn = 10005, INF = 0x3f3f3f3f; int in[maxn], post[maxn], msum, ans; struct node {

  • uva 1382 Distant Galaxy (枚举) 2012-03-30

    uva 1382 Distant Galaxy You are observing a distant galaxy using a telescope above the Astronomy Tower, and you think that a rectangle drawn in that galaxy whose edges are parallel to coordinate axes and contain maximum star systems on its edges has

  • UVa 704 - Colour Hash, 双向bfs,很给力 2012-03-30

    类型:隐式图搜索,双向bfs 原题: This puzzle consists of two wheels. Both wheels can rotate both clock and counter-clockwise. They contain 21 coloured pieces, 10 of which are rounded triangles and 11 of which are separators. Figure 1 shows the final position of ea

  • UVA - 10673 - Play with Floor and Ceil (简单数学!) 2012-04-12

    题目链接:Play with Floor and Ceil UVA - 10673 Play with Floor and Ceil Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu SubmitStatus Description Problem A Play with Floor and Ceil Input: standard input Output: standard output Tim

  • UVA - 1069 Always an integer (模拟) 2012-07-01

    Description Combinatorics is a branch of mathematics chiefly concerned with counting discrete objects. For instance, how many ways can you pick two people out of a crowd ofn people? Into how many regions can you divide a circular disk by connectingn

  • UVA - 12075 Counting Triangles 2012-09-02

    Description Triangles are polygons with three sides and strictly positive area. Lattice triangles are the triangles all whose vertexes have integer coordinates. In this problem you have to find the number of lattice triangles in anMxN grid. For examp

  • UVA - 11645 Bits 2012-09-12

    Description Problem J Bits Input: Standard Input Output: Standard Output A bit is a binary digit, taking a logical value of either "1" or "0" (also referred to as "true" or "false" respectively). And every decimal number has a binary representation w

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.051 (s). 10 q(s)