怎样做美食网站,wordpress固定链接中文,网站基本设置,凌云网最新消息今天知识点#xff1a;
区间统计不超过h的值#xff1b;
查询二维区间的极差#xff1b;
求区间最频繁数#xff1b;
目录
HDU4417#xff1a;超级马里奥
思路#xff1a;
poj2019:玉米田
思路#xff1a;
POJ3368:频繁值
思路#xff1a; HDU4417#xff1…今天知识点
区间统计不超过h的值
查询二维区间的极差
求区间最频繁数
目录
HDU4417超级马里奥
思路
poj2019:玉米田
思路
POJ3368:频繁值
思路 HDU4417超级马里奥
在长n的道路中。每个i点都有高度Hi的砖输入l,r,h表示他最高能跳h问在区间[l,r]中最多可以跳多少砖块
输入 1 10 10 0 5 2 7 5 4 3 8 7 7 2 8 6 3 5 0 1 3 1 1 9 4 0 1 0 3 5 5 5 5 1 4 6 3 1 5 7 5 7 3
输出
Case1:
4 0 0 3 1 2 0 1 5 1 思路
其实就是统计区间中有多少个不超过h的值。
我们采用分块处理对于完整的块可以采用排序然后upper_bound直接返回个数。不完整的块暴力所查区间
#include bits/stdc.h
using namespace std;
const int maxn1e510;
int L[maxn],R[maxn],be[maxn];
int a[maxn],tmp[maxn],n,m;void build(){int tsqrt(n);int numn/t;if(n%num)num;for(int i1;inum;i){L[i](i-1)*t1;R[i]i*t;}R[num]n;for(int i1;in;i){be[i](i-1)/t1;}for(int i1;inum;i){sort(tmpL[i],tmp1R[i]);//每块排序}
}int query(int l,int r,int h){int ans0;if(be[l]be[r]){//在同一块就暴力for(int il;ir;i)if(a[i]h)ans;}else{for(int il;iR[be[l]];i){//左端块暴力if(a[i]h)ans;}for(int ibe[l]1;ibe[r];i){//中间块直接lowerboundansupper_bound(tmpL[i],tmpR[i]1,h)-tmp-L[i];//直接获取能跳过去的个数}for(int iL[be[r]];ir;i){//右端块暴力if(a[i]h) ans;}}return ans;
}
int main(){int t;cint;for(int cas1;cast;cas){scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,a[i]);tmp[i]a[i];}build();printf(Case %d:\n,cas);while(m--){int l,r,h;scanf(%d%d%d,l,r,h);printf(%d\n,query(l,r,h));}}
}poj2019:玉米田
为了寻找平坦的地来种玉米在n*n公顷的农场中每公顷都有一个整数高度查询k次对于(x,y)为左顶点的c*c子矩阵中的最大和最小高度差是多少
输入 5 3 1 5 1 2 6 3 1 3 5 2 7 7 2 4 6 1 9 9 8 6 5 0 6 9 3 9 1 2 思路
首先这题是个离线的区间最值题倍增就行了
一维max不满足减法所以不能直接建立二维max数组那么就用多个一维的max数组等价成二维的即可。
但是我们仍然开三维数组f[x][y][j]表示(x,y)点向右扩展1j长度的最值
因为每次查询都要取一次log当查询量较大时候就不行了所以可以利用动态规划来初始化log函数因为如果i(i-1)是0那么log(i)log(i-1)1否则log(i)log(i-1)。
void initlog(){b[0]-1;for(int i1;imaxn;i){b[i](i(i-1))?b[i-1]:b[i-1]1;}
}
#include bits/stdc.h
using namespace std;
const int maxn260;
int a[maxn][maxn],b[maxn];
int f_max[maxn][maxn][11],f_min[maxn][maxn][11];//f[x][y][j]表示(x,y)点向右扩展1j长度的最值void initlog(){b[0]-1;for(int i1;imaxn;i){b[i](i(i-1))?b[i-1]:b[i-1]1;}
}void ST(int n){for(int k1;kn;k)for(int i1;in;i)f_max[k][i][0]f_min[k][i][0]a[k][i];//初始化for(int k1;kn;k)//一行一行处理for(int j1;jb[n];j)//j是二进制大小for(int i1;i(1j)-1n;i){//i是每个列值f_max[k][i][j]max(f_max[k][i][j-1],f_max[k][i(1(j-1))][j-1]);//更新最大值和最小值f_min[k][i][j]min(f_min[k][i][j-1],f_min[k][i(1(j-1))][j-1]);}
}void solve(int x,int y,int c){//从xy开始向右下扩展c长度int kb[c];int maxx-1,minx0x3f3f3f3f;int ly,ryc-1;for(int ix;ixc;i){//查询每行的最值maxxmax(maxx,max(f_max[i][l][k],f_max[i][r-(1k)1][k]));minxmin(minx,min(f_min[i][l][k],f_min[i][r-(1k)1][k]));}printf(%d\n,maxx-minx);
}int main(){int n,k,c;int x,y;initlog();while(scanf(%d%d%d,n,c,k)!EOF){//输入n大小c大小k次数for(int i1;in;i)for(int j1;jn;j)scanf(%d,a[i][j]);ST(n);for(int i0;ik;i){scanf(%d%d,x,y);solve(x,y,c);}}
}POJ3368:频繁值
给定一个非递减的整数序列n进行q次查询确定i到j之间的最频繁的值 10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0 输出 1 4 3
思路
注意到非递减的性质不难想到对应的频繁数1 2 1 2 3 4 1 1 2 3然后就转化成了离线的区间最值。
直接设置f[i][j]表示存放[i,i2^j-1]长度2^j的最值初始化f[i][0]然后在查询区间的时候注意单独处理最左边的元素剩余的区间就能直接查询了
#include bits/stdc.h
using namespace std;
const int maxn100010;
int a[maxn],b[maxn],f[maxn][20];//a存放数据b存放log值f存放[i,i2^j-1]长度2^jvoid initlog(){b[0]-1;for(int i1;imaxn;i){b[i](i(i-1))?b[i-1]:b[i-1]1;}
}void ST(int n){for(int j1;jb[n];j){for(int i1;in-(1j)1;i){f[i][j]max(f[i][j-1],f[i(1(j-1))][j-1]);}}
}int RMQ(int l,int r){if(lr)return 0;int kb[r-l1];return max(f[l][k],f[r-(1k)1][k]);
}
int main(){int n,q,l,r;initlog();while(~scanf(%d,n)n){cinq;for(int i1;in;i){scanf(%d,a[i]);if(i1){ //初始化过程f[i][0]1;continue;}if(a[i]a[i-1]){f[i][0]f[i-1][0]1;}else f[i][0]1; }ST(n);for(int j1;jq;j){scanf(%d%d,l,r);int tl;while(tra[t]a[t-1]) t;//将查询区间分开printf(%d\n,max(t-l,RMQ(t,r)));}}
}
